排序：从冒泡到 TimSort

第二十一章：排序 — 从冒泡到 TimSort

打开 Python 解释器，输入 sorted([3, 1, 4, 1, 5, 9])，你会在微秒级得到 [1, 1, 3, 4, 5, 9]。这看起来理所当然，但背后是 60 多年计算机科学家的智慧结晶。排序是计算机科学中被研究得最透彻的问题之一——从 1945 年冯·诺依曼在 EDVAC 上实现的归并排序，到 2002 年 Tim Peters 为 CPython 设计的 TimSort，每一代算法都在向"完美排序"逼近。

为什么排序如此重要？因为它是其他算法的基石。二分查找需要有序数组；数据库索引本质上是排序后的映射；操作系统的进程调度需要按优先级排序；搜索引擎的结果需要按相关度排序。Donald Knuth 在《The Art of Computer Programming》第三卷中用了整整一卷来讲排序和查找，他说："一台计算机大约 25% 的时间花在排序上。"

这一章我们从最简单的冒泡排序出发，一路走到工业级的 TimSort 和 introsort，覆盖所有你需要知道的排序知识。

Level 1 · 你需要知道的

21.1 八大排序算法概览

在深入每个算法之前，先看全局。下表列出了八种经典排序算法的核心指标：

其中 n 是元素个数，k 是值域大小，d 是最大位数。

注意一个关键区分：前六种是比较排序（comparison sort），只通过两两比较来确定顺序；后两种（加上桶排序）是非比较排序（non-comparison sort），利用元素本身的数值特征来定位。这个区分至关重要——比较排序有 O(n log n) 的理论下界，而非比较排序可以突破它。

21.2 冒泡排序（Bubble Sort）

冒泡排序是最直观的排序算法：反复遍历数组，比较相邻元素，如果顺序错误就交换。每一轮遍历至少能把一个最大元素"冒泡"到正确位置。

def bubble_sort(arr):
    """冒泡排序：相邻元素比较交换"""
    n = len(arr)
    for i in range(n):
        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)
• 最坏情况：数组逆序，需要 n(n-1)/2 次比较和交换，O(n²)
• 平均情况：O(n²)
• 稳定性：稳定（相等元素不会交换）
• 空间：O(1)，原地排序

冒泡排序的唯一优点是简单和稳定。实际中几乎没有使用它的理由——即使是 O(n²) 级别的算法，插入排序也比它快得多。

21.3 选择排序（Selection Sort）

选择排序的思路：每次从未排序部分选出最小元素，放到已排序部分的末尾。

def selection_sort(arr):
    """选择排序：每次选最小的放前面"""
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

分析：

• 无论输入什么，比较次数都是 n(n-1)/2，所以最好、最坏、平均都是 O(n²)
• 交换次数最多 n-1 次——这是选择排序的唯一优势
• 不稳定：例如 [5a, 5b, 3]，第一轮 5a 和 3 交换，5a 跑到 5b 后面
• 空间：O(1)

选择排序虽然比较次数固定，但交换次数少的优势在现代硬件上并不明显（因为比较也需要访存），所以实际中也很少使用。

21.4 插入排序（Insertion Sort）

插入排序像打扑克牌时整理手牌：拿到一张新牌，从右到左找到它该插入的位置。

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)
• 最坏情况：数组逆序，O(n²)
• 平均情况：O(n²)
• 稳定：相等元素不会改变相对顺序
• 空间：O(1)

插入排序是 O(n²) 算法中实际最快的，原因：

1. 内层循环有条件退出（不像冒泡和选择那样每次都走完）
2. 对近乎有序的数据退化到 O(n)
3. 缓存友好：总是访问相邻内存
4. 常数因子小：每次比较只做一次赋值（不是交换）

这些特性使得插入排序在小数组（n < 16~64）上比快排还快。TimSort 和 introsort 都在小子数组上切换到插入排序。

21.5 归并排序（Merge Sort）

归并排序是分治（divide and conquer）思想的经典体现：

1. 分：把数组从中间切成两半
2. 治：递归地对两半分别排序
3. 合：把两个已排序的半数组合并成一个有序数组

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

分析：

• 时间复杂度：无论什么输入都是 O(n log n)。递推关系 T(n) = 2T(n/2) + O(n)，由主定理得 O(n log n)
• 空间：O(n)——需要额外数组来合并
• 稳定：merge 中用 <= 而不是 < 就能保证稳定
• 递归深度：O(log n)

