算法复习

因为晚上算法上机实验，我复习了一些算法内容。思绪在几种排序方法间切换：从直观的插入排序，到分治的归并排序，再到高效的快速排序及其变体。这些精妙的逻辑，像是为混沌世界建立秩序的种种尝试。

插入排序（Insertion Sort, IS）

基本思想：将元素逐个插入到已排序序列的适当位置

python

1
2
3
4
5
6
7
8
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

特点：

  • 时间复杂度：O(n²) 最坏/平均，O(n) 最好（已排序）
  • 空间复杂度：O(1)
  • 稳定排序
  • 对小规模数据高效

自顶向下归并排序（Top-down Mergesort, TDM）

基本思想：递归地将数组分成两半，分别排序后合并

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

自底向上归并排序（Bottom-up Mergesort, BUM）

基本思想：从单个元素开始，迭代地合并相邻的有序段

python

1
2
3
4
5
6
7
8
9
10
def bottom_up_merge_sort(arr):
    n = len(arr)
    size = 1
    
    while size < n:
        for start in range(0, n, 2 * size):
            mid = min(start + size, n)
            end = min(start + 2 * size, n)
            merge(arr, start, mid, end)
        size *= 2

TDM vs BUM：

  • TDM：递归实现，可能栈溢出
  • BUM：迭代实现，无递归开销
  • 两者时间复杂度相同：O(n log n)

随机快速排序（Random Quicksort, RQ）

基本思想：随机选择pivot，分区后递归排序

python

1
2
3
4
5
6
7
8
9
10
11
12
import random

def quicksort(arr, low, high):
    if low < high:
        pivot_index = random_partition(arr, low, high)
        quicksort(arr, low, pivot_index - 1)
        quicksort(arr, pivot_index + 1, high)

def random_partition(arr, low, high):
    random_index = random.randint(low, high)
    arr[random_index], arr[high] = arr[high], arr[random_index]
    return partition(arr, low, high)

Dijkstra 3-路划分快速排序（QD3P）

基本思想：将数组分为三部分：< pivot, = pivot, > pivot

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def three_way_quicksort(arr, low, high):
    if low >= high:
        return
    
    lt, gt = three_way_partition(arr, low, high)
    three_way_quicksort(arr, low, lt - 1)
    three_way_quicksort(arr, gt + 1, high)

def three_way_partition(arr, low, high):
    pivot = arr[low]
    lt = low      # 小于pivot的右边界
    i = low + 1   # 当前元素
    gt = high     # 大于pivot的左边界
    
    while i <= gt:
        if arr[i] < pivot:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
            i += 1
        elif arr[i] > pivot:
            arr[i], arr[gt] = arr[gt], arr[i]
            gt -= 1
        else:
            i += 1
    
    return lt, gt

《瓦尔登湖》的生活

而在《瓦尔登湖》中，我看到了另一种“有序生活”。梭罗在森林里亲手搭建小屋，精确记录生活账本，务实应对生存挑战。他躬耕于湖畔，不仅建起了一个栖身之所，更构筑了一种高度自觉的生活范式。

这让我陷入沉思：我能清晰地解析算法逻辑，但对于自己的生活，是否也曾如此清醒地审视过？梭罗的下一句话，更是击中了这种困惑的核心：

“我们为什么要活得这么匆忙，浪费生活？”