06_排序

排序

竞赛中优先使用内置 sorted / list.sort（Timsort，稳定 $O(n \log n)$）；手写六大排序主要用于理解算法与应付考点。排序本身很少是考点，考点是排序后的性质——贪心按序取、双指针要求有序、二分要求有序。

arr.sort(key=lambda x: (-x[0], x[1]))   # 第一维降序、第二维升序
b = sorted(arr, key=lambda x: abs(x))   # 按绝对值

冒泡排序

相邻两两比较，每轮把当前最大值「冒泡」到末尾。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:        # 一轮无交换说明已有序，提前结束
            break
    return arr

时间 $O(n^2)$（有序输入 $O(n)$），空间 $O(1)$，稳定。

选择排序

每轮从未排序部分选出最小值，放到已排序部分的末尾。交换次数最少（至多 $n-1$ 次），但比较次数固定 $O(n^2)$。

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        mn = i
        for j in range(i + 1, n):
            if arr[j] < arr[mn]:
                mn = j
        arr[i], arr[mn] = arr[mn], arr[i]
    return arr

时间 $O(n^2)$，空间 $O(1)$，不稳定（交换会跨越相等元素）。

插入排序

像整理扑克牌：把新元素插入到前面已排序部分的正确位置。小规模或基本有序的数据非常快，是 Timsort 的组成部分。

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
    return arr

时间 $O(n^2)$（基本有序时接近 $O(n)$），空间 $O(1)$，稳定。

快速排序

分治：partition 选一个基准（pivot），把比它小的换到左边，基准归位，再对左右两段递归。平均 $O(n\log n)$；数组已有序且总取首元素为基准时退化 $O(n^2)$（随机化基准可规避）。不稳定。

def quicksort(arr, lo, hi):
    if lo >= hi:
        return
    p = part(arr, lo, hi)
    quicksort(arr, lo, p - 1) 
    quicksort(arr, p + 1, hi)

def part(arr, lo, hi):
    x = arr[lo]
    i = lo
    for j in range(lo + 1, hi + 1):
        if arr[j] < x:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[lo], arr[i] = arr[i], arr[lo]
    return i

归并排序

分治：递归拆成两半各自排好，再线性归并两个有序段。任何输入都稳定 $O(n\log n)$，代价是 $O(n)$ 辅助数组。稳定（相等时先取左半段）。

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):
    res = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= 保证稳定性
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

经典应用——逆序对计数：归并时每当从右半段取走 right[j]，左半段剩余元素都和它构成逆序对，cnt += len(left) - i，$O(n\log n)$ 数完逆序对。

堆排序

建大顶堆后反复「取堆顶 + 下沉」。竞赛中直接用 heapq（见《05_优先队列》）；手写版理解堆的 sift down 机制：

def heap_sort(arr):
    n = len(arr)

    # 自底向上建大顶堆：从最后一个非叶子节点开始下沉
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

    # 每次把最大值换到末尾，堆范围 -1，重新下沉
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, 0, end)

    return arr

def sift_down(arr, i, n):
    while True:
        largest = i
        l, r = 2 * i + 1, 2 * i + 2
        if l < n and arr[l] > arr[largest]:
            largest = l
        if r < n and arr[r] > arr[largest]:
            largest = r
        if largest == i:
            return
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest

if __name__ == "__main__":
    nums = [3, 6, 8, 10, 1, 2, 1]
    print(heap_sort(nums))  # [1, 1, 2, 3, 6, 8, 10]

时间 $O(n\log n)$，空间 $O(1)$，不稳定。

总结

算法	平均	最坏	空间	稳定	备注
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	✅	有序输入 $O(n)$
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	❌	交换次数最少
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	✅	基本有序时最快
快速排序	$O(n\log n)$	$O(n^2)$	$O(\log n)$ 栈	❌	随机化基准防退化
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$	✅	可数逆序对
堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	❌	竞赛用 heapq
Python sort	$O(n\log n)$	$O(n\log n)$	$O(n)$	✅	Timsort，首选

关联：排序配合贪心的经典套路见《贪心算法》；自定义比较器 / 坐标压缩见《其他算法/08_自定义比较器和坐标压缩》。