原地归并排序存在但很复杂（Kronrod 1969），实际中很少使用。归并排序的主要劣势就是需要 O(n) 额外空间。

归并排序的优势场景：

• 链表排序：链表不能随机访问，快排的 partition 退化，但归并排序只需改指针
• 外部排序：当数据太大装不进内存时，多路归并是标准做法
• 需要稳定排序时：Python 的 TimSort 就是基于归并排序的改良

21.6 快速排序（Quick Sort）

快速排序是 Tony Hoare 1959 年发明的，至今仍是实际中最常用的排序算法之一。核心思想：

1. 选一个元素作为基准（pivot）
2. 分区（partition）：把数组分成"比 pivot 小"和"比 pivot 大"两部分
3. 递归地对两部分排序

def quicksort(arr, lo=0, hi=None):
    """快速排序（Lomuto 分区方案）"""
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        pivot_idx = partition_lomuto(arr, lo, hi)
        quicksort(arr, lo, pivot_idx - 1)
        quicksort(arr, pivot_idx + 1, hi)
    return arr


def partition_lomuto(arr, lo, hi):
    """Lomuto 分区：以最后一个元素为 pivot"""
    pivot = arr[hi]
    i = lo  # i 指向"小于区"的下一个位置
    for j in range(lo, hi):
        if arr[j] <= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[hi] = arr[hi], arr[i]
    return i

Lomuto vs Hoare 分区

Lomuto 分区（上面的代码）：

• 简单直观，一个指针 i 维护"小于区"的边界
• 缺点：在有大量重复元素时退化，交换次数多

Hoare 分区：

• 用两个指针从两端向中间扫描
• 交换次数平均少一半
• 代码稍复杂

def partition_hoare(arr, lo, hi):
    """Hoare 分区：两端向中间扫描"""
    pivot = arr[lo]
    i = lo - 1
    j = hi + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

随机化 Pivot

最坏情况 O(n²) 出现在每次 pivot 恰好是最大或最小元素时。解决方案：随机选择 pivot。

import random

def quicksort_random(arr, lo=0, hi=None):
    """随机化快排"""
    if hi is None:
        hi = len(arr) - 1
    if lo < hi:
        # 随机选一个元素和最后一个交换，然后用 Lomuto
        rand_idx = random.randint(lo, hi)
        arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx]
        pivot_idx = partition_lomuto(arr, lo, hi)
        quicksort_random(arr, lo, pivot_idx - 1)
        quicksort_random(arr, pivot_idx + 1, hi)
    return arr

随机化后，最坏情况 O(n²) 的概率极低（需要每次随机都选到极值）。期望时间复杂度 O(n log n)。

快排分析：

• 平均时间：O(n log n)，常数因子比归并排序小
• 最坏时间：O(n²)（但随机化后几乎不可能）
• 空间：O(log n)——递归栈深度（平均情况）
• 不稳定：partition 过程中交换会改变相等元素的顺序

21.7 堆排序简介

堆排序利用最大堆的性质：堆顶总是最大元素。

1. 建堆：O(n)
2. 反复取出堆顶（最大值）放到数组末尾，然后堆大小减 1，下沉调整

def heap_sort(arr):
    """堆排序：建堆 + 反复取最大"""
    n = len(arr)
    
    # 建最大堆（从最后一个非叶子节点开始下沉）
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)
    
    # 逐个取出最大值
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 堆顶和末尾交换
        sift_down(arr, 0, i)  # 缩小堆范围，下沉新堆顶
    
    return arr


def sift_down(arr, root, size):
    """下沉操作"""
    while True:
        largest = root
        left = 2 * root + 1
        right = 2 * root + 2
        
        if left < size and arr[left] > arr[largest]:
            largest = left
        if right < size and arr[right] > arr[largest]:
            largest = right
        
        if largest == root:
            break
        arr[root], arr[largest] = arr[largest], arr[root]
        root = largest

分析：

• 时间：O(n log n)，无论什么输入
• 空间：O(1)，原地排序
• 不稳定

堆排序的详细讨论见第 12 章（堆与优先队列）。这里只需知道：堆排序保证最坏情况 O(n log n)，但实际中比快排慢（缓存不友好——跳跃访问）。

21.8 计数排序（Counting Sort）

当元素是范围有限的整数时，可以用计数排序突破 O(n log n) 的下界。

def counting_sort(arr, max_val=None):
    """计数排序：适用于非负整数，值域不大"""
    if not arr:
        return arr
    
    if max_val is None:
        max_val = max(arr)
    
    # 计数
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    
    # 前缀和（保证稳定性）
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 从后往前放置（保证稳定性）
    result = [0] * len(arr)
    for x in reversed(arr):
        count[x] -= 1
        result[count[x]] = x
    
    return result

分析：

• 时间：O(n + k)，k 是值域大小
• 空间：O(n + k)
• 稳定

计数排序的限制：值域 k 不能太大。如果排序 100 万个 0100 的整数，非常高效；但如果排序 100 个 010亿 的整数，count 数组就太大了。

21.9 桶排序（Bucket Sort）

桶排序是计数排序的泛化：把元素分到若干个"桶"里，每个桶内部用其他排序算法（通常是插入排序）排序，然后按顺序连接所有桶。

def bucket_sort(arr, num_buckets=10):
    """桶排序：适用于均匀分布的浮点数"""
    if not arr:
        return arr
    
    min_val, max_val = min(arr), max(arr)
    if min_val == max_val:
        return arr
    
    bucket_range = (max_val - min_val) / num_buckets
    buckets = [[] for _ in range(num_buckets)]
    
    for x in arr:
        idx = int((x - min_val) / bucket_range)
        if idx == num_buckets:
            idx -= 1
        buckets[idx].append(x)
    
    # 每个桶内排序（用插入排序）
    result = []
    for bucket in buckets:
        insertion_sort(bucket)
        result.extend(bucket)
    
    return result

分析：

• 平均时间：O(n + k)（当数据均匀分布时，每个桶内 O(1) 个元素）
• 最坏时间：O(n²)（所有元素落入同一个桶）
• 空间：O(n + k)
• 稳定性取决于桶内排序是否稳定

21.10 基数排序（Radix Sort）

基数排序按位排序，从最低位（LSD）或最高位（MSD）开始，每一位用稳定的排序（如计数排序）来排。

def radix_sort(arr):
    """基数排序（LSD，最低位优先）"""
    if not arr:
        return arr
    
    max_val = max(arr)
    exp = 1  # 当前处理的位：1, 10, 100, ...
    
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr


def counting_sort_by_digit(arr, exp):
    """按某一位做计数排序"""
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # 0-9
    
    for x in arr:
        digit = (x // exp) % 10
        count[digit] += 1
    
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        count[digit] -= 1
        output[count[digit]] = arr[i]
    
    for i in range(n):
        arr[i] = output[i]

分析：

• 时间：O(d·(n+k))，d 是最大位数，k 是基数（这里是 10）
• 空间：O(n + k)
• 稳定

基数排序适合：位数固定的整数（如电话号码、身份证号）。当 d 是常数时，时间就是 O(n)。

Level 2 · 深入理解

21.11 TimSort：Python 和 Java 的选择

TimSort 是 Tim Peters 在 2002 年为 CPython 设计的排序算法。Python 的 list.sort() 和 sorted() 底层都是 TimSort，Java 的 Arrays.sort() 对对象数组也用 TimSort。它结合了归并排序的稳定性和插入排序对小数组/近乎有序数据的高效。

核心思想：利用已有的有序段

现实世界的数据很少是完全随机的。一个日志文件可能按时间大致有序；一个用户列表可能按注册时间大致有序。TimSort 的核心洞察是：先识别数据中已有的有序段（run），再用归并排序把它们合并起来。

TimSort 的执行流程

第一步：识别 run

从左到右扫描数组，找出自然的升序或降序片段。如果是降序，反转为升序。

def find_run(arr, lo, hi):
    """找到从 lo 开始的自然有序段"""
    if lo + 1 > hi:
        return lo + 1
    
    run_hi = lo + 1
    if arr[run_hi] < arr[lo]:
        # 严格递减
        while run_hi <= hi and arr[run_hi] < arr[run_hi - 1]:
            run_hi += 1
        # 反转为递增
        reverse(arr, lo, run_hi - 1)
    else:
        # 非递减
        while run_hi <= hi and arr[run_hi] >= arr[run_hi - 1]:
            run_hi += 1
    
    return run_hi

第二步：确保最小 run 长度（minrun）

如果自然 run 太短（短于 minrun），用插入排序把它扩展到 minrun 长度。minrun 通常是 32~64 之间的值，由数组总长度决定。

def compute_minrun(n):
    """计算 minrun：取 n 的前 6 位，如果剩余位有 1 则加 1"""
    r = 0
    while n >= 64:
        r |= n & 1
        n >>= 1
    return n + r

这个公式确保 n/minrun 要么是 2 的幂，要么略小于 2 的幂——这使得最后的合并阶段最高效。

第三步：合并 run

用一个栈来管理 run。每次发现新的 run 就压栈，然后检查栈顶的几个 run 是否满足合并条件。Tim Peters 定义了一个不变量来保证合并的效率：

对于栈顶三个 run 的长度 A, B, C：

• C > A + B
• B > A

如果违反了这个不变量，就合并较小的相邻 run。

第四步：galloping mode（加速合并）

在合并两个 run 时，如果发现一侧连续"赢"了很多次（比如左边 run 的元素连续比右边小），说明还有更多连续元素也会"赢"。此时切换到二分查找模式（galloping），一次性找到这一侧连续"赢"的范围，然后批量拷贝。

def gallop_left(key, arr, lo, hi):
    """在 arr[lo:hi] 中找到 key 应该插入的位置（偏左）
    使用 galloping: 先指数跳跃，再二分查找"""
    last_ofs = 0
    ofs = 1
    
    while ofs < hi - lo and arr[lo + ofs] < key:
        last_ofs = ofs
        ofs = (ofs << 1) + 1  # 指数增长: 1, 3, 7, 15, ...
    
    ofs = min(ofs, hi - lo)
    
    # 在 [last_ofs, ofs) 之间二分查找
    last_ofs += lo
    ofs += lo
    while last_ofs < ofs:
        mid = last_ofs + (ofs - last_ofs) // 2
        if arr[mid] < key:
            last_ofs = mid + 1
        else:
            ofs = mid
    
    return ofs

如果 galloping 没有带来足够收益（连续"赢"的次数低于阈值），会退回到逐元素比较。

TimSort 的时间复杂度

• 最好情况：O(n)——数据已完全有序，识别一个 run 后就结束
• 平均情况：O(n log n)
• 最坏情况：O(n log n)
• 空间：O(n)——合并需要临时数组
• 稳定

TimSort 的魔力在于它对实际数据的表现：现实数据中的有序段被直接利用，而不是被打散重排。

21.12 快排的三路分区（Dutch National Flag）

标准快排在面对大量重复元素时会退化。例如排序 100 万个元素，其中 99% 都是相同值，Lomuto 分区会把所有相等元素放到一侧，递归严重不平衡。

三路分区把数组分成三部分：小于 pivot、等于 pivot、大于 pivot。等于 pivot 的部分不再参与递归。

def quicksort_3way(arr, lo=0, hi=None):
    """三路快排（Dutch National Flag）"""
    if hi is None:
        hi = len(arr) - 1
    if lo >= hi:
        return
    
    # 三路分区
    pivot = arr[lo]
    lt = lo      # arr[lo..lt-1] < pivot
    gt = hi      # arr[gt+1..hi] > pivot
    i = lo + 1   # arr[lt..i-1] == 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[gt], arr[i] = arr[i], arr[gt]
            gt -= 1
            # 注意：i 不加 1，因为换过来的元素还没看过
        else:
            i += 1
    
    # arr[lt..gt] 都等于 pivot，不需要再排
    quicksort_3way(arr, lo, lt - 1)
    quicksort_3way(arr, gt + 1, hi)

这个算法就是 Dijkstra 著名的"荷兰国旗问题"（Dutch National Flag Problem）——他在 1976 年提出这个问题时，荷兰国旗有红白蓝三色，正好对应三路分区的三个区域。

21.13 为什么快排实际中最快

从渐近复杂度看，归并排序和堆排序都是 O(n log n)，而快排最坏情况还是 O(n²)。但实际中快排通常最快，原因如下：

1. 缓存友好（Cache Locality）

快排的 partition 阶段是顺序扫描数组，对 CPU 缓存极其友好。归并排序需要在两个数组间跳转合并；堆排序的父子节点跳跃访问破坏了空间局部性。

现代 CPU 的 L1/L2/L3 缓存命中率对性能影响巨大。快排的顺序访问模式使得缓存未命中（cache miss）很少。

2. 常数因子小

快排的内循环非常紧凑：一次比较 + 一次指针移动。归并排序的合并阶段需要额外数组和拷贝操作。

3. 原地排序

快排只需 O(log n) 的栈空间，而归并排序需要 O(n) 的额外空间。少的内存分配 = 少的系统调用 = 更快。

4. 尾递归优化

快排可以对较长的子数组做尾递归优化，保证栈深度不超过 O(log n)：

def quicksort_tail_optimized(arr, lo, hi):
    """尾递归优化：总是先递归短的子数组"""
    while lo < hi:
        pivot_idx = partition_lomuto(arr, lo, hi)
        # 递归较短的一半，循环处理较长的一半
        if pivot_idx - lo < hi - pivot_idx:
            quicksort_tail_optimized(arr, lo, pivot_idx - 1)
            lo = pivot_idx + 1
        else:
            quicksort_tail_optimized(arr, pivot_idx + 1, hi)
            hi = pivot_idx - 1

21.14 外部排序（External Sort）

当数据量超过内存容量时（比如 100GB 的数据，但只有 4GB 内存），需要外部排序。经典做法是多路归并排序：

第一阶段：生成有序段（sorted run）

1. 把数据分成能装入内存的块（比如每块 4GB）
2. 每块在内存中用快排/TimSort 排好，写回磁盘成为一个有序文件

第二阶段：多路归并

1. 如果有 k 个有序文件，维护一个大小为 k 的最小堆
2. 每次从堆中取最小值写入输出文件
3. 从该最小值所在的文件中读取下一个元素放入堆

import heapq

def external_merge_sort(sorted_files, output_file):
    """多路归并：合并 k 个已排序的文件"""
    # 打开所有文件
    file_handles = [open(f) for f in sorted_files]
    
    # 用堆进行 k 路归并
    heap = []
    for i, fh in enumerate(file_handles):
        line = fh.readline()
        if line:
            heapq.heappush(heap, (int(line.strip()), i))
    
    with open(output_file, 'w') as out:
        while heap:
            val, file_idx = heapq.heappop(heap)
            out.write(f"{val}\n")
            
            next_line = file_handles[file_idx].readline()
            if next_line:
                heapq.heappush(heap, (int(next_line.strip()), file_idx))
    
    for fh in file_handles:
        fh.close()

优化技巧：

• 用替换选择（replacement selection）生成初始有序段：平均能生成 2 倍内存大小的有序段
• 读写缓冲区：减少磁盘 I/O 次数
• 多路归并的路数要平衡：路数太多每路缓冲区太小，路数太少归并轮次太多

外部排序的关键指标不是比较次数，而是磁盘 I/O 次数。现代外排还会考虑 SSD 的随机读写特性。

Level 3 · 理论与历史

21.15 比较排序的下界 O(n log n) 证明

定理：任何基于比较的排序算法，在最坏情况下至少需要 Ω(n log n) 次比较。

证明（决策树模型）：

把排序算法抽象为一棵二叉决策树：

• 每个内部节点是一次比较 a[i] vs a[j]
• 左子树对应"小于"的情况，右子树对应"大于等于"
• 每个叶子节点对应一种排列结果

n 个元素有 n! 种可能的排列，所以决策树至少有 n! 个叶子。一棵高度为 h 的二叉树最多有 2^h 个叶子，因此：

2^h >= n!
h >= log₂(n!)

由斯特林近似 n! ≈ (n/e)^n：

h >= log₂((n/e)^n) = n·log₂(n/e) = n·log₂n - n·log₂e
  = Ω(n log n)

信息论解释：

排序本质上是确定 n! 种排列中的哪一种。每次比较提供 1 bit 的信息。要区分 n! 种可能性，至少需要 log₂(n!) = Ω(n log n) bits 的信息。

这就是为什么计数排序和基数排序能突破这个下界——它们不是纯粹基于比较的，而是利用了元素的数值信息（额外信息来源）。

21.16 排序算法的发明历史

排序算法的历史几乎就是计算机科学的发展史：

Tony Hoare 发明快排时只有 25 岁。他后来回忆："我当时在做俄英翻译的机器查找，需要把单词排序。我一开始想用冒泡排序，但太慢了。我思考了一段时间，发现了 partition 的想法。"

Tim Peters 在 CPython 邮件列表中提交 TimSort 的邮件标题是 "[Python-Dev] Sorting"，附带了一份 27 页的设计文档（listsort.txt），详细解释了每个设计决策。这份文档至今仍是 CPython 源码树的一部分。

21.17 稳定性的严格定义和重要性

定义：如果排序前 a[i] == a[j] 且 i < j，排序后 a[i] 仍然在 a[j] 前面，则该排序算法是稳定的。

换句话说：相等的元素保持它们原来的相对顺序。

为什么稳定性重要？

1. 多级排序：先按姓名排序，再按年龄排序。如果排序稳定，同龄的人仍按姓名有序。

students = [
    ("Alice", 20), ("Bob", 22), ("Charlie", 20), ("Diana", 22)
]

# 先按名字排
students.sort(key=lambda x: x[0])
# [("Alice", 20), ("Bob", 22), ("Charlie", 20), ("Diana", 22)]

# 再按年龄排（稳定排序）
students.sort(key=lambda x: x[1])
# [("Alice", 20), ("Charlie", 20), ("Bob", 22), ("Diana", 22)]
# 同龄的 Alice 仍在 Charlie 前面，Bob 仍在 Diana 前面

2. 数据库查询：SQL 的 ORDER BY 多字段排序依赖稳定性。

3. UI 排序：用户点击表头排序时，期望相同值的行保持之前的顺序。

4. 正确性：某些应用中，相等元素的相对顺序有语义含义（如时间戳相同的事件按到达顺序排列）。

Python 的 sort 保证稳定——这是语言规范的一部分，不仅仅是实现细节。

21.18 introsort：C++ std::sort 的混合策略

introsort（内省排序）是 David Musser 1997 年提出的混合排序算法，是 C++ 标准库 std::sort 的典型实现。它结合了三种算法的优势：

1. 快排：平均情况最快
2. 堆排序：保证最坏情况 O(n log n)
3. 插入排序：小数组上最快

策略：

• 开始用快排
• 如果递归深度超过 2·log₂(n)，说明可能退化到 O(n²)，切换到堆排序
• 当子数组大小小于阈值（通常 16），切换到插入排序

import math

def introsort(arr):
    """introsort：快排 + 堆排 + 插入排序的混合"""
    max_depth = 2 * int(math.log2(len(arr))) if arr else 0
    _introsort_helper(arr, 0, len(arr) - 1, max_depth)
    return arr


def _introsort_helper(arr, lo, hi, depth_limit):
    SIZE_THRESHOLD = 16
    
    while hi - lo + 1 > SIZE_THRESHOLD:
        if depth_limit == 0:
            # 递归太深，切换到堆排序
            heap_sort_range(arr, lo, hi)
            return
        
        depth_limit -= 1
        # 三数取中选 pivot
        mid = (lo + hi) // 2
        pivot_idx = median_of_three(arr, lo, mid, hi)
        arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
        
        p = partition_lomuto(arr, lo, hi)
        _introsort_helper(arr, p + 1, hi, depth_limit)
        hi = p - 1  # 尾递归优化
    
    # 小数组用插入排序
    insertion_sort_range(arr, lo, hi)


def median_of_three(arr, a, b, c):
    """三数取中：选 arr[a], arr[b], arr[c] 的中位数的下标"""
    if arr[a] > arr[b]:
        a, b = b, a
    if arr[b] > arr[c]:
        b, c = c, b
    if arr[a] > arr[b]:
        a, b = b, a
    return b

introsort 巧妙地结合了三种算法的优势：

• 绝大多数情况走快排路径，享受快排的缓存优势和低常数
• 万一遇到病态输入导致递归过深，自动切换到堆排序，保证 O(n log n)
• 小子数组用插入排序，避免递归开销

因此 introsort 是：O(n log n) 最坏、O(n log n) 平均、原地、不稳定。

Level 4 · 实战与面试

21.19 Python 排序 API 详解

sort() vs sorted()

# list.sort() — 原地排序，返回 None，只能用于列表
nums = [3, 1, 4, 1, 5]
nums.sort()
# nums = [1, 1, 3, 4, 5]

# sorted() — 返回新列表，可以用于任何可迭代对象
result = sorted((3, 1, 4, 1, 5))  # 元组也行
# result = [1, 1, 3, 4, 5]

# sorted 可以接受生成器、字典视图等
sorted({"b": 2, "a": 1}.items(), key=lambda x: x[1])
# [('a', 1), ('b', 2)]

关键区别：

• sort() 是原地排序，不消耗额外 O(n) 内存（除了 TimSort 合并用的临时空间）
• sorted() 总是创建新列表
• sort() 只有 list 类型有；sorted() 是内置函数，接受任何 iterable

key 参数

# lambda
words = ["banana", "apple", "cherry"]
words.sort(key=lambda w: len(w))
# ['apple', 'banana', 'cherry']

# operator.itemgetter — 比 lambda 快（C 实现）
from operator import itemgetter
students = [("Alice", 85), ("Bob", 92), ("Charlie", 78)]
students.sort(key=itemgetter(1))  # 按成绩排
# [('Charlie', 78), ('Alice', 85), ('Bob', 92)]

# operator.attrgetter — 按属性排
from operator import attrgetter
from dataclasses import dataclass

@dataclass
class Student:
    name: str
    gpa: float

students = [Student("Alice", 3.8), Student("Bob", 3.9)]
students.sort(key=attrgetter('gpa'))

# 多级排序：先按 GPA 降序，再按名字升序
students.sort(key=lambda s: (-s.gpa, s.name))

functools.cmp_to_key

Python 3 移除了 sort 的 cmp 参数，但有些比较逻辑用 key 不好表达（如自定义比较函数）。此时用 cmp_to_key：

from functools import cmp_to_key

def compare_versions(v1, v2):
    """比较版本号：'1.2.3' vs '1.2.10'"""
    parts1 = list(map(int, v1.split('.')))
    parts2 = list(map(int, v2.split('.')))
    for p1, p2 in zip(parts1, parts2):
        if p1 < p2:
            return -1
        elif p1 > p2:
            return 1
    return len(parts1) - len(parts2)

versions = ["1.2.3", "1.2.10", "1.1.0", "2.0.0"]
versions.sort(key=cmp_to_key(compare_versions))
# ['1.1.0', '1.2.3', '1.2.10', '2.0.0']

经典面试应用——最大数拼接（LeetCode 179）：

def largest_number(nums):
    """给定整数数组，拼接成最大的数"""
    strs = [str(n) for n in nums]
    
    def compare(a, b):
        if a + b > b + a:
            return -1
        elif a + b < b + a:
            return 1
        return 0
    
    strs.sort(key=cmp_to_key(compare))
    result = ''.join(strs)
    return '0' if result[0] == '0' else result

21.20 面试高频排序题

题 1：合并区间（LeetCode 56）

给定若干区间 [start, end]，合并所有重叠的区间。

def merge_intervals(intervals):
    """
    排序后一次遍历合并
    时间 O(n log n)，空间 O(n)
    """
    if not intervals:
        return []
    
    # 按起点排序
    intervals.sort(key=lambda x: x[0])
    
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            # 重叠，合并（取较大的终点）
            merged[-1] = [merged[-1][0], max(merged[-1][1], end)]
        else:
            merged.append([start, end])
    
    return merged

# 测试
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1, 6], [8, 10], [15, 18]]

思路： 排序后，重叠区间一定相邻。所以排序+线性扫描就能解决。

题 2：最大间距（LeetCode 164）

给定无序数组，找到排序后相邻元素的最大差值。要求 O(n) 时间和空间。

def maximum_gap(nums):
    """
    桶排序思想：最大间距一定 >= ceil((max-min)/(n-1))
    所以桶大小设为 floor((max-min)/(n-1))，答案一定在桶间（不在桶内）
    """
    n = len(nums)
    if n < 2:
        return 0
    
    min_val, max_val = min(nums), max(nums)
    if min_val == max_val:
        return 0
    
    # 桶大小和桶数量
    bucket_size = max(1, (max_val - min_val) // (n - 1))
    bucket_count = (max_val - min_val) // bucket_size + 1
    
    # 每个桶只记录最大值和最小值
    buckets_min = [float('inf')] * bucket_count
    buckets_max = [float('-inf')] * bucket_count
    
    for num in nums:
        idx = (num - min_val) // bucket_size
        buckets_min[idx] = min(buckets_min[idx], num)
        buckets_max[idx] = max(buckets_max[idx], num)
    
    # 最大间距 = 某个桶的 min - 前一个非空桶的 max
    max_gap = 0
    prev_max = buckets_max[0]
    for i in range(1, bucket_count):
        if buckets_min[i] == float('inf'):
            continue  # 空桶跳过
        max_gap = max(max_gap, buckets_min[i] - prev_max)
        prev_max = buckets_max[i]
    
    return max_gap

关键洞察： 鸽巢原理——如果 n 个数均匀分布在 [min, max]，相邻差值的平均值是 (max-min)/(n-1)。最大间距一定 >= 这个平均值。把桶大小设为这个平均值，最大间距不会出现在桶内部，只会出现在相邻桶之间。

题 3：颜色分类（LeetCode 75，荷兰国旗问题）

数组只有 0、1、2 三种值，原地排序，一次遍历。

def sort_colors(nums):
    """
    荷兰国旗问题：三路分区
    lo: 0 的右边界
    hi: 2 的左边界
    i: 当前指针
    """
    lo, i, hi = 0, 0, len(nums) - 1
    
    while i <= hi:
        if nums[i] == 0:
            nums[lo], nums[i] = nums[i], nums[lo]
            lo += 1
            i += 1
        elif nums[i] == 2:
            nums[hi], nums[i] = nums[i], nums[hi]
            hi -= 1
            # i 不动，因为换过来的值还没检查
        else:  # nums[i] == 1
            i += 1

# 测试
arr = [2, 0, 2, 1, 1, 0]
sort_colors(arr)
print(arr)  # [0, 0, 1, 1, 2, 2]

这就是 Dijkstra 的荷兰国旗算法在面试中的直接应用。注意和快排的三路分区是同一个思想。

21.21 什么时候用什么排序

实际编程中，排序的选择取决于：

Python 实际建议：

• 99% 的情况直接用 sorted() 或 .sort()——它们是 TimSort，已经够好了
• 如果元素是小范围整数且性能关键，手写计数排序
• 如果数据量超过内存，用外部排序（或用数据库/Spark 等工具）

21.22 排序算法的并行化潜力

不同排序算法的并行化潜力差异很大：

归并排序——天然适合并行

分治结构意味着两半可以独立排序，合并阶段也可以部分并行化：

from concurrent.futures import ThreadPoolExecutor

def parallel_merge_sort(arr, depth=0, max_depth=3):
    """并行归并排序（用线程池）"""
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    
    if depth < max_depth:
        with ThreadPoolExecutor(max_workers=2) as executor:
            left_future = executor.submit(parallel_merge_sort, arr[:mid], depth+1, max_depth)
            right_future = executor.submit(parallel_merge_sort, arr[mid:], depth+1, max_depth)
            left = left_future.result()
            right = right_future.result()
    else:
        left = parallel_merge_sort(arr[:mid], depth+1, max_depth)
        right = parallel_merge_sort(arr[mid:], depth+1, max_depth)
    
    return merge(left, right)

注意：Python 的 GIL 限制了多线程的并行度。真正的并行排序建议用多进程或 C 扩展。

快排——也可以并行

partition 后两半独立，但 partition 本身是串行的。快排的并行效率取决于 partition 的平衡度。

排序网络（Sorting Networks）——最适合硬件并行

排序网络是一种固定的比较-交换序列，所有比较操作在编译时确定，非常适合 GPU 和 FPGA 上的并行实现。Batcher 的 bitonic merge sort 是经典的并行排序网络。

实际中的并行排序：

• C++ 的 std::execution::par 策略
• Java 的 Arrays.parallelSort()——基于并行归并排序
• Python 中用 multiprocessing 或 NumPy（底层 C 并行）
• 大数据场景用 MapReduce/Spark 的分布式排序

本章小结

排序是计算机科学的"试金石"——它看似简单，却涉及算法设计的核心思想：分治、递归、随机化、摊还分析、缓存优化、并行化。

关键要点：

1. 比较排序有 O(n log n) 的理论下界，但非比较排序可以在特定条件下达到 O(n)
2. 快排实际最快，因为缓存友好和常数小——但需要随机化 pivot 避免最坏情况
3. TimSort 是实际最优的通用排序算法，利用数据中的有序段，是 Python/Java 的默认选择
4. introsort 是 C++ 的选择：快排的速度 + 堆排的最坏保证 + 插入排序的小数组效率
5. 稳定性是实际需求：多级排序、数据库查询、UI 排序都需要稳定性
6. 选择合适的算法取决于数据特征：大小、值域、分布、是否需要稳定、内存限制

下一章我们将讨论搜索与匹配算法——排序的"近亲"。很多搜索问题的第一步就是排序。