排序与选择算法

#数据结构 · #算法 · #排序 · #快速排序 · #归并排序 · #堆排序 · #Timsort

排序算法是计算机科学中最经典的问题之一。本文从算法原理到各语言实现，涵盖：冒泡/插入/选择、快速排序（含优化）、堆排序、归并排序、快速选择，以及混合排序策略（Timsort/Pattern-defeating quicksort）。

1. 基本排序算法

1.1 冒泡排序（Bubble Sort）

// O(n²) — 教学用，生产环境永远不要用
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
}

最好	平均	最坏	空间	稳定
O(n)	O(n²)	O(n²)	O(1)	✅

1.2 插入排序（Insertion Sort）

// O(n²) — 但对小数组和"几乎有序"的数组非常快
void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i], j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

最好	平均	最坏	空间	稳定
O(n)	O(n²)	O(n²)	O(1)	✅

为什么快排/归并排还要用它：当 n < 阈值（通常 16~32），插入排序的实际运行速度超过 O(n log n) 算法——因为常数因子极小，缓存友好。

1.3 选择排序（Selection Sort）

最好	平均	最坏	空间	稳定
O(n²)	O(n²)	O(n²)	O(1)	❌

交换次数最少（n-1 次），适合写操作很昂贵的场景。

2. 快速排序（Quick Sort）— 实践中最快

2.1 基本算法

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
        if (arr[j] <= pivot)
            swap(arr[++i], arr[j]);
    swap(arr[i+1], arr[high]);
    return i + 1;
}

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quicksort(arr, low, pi - 1);
        quicksort(arr, pi + 1, high);
    }
}

最好	平均	最坏	空间	稳定
O(n log n)	O(n log n)	O(n²)	O(log n)	❌

平均复杂度 O(n log n) 的完整推导：

设 T(n) 为对 n 个元素的数组进行快速排序的平均比较次数。

pivot 的选择均匀随机，即任意一个元素作为 pivot 的概率 = 1/n。

分区操作 partition 需要 n-1 次比较（每个元素都和 pivot 比较一次）。

分区完成后，pivot 落在位置 k（0 ≤ k ≤ n-1），左子数组 k 个元素，右子数组 n-1-k 个元素。

递推关系:
  T(n) = (n-1) + (1/n) × Σ_{k=0}^{n-1} [T(k) + T(n-1-k)]

其中 (n-1) 是分区比较次数，括号内是当 pivot 落在位置 k 时的期望递归代价。

由于 T(k) 和 T(n-1-k) 在 k 从 0 到 n-1 遍历时各出现两次，可以合并:

  T(n) = (n-1) + (2/n) × Σ_{k=0}^{n-1} T(k)

两边乘以 n:
  n × T(n) = n(n-1) + 2 × Σ_{k=0}^{n-1} T(k)    ... (1)

对于 n-1:
  (n-1) × T(n-1) = (n-1)(n-2) + 2 × Σ_{k=0}^{n-2} T(k)    ... (2)

(1) - (2):
  n×T(n) - (n-1)×T(n-1) = n(n-1) - (n-1)(n-2) + 2×T(n-1)
                         = (n-1)(n - (n-2)) + 2×T(n-1)
                         = 2(n-1) + 2×T(n-1)

  n×T(n) = 2(n-1) + 2×T(n-1) + (n-1)T(n-1)
          = 2(n-1) + (n+1)×T(n-1)

  T(n) = 2(n-1)/n + (n+1)/n × T(n-1)

两边除以 n+1:
  T(n)/(n+1) = 2(n-1)/(n(n+1)) + T(n-1)/n
             ≈ 2/(n+1) + T(n-1)/n    (当 n 较大时)

展开递推:
  T(n)/(n+1) ≈ 2 × Σ_{i=1}^{n} 1/(i+1) + T(0)/1
             ≈ 2 × (H_{n+1} - 1)        (H_{n+1} 是调和数)

  H_{n+1} ≈ ln(n+1) + γ  (γ ≈ 0.577 欧拉常数)
  → T(n)/(n+1) ≈ 2 × (ln(n+1) + γ - 1)
  → T(n) ≈ 2×(n+1)×ln(n+1) ≈ 1.39 × n × log₂(n)

结论: 平均比较次数 ≈ 1.39 n log₂ n，常数 1.39 来自"每个 element 平均和约 2 ln 2 ≈ 1.39 个 pivot 比较"。

所以快排的"O(n log n)"不是紧的——它比归并排序做更多的比较。
但快排在实际中更快，原因:
  1. pivot 比较操作在 cache 内（分区在原地进行）
  2. 递归深度 O(log n)，栈开销小
  3. 常数 1.39 被优越的 cache 局部性抵消

2.2 三大优化（生产级快排必备）

优化 1：三数取中法选 pivot

// 避免最坏 O(n²)：取 low、mid、high 的中位数作为 pivot
int median_of_three(int arr[], int low, int high) {
    int mid = (low + high) / 2;
    if (arr[mid] < arr[low])  swap(arr[low], arr[mid]);
    if (arr[high] < arr[low]) swap(arr[low], arr[high]);
    if (arr[high] < arr[mid]) swap(arr[mid], arr[high]);
    swap(arr[mid], arr[high]);  // pivot 放末尾
    return arr[high];
}

优化 2：小数组切插入排序

if (high - low < 16) {
    insertion_sort(arr + low, high - low + 1);
    return;
}

为什么阈值是 16~32？——交叉点的量化分析

快排和插入排序的实际运行时间（不只看 O 记号）:

  快排单次递归的代价:
    T_qs(n) = C_qs × n × log₂(n)
    其中 C_qs 包含: 函数调用开销、分区循环、递归栈帧
    实测 C_qs ≈ 8-12 ns/比较（含分支预测失败、cache miss）

  插入排序的代价:
    T_ins(n) = C_ins × n²/2
    其中 C_ins 包含: 比较 + 移动（相邻元素，cache 极好）
    实测 C_ins ≈ 2-3 ns/比较（几乎全部 L1 hit）

  交叉点: T_qs(n) = T_ins(n)
    C_qs × n × log₂(n) = C_ins × n²/2
    → n = 2 × C_qs × log₂(n) / C_ins

    代入 C_qs=10, C_ins=2.5:
    → n ≈ 2 × 10 × log₂(n) / 2.5 = 8 × log₂(n)
    → n=16: 8 × 4 = 32 > 16 → 插入排序更快 ✅
    → n=32: 8 × 5 = 40 > 32 → 插入排序更快 ✅
    → n=64: 8 × 6 = 48 < 64 → 快排更快 ✅

  所以交叉点在 n ≈ 32~48 之间。

  但实际选 16 而非 48 的原因:
    1. 递归到 n=16 时，数据已经"大致有序"（快排已经做了粗分区）
       → 插入排序对"几乎有序"的数据接近 O(n)
    2. n=16 时 16 个 int = 128B = 2 个 cache line
       → 完全在 L1 cache 内操作
    3. 选太大的阈值会让插入排序的 O(n²) 部分变得显著

各语言/库的实际阈值:
  Go pdqsort:     24
  C++ Introsort:  16 (libstdc++), 32 (MSVC)
  Java DualPivot: 47
  Rust pdqsort:   20
  Python Timsort: 32 (minrun)

优化 3：三路划分（荷兰国旗问题）

// 处理大量重复元素，分成 <pivot | ==pivot | >pivot
// 避免传统快排在重复元素数组上退化到 O(n²)
void quicksort_3way(int arr[], int low, int high) {
    if (low >= high) return;
    int lt = low, gt = high, i = low + 1;
    int pivot = arr[low];
    while (i <= gt) {
        if (arr[i] < pivot)      swap(arr[lt++], arr[i++]);
        else if (arr[i] > pivot) swap(arr[i], arr[gt--]);
        else                     i++;
    }
    quicksort_3way(arr, low, lt - 1);
    quicksort_3way(arr, gt + 1, high);
}

2.3 各语言快排实现

语言	算法	备注
Go	pdqsort (1.19+)	Pattern-defeating quicksort
C++	Introsort	快排 + 堆排兜底
Java	Dual-Pivot Quicksort	双 pivot 三分区
Rust	pdqsort	同 Go
Python	Timsort	归并排变体

2.4 Introsort (C++ STL)

Introsort 是 David Musser 于 1997 年提出的混合排序算法，至今仍是 C++ STL 标准库（libstdc++/libc++）的默认排序实现。

Introsort 的完整工作流程：

mermaid

flowchart TD
    START["Introsort(arr, depth_limit)"] --> SMALL{"len(arr) < 16?"}
    SMALL -->|"是"| INS["插入排序"]
    SMALL -->|"否"| DEPTH{"depth_limit == 0?"}
    DEPTH -->|"是"| HEAP["切换到堆排序<br/>heapsort(arr)"]
    DEPTH -->|"否"| PIVOT["三数取中选 pivot"]
    PIVOT --> PART["Hoare 分区<br/>arr = [≤pivot] | [≥pivot]"]
    PART --> RECURSE
    subgraph RECURSE["递归处理左右子数组"]
        L["Introsort(left, depth_limit-1)"]
        R["Introsort(right, depth_limit-1)"]
    end
    style HEAP fill:#FF9800,color:#fff
    style INS fill:#4CAF50,color:#fff
    style START fill:#607D8B,color:#fff

三个核心机制：

Pivot 选择 — 三数取中：取 arr[low]、arr[mid]、arr[high] 的中位数作为 pivot，避免有序/逆序输入时固定选首尾导致 O(n²)。
分区 — Hoare 双边扫描：从两端向中间扫描。为什么不用 Lomuto？ Lomuto 单向扫描对相同值数组要做 n 次冗余 swap；Hoare 双向扫描只在真正需要交叉时才交换——相同值数组 0 次 swap。生产环境（std::sort、pdqsort）全用 Hoare。

Hoare vs Lomuto 分区对比：

// Lomuto 分区（单向扫描）：pivot 固定在末尾
int lomuto_partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++)
        if (arr[j] <= pivot)
            swap(arr[++i], arr[j]);  // 每次遇到 ≤ pivot 就交换
    swap(arr[i+1], arr[high]);
    return i + 1;
}
// 问题：每个 ≤ pivot 的元素都要 swap — 等价元素也要 swap
// 一个全是相同值的数组 → n 次 swap → O(n) 次操作都是冗余的！

// Hoare 分区（双边扫描）：pivot 取中间值
int hoare_partition(int arr[], int low, int high) {
    int pivot = arr[(low + high) / 2];
    int i = low - 1, j = high + 1;
    while (1) {
        do { i++; } while (arr[i] < pivot);   // 左边找 ≥ pivot
        do { j--; } while (arr[j] > pivot);   // 右边找 ≤ pivot
        if (i >= j) return j;
        swap(arr[i], arr[j]);  // 只在真正需要交换时才换
    }
}
// 优势：只在左右各找到一个"放错位置"的元素时才 swap
// 相同值数组 → 0 次 swap → 快速收敛到中间

维度	Lomuto	Hoare
扫描方向	单向，固定 pivot 在末尾	双向，pivot 在中间
交换次数	每个 ≤pivot 元素都换（等价元素也换）	只换"放错位置"的元素对
相同值数组	O(n) 次交换	0 次交换 ✅
结果	pivot 在最终位置	左半 ≤ pivot，右半 ≥ pivot，pivot 可能不在最终位置
稳定性	❌	❌
使用场景	教学、易于理解	生产（C++ std::sort、Go pdqsort）

Introsort 和 pdqsort 都使用 Hoare 分区，因为真实数据中重复元素非常常见。

退路 — 堆排序兜底：初始化 depth_limit = 2×log₂(n)，每次递归 depth_limit--。当递归深度超过阈值时，说明 pivot 一直选得不好（可能遇到恶意构造的输入），立刻切到堆排序——堆排序保证 O(n log n) 最坏，且原地排序。

Introsort 的"够了"哲学：

快排绝大多数时候是最快的，但对手可以构造输入让它退化。Introsort 的方案不是让快排"更聪明地选 pivot"来预防退化，而是直接设一个安全线——超过深度就换堆排。简单粗暴，但有效。
代价：堆排序比快排慢（常数因子大），且跳转模式对 cache 不友好。如果一个输入反复触发堆排序兜底，性能反而不如一开始就用堆排。这正是 pdqsort 要修复的问题之一。

为什么历史地位重要：Introsort 是第一个被广泛采用的"混合排序"算法，证明了"不同算法在不同数据特征下各有优势→自适应切换"的思想是正确的。pdqsort 本质上是把这一思想推进到极致。

2.5 pdqsort (Go 1.19+, Rust)

Pattern-defeating quicksort — 目前最快的通用排序算法之一。

mermaid

flowchart TD
    START["pdqsort(arr)"] --> SMALL{"len(arr) < 24?"}
    SMALL -->|"是"| INS["插入排序<br/>小数组最优"]
    SMALL -->|"否"| PIVOT["选 pivot<br/>三数取中/中中位数"]
    PIVOT --> PART["分区 partition"]
    PART --> CHECK{"坏分区？<br/>(极不平衡)"}
    CHECK -->|"是"| HEAP["切换到堆排序<br/>防 O(n²) 退化"]
    CHECK -->|"否"| DEPTH{"递归深度 > log₂(n)?"}
    DEPTH -->|"是"| HEAP
    DEPTH -->|"否"| RECURSE["递归处理左右子数组"]
    RECURSE -->|"子数组有序?"| PARTIAL{"检测到<br/>部分有序?"}
    PARTIAL -->|"是"| TIMSORT["切换到 Timsort<br/>利用有序性"]
    PARTIAL -->|"否"| PIVOT

    style HEAP fill:#FF9800,color:#fff
    style INS fill:#4CAF50,color:#fff
    style TIMSORT fill:#2196F3,color:#fff
    style START fill:#607D8B,color:#fff

pdqsort 对付敌手数据的四层防线：

层级	检测条件	应对策略
1. 坏分区（Bad Partition）	分区后一侧 < n/8	换 pivot 策略（中中位数）、标记为坏分区
2. 递归深度超限	深度 > log₂(n)	切换到堆排序（保证 O(n log n)）
3. 连续坏分区	连续出现坏分区	提前切换到堆排序
4. 检测到有序	子数组已经/接近有序	切换到插入排序或部分 Timsort 合并

与 Introsort 的关键区别：

特性	Introsort (C++)	pdqsort (Go/Rust)
退化检测	仅递归深度	深度 + 坏分区比例 + 有序检测
兜底策略	堆排序	堆排序 / 插入排序 / Timsort 风格合并
重复元素	传统二分	三路划分（荷兰国旗）自适应
部分有序	无感知	检测 natural runs 并利用
pivot 选择	三数取中	三数取中 → 伪中位数（九个样本）→ Tukey's ninther

为什么 Go 1.19 要从 Introsort 换到 pdqsort？

Go 1.18 及之前使用 Introsort，1.19 起使用 pdqsort。这不是简单的算法替换，而是在大量真实数据集上 benchmark 后的工程决策。

Introsort 的三大缺陷：

缺陷	表现	pdqsort 如何解决
对"几乎有序"数据性能差	Introsort 无视输入有序性，始终走快排→堆排分支；对一个已排好序的数组和随机数组耗时相同（都是 O(n log n)）	pdqsort 检测 natural runs（连续递增序列），发现有序段后跳过或做 cheap merge，对完全有序数组 → O(n)
重复元素退化	Introsort 使用传统二分分区，遇到全是相同值的数组，依然递归 O(n log n) 次	pdqsort 检测到大量相等元素后切换三分区（荷兰国旗），重复值数组 → O(n)
pivot 选择不鲁棒	Introsort 只用三数取中，遇到专门构造的"Killer Sequence"（三数取中每次都选到次小/次大值），频繁触发堆排序反而更慢	pdqsort 用四阶段 pivot 选择：三数取中 → 伪中位数（9个样本）→ Tukey's ninther → 中中位数。逐级升级策略只在必要时付出 cost

pdqsort 这个名字的由来：Pattern-Defeating = 检测并击破各类坏数据模式。它不是"比 Introsort 常数因子更快"，而是对各类输入自适应用最优策略。

Go 的 benchmark 数据（Go 1.19 release notes）：

text

对比 Go 1.18 Introsort vs Go 1.19 pdqsort:
  随机数据:     快 5-10%     (pivot 选择更优)
  有序数据:     快 10x       (natural run 检测 → 接近 O(n))
  重复数据:     快 5-10x     (三路划分 → O(n))
  几乎有序数据: 快 3-5x      (partial Timsort 合并)
  敌手数据:     快 10-30%    (多层防线提前拦截)

pdqsort 的"模式检测"具体怎么做的？

// 1. 分区后检查是否平衡
bool is_balanced = (left_len >= n/8) && (right_len >= n/8);
if (!is_balanced) bad_partitions++;

// 2. 连续坏分区数 ≥ 5 → 直接堆排序
if (bad_partitions >= 5) {
    heapsort(arr);
    return;
}

// 3. 检测 natural runs — 扫描相邻元素，找出已排好的连续段
//    一个"run"是一段递增序列 arr[i] <= arr[i+1] <= arr[i+2] ...
int run_len = 1;
for (int i = 1; i < n; i++) {
    if (arr[i-1] <= arr[i])
        run_len++;
    else {
        // run 结束，记录这段
        runs.push({start: i - run_len, len: run_len});
        run_len = 1;
    }
}
// 完全有序 → 只有 1 个 run（整个数组）→ O(n) 直接返回！
if (runs.size() == 1 && runs[0].len == n) return;

// 4. 检测 was_partitioned:
//    递归返回后，检查子数组的 min/max 是否都在 pivot 一侧
//    如果 min ≥ pivot 或 max ≤ pivot → 说明 pivot 选偏了 → 升级 pivot 策略

// 5. 对"几乎有序"的偏斜数组：不做快排分区，直接用 Timsort 风格归并
if (runs.size() > 0 && runs.size() < some_threshold) {
    // 将多个已排好的 run 两两归并
    // 类似 Timsort 的 merge_collapse，但只做 cheap merge：
    //   小 run 插入排序，中等 run 二分归并，大 run 再用快排
    partial_merge(runs);
    return;
}

Natural run 检测的"为什么能加速"：

输入: [1, 2, 3, 4, 5, 10, 9, 8, 7, 6, 11, 12, 13, 14, 15]

  Introsort: 无视结构 → 选 pivot → 分区 → 递归 → O(n log n)

  pdqsort 扫描:
    run 1: [1,2,3,4,5]   ← 递增, 长度 5
    run 2: [10,9,8,7,6]  ← 递减! (可以反转成递增)
    run 3: [11,12,13,14,15] ← 递增, 长度 5

  发现 3 个 run → 做归并而非快排 → 接近 O(n)

pdqsort 真正的洞察是：现实世界的数据从来不是均匀随机的。数据库导出、日志时间戳、排序后的 JSON 字段——这些"几乎有序""大量重复""部分偏斜"的数据才是常态。pdqsort 为常态优化，Introsort 为最坏情况优化——常态赢了。

3. 堆排序（Heap Sort）

3.1 堆数据结构

堆是一种完全二叉树，满足堆性质：

最大堆：每个节点 ≥ 其子节点，根节点是全局最大值
最小堆：每个节点 ≤ 其子节点，根节点是全局最小值

最大堆示例:                  数组存储(完全二叉树):
        100                  索引: 0   1   2   3   4   5   6   7   8
       /   \                 值: [100, 36, 19, 25, 17, 3, 7, 1, 2]
     36     19
    /  \   /  \              父子关系 (0-index):
   25  17 3    7              parent(i) = (i-1)/2
  /  \                        left(i)   = 2*i+1
 1    2                       right(i)  = 2*i+2

堆的数组存储优势：不需要指针，利用完全二叉树的索引关系 O(1) 访问父子节点。这是堆能做到 O(1) 额外空间的关键。

3.2 建堆（Build Heap）— O(n) 不是 O(n log n)！

mermaid

flowchart TD
    A["无序数组: [4,10,3,5,1]"] --> B["从最后一个非叶节点开始<br/>i = n/2 - 1 = 1 (值为10)"]
    B --> C["heapify(10): 与子节点5,1比较<br/>10最大, 不变"]
    C --> D["heapify(4): 与子节点10,3比较<br/>10>4, 交换"]
    D --> E["递归heapify(4): 与5,1比较<br/>5>4, 交换"]
    E --> F["✅ 最大堆: [10,5,3,4,1]"]

    style A fill:#607D8B,color:#fff
    style F fill:#4CAF50,color:#fff

关键：为什么建堆是 O(n) 而不是 O(n log n)？

第 0 层 (根) 节点数 = n/2^(h+1) ≈ 1,   heapify 代价 = h
第 1 层      节点数 = n/4     ≈ n/4, heapify 代价 = h-1
第 2 层      节点数 = n/8     ≈ n/8, heapify 代价 = h-2
...

总代价 = Σ (n/2^(k+1)) × k = n × Σ k/2^(k+1) < 2n → O(n)

直觉：底层节点很多但 heapify 代价极小（不需要下沉），顶层节点少代价大。加权后是 O(n)。

// heapify: 维护堆性质 O(log n)（单次）
void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i + 1, r = 2*i + 2;

    // 找 i、左子、右子中最大的
    if (l < n && arr[l] > arr[largest]) largest = l;
    if (r < n && arr[r] > arr[largest]) largest = r;

    // 如果最大不是 i，交换并递归向下修复
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // 继续向下调整
    }
}

// 建堆 O(n)
void build_heap(int arr[], int n) {
    // 从最后一个非叶节点开始，自底向上
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

3.3 排序过程

mermaid

sequenceDiagram
    participant H as 堆
    participant A as 已排序区(数组末尾)
    participant P as 未排序区(数组前部)

    Note over H,P: 初始: 建好最大堆 [10,5,3,4,1]

    rect rgb(240, 248, 255)
        H->>H: swap(堆顶10, 末尾1) → [1,5,3,4,|10]
        H->>H: heapify(n=4, i=0) → [5,4,3,1,|10]
        Note over A,P: 10 已就位
    end

    rect rgb(255, 248, 240)
        H->>H: swap(堆顶5, 末尾1) → [1,4,3,|5,10]
        H->>H: heapify(n=3, i=0) → [4,1,3,|5,10]
        Note over A,P: 5 已就位
    end

    rect rgb(240, 255, 240)
        H->>H: swap(堆顶4, 末尾3) → [3,1,|4,5,10]
        H->>H: heapify(n=2, i=0) → [3,1,|4,5,10]
    end

    rect rgb(255, 240, 255)
        H->>H: swap(堆顶3, 末尾1) → [1,|3,4,5,10]
        Note over A: ✅ 排序完成
    end

// 完整堆排序
// 堆的底层数据结构、优先队列实现及 TopK 多种解法见 [[堆与优先队列]]
void heapsort(int arr[], int n) {
    // 第1步: 建堆 O(n)
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 第2步: 逐个取堆顶 O(n log n)
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);     // 最大值移到末尾
        heapify(arr, i, 0);       // 重建堆 O(log i)
    }
}

步骤	复杂度	说明
建堆 (buildHeap)	O(n)	自底向上，非叶节点逐个下沉
取n-1次堆顶	O(n log n)	每次取堆顶后 heapify 耗时 O(log i)
堆排序整体	O(n log n)	建堆 O(n) 被 log n 阶段主导
空间	O(1)	原地排序，无需额外数组

3.4 堆的数据结构特性（重要面试点）

特性	说明
不完全有序	堆不保证兄弟间顺序，只保证父子关系。不能用于"按序输出全量数据"
随机访问差	数组存储但父子节点在内存中距离远（index 差距大），缓存不友好
插入 O(log n)	新元素放末尾 → 上浮 (sift-up/bubble-up)
删除堆顶 O(log n)	末尾元素移到堆顶 → 下沉 (sift-down/heapify)
查找非堆顶 O(n)	堆不支持按值快速查找（不是搜索结构！）
取堆顶 O(1)	这是堆的核心优势
不稳定排序	相等元素的相对顺序可能改变

上浮 vs 下沉：

// 插入：上浮（新元素从底部向上调整）
void sift_up(int arr[], int i) {
    int parent = (i - 1) / 2;
    while (i > 0 && arr[parent] < arr[i]) {
        swap(arr[parent], arr[i]);
        i = parent;
        parent = (i - 1) / 2;
    }
}

// 删除堆顶：下沉（末尾元素从顶部向下调整）= heapify

堆 vs 快排：理论更优（严格 O(n log n)），但实际更慢——

缓存不友好：父子节点 index 差距大（2×），跨越式访问导致 cache miss 多
不稳定：不能保证相等元素相对顺序
无法利用部分有序：输入数据的有序性对堆没有帮助

何时用堆：优先队列（std::priority_queue/heapq）、Top K 问题、Introsort 的 O(n²) 兜底、Dijkstra 最短路径、多路归并。

4. 归并排序（Merge Sort）

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int *L = malloc(n1 * sizeof(int)), *R = malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
    free(L); free(R);
}

void mergesort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

最好	平均	最坏	空间	稳定
O(n log n)	O(n log n)	O(n log n)	O(n)	✅

归并排序的核心优势：

稳定排序 — 相等元素的相对顺序不变
适合外部排序 — 可以分块排序后归并（磁盘场景）
适合链表 — 不需要随机访问
并行友好 — 分治结构天然适合多线程

4.1 Timsort — Python 的工程杰作

Timsort 是归并排序的变体，由 Tim Peters 为 Python 设计（2002），现已被 Java、Android、Swift 采用。

python

# 核心思想：
# 1. 扫描数组，找自然运行（run）— 已排序的子序列
# 2. 如果 run 太短（<minrun），用插入排序扩充
# 3. 用类似归并排序的方式合并 run
# 4. 合并时利用"galloping"模式加速（当一个数组的元素连续多次来自一边时）

Timsort 为什么快：

真实数据常有部分有序 → Timsort 发现 runs 后几乎 O(n)
与 pdqsort 不同，Timsort 是稳定的（稳定排序的需求场景很多）

5. 快速选择（Quickselect）

找第 k 小的元素，平均 O(n)，最坏 O(n²)。

// 类似快排，但只递归一侧
int quickselect(int arr[], int low, int high, int k) {
    if (low == high) return arr[low];
    int pi = partition(arr, low, high);
    if (pi == k) return arr[pi];
    else if (pi > k) return quickselect(arr, low, pi - 1, k);
    else return quickselect(arr, pi + 1, high, k);
}

应用：Top K 问题（找第 K 大）、中位数查找、BFPRT 算法（最坏 O(n) 的中位数）

各语言的 nth_element：

语言	函数	算法
C++	`std::nth_element`	Introselect（快速选择 + 堆排兜底）
Go	无内置	需自己实现或用排序取下标
Python	`heapq.nlargest/nsmallest`	堆实现

6. 排序算法对比总览

mermaid

flowchart LR
    subgraph Comparison["比较排序 (Ω(n log n))"]
        QS["快速排序<br/>pivot分区+递归<br/>实践最快"]
        MS["归并排序<br/>分治+合并<br/>稳定+外排"]
        HS["堆排序<br/>建堆+取顶<br/>O(1)空间"]
    end

    subgraph Hybrid["混合排序 (工程实践)"]
        PDQ["pdqsort Go/Rust<br/>快排+插入+堆排兜底<br/>自适应"]
        TIM["Timsort Python/Java<br/>归并+自然run<br/>部分有序极快"]
        INTRO["Introsort C++<br/>快排+堆排兜底<br/>防退化"]
    end

    subgraph NonComp["非比较排序 (突破下界)"]
        CS["计数排序 O(n+k)"]
        RS["基数排序 O(dn)"]
        BS["桶排序 O(n)期望"]
    end

    QS --> PDQ
    MS --> TIM
    HS --> INTRO

    style PDQ fill:#4CAF50,color:#fff
    style TIM fill:#2196F3,color:#fff
    style INTRO fill:#FF9800,color:#fff
    style CS fill:#9C27B0,color:#fff

算法	平均	最坏	空间	稳定	何时用
冒泡	O(n²)	O(n²)	O(1)	✅	教学
插入	O(n²)	O(n²)	O(1)	✅	n≤32 的子数组
选择	O(n²)	O(n²)	O(1)	❌	交换成本极高
快排	O(n log n)	O(n²)	O(log n)	❌	通用，最快
堆排	O(n log n)	O(n log n)	O(1)	❌	内存受限，TopK
归并	O(n log n)	O(n log n)	O(n)	✅	外部排序，需要稳定
Timsort	O(n log n)	O(n log n)	O(n)	✅	部分有序数据（Python）
pdqsort	O(n log n)	O(n log n)	O(log n)	❌	通用混合（Go/Rust）
Introsort	O(n log n)	O(n log n)	O(log n)	❌	通用混合（C++）

6.1 选择决策树

需要稳定？
├── 是 → 数据在内存 → Timsort
│        └── 数据在磁盘 → 外部归并排序
│
└── 否 → 通用场景 → pdqsort / Introsort
         └── 内存极有限 → 堆排序（原地 O(1)）
              └── 只需要 Top K → 堆 或 快速选择

7. 外部排序（External Sort）— 数据放不下内存

当数据 > 可用内存时：

Phase 1: 分块排序
  读取 M 大小的块 → 内存排序 → 写入临时文件
  → Sorted_Chunk_1, Sorted_Chunk_2, ..., Sorted_Chunk_N

Phase 2: K 路归并
  从 N 个临时文件各读一个 buffer
  → 用最小堆维护 N 路的当前最小值
  → 每次输出最小值，从对应文件读下一个值

数据库的 ORDER BY 在内存不足时用的就是这个策略。PostgreSQL 的 work_mem 参数决定了多少数据可以在内存排序。

7.1 外部排序的优化

置换-选择排序（Replacement Selection）：在 Phase 1 生成更长的初始 run。

传统方法: 每块 M → 排序 → run 长度 = M
置换选择: 用最小堆维护 → run 长度 ≈ 2M（数据稍有偏序时更长）

多路归并的 buffer 管理：每个输入文件分配一个 buffer，用双缓冲（一个读磁盘，一个给归并使用）来隐藏 IO 延迟。

8. 排序的理论下界

8.1 比较排序的 Ω(n log n) 下界

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

决策树证明：

n 个元素的排列有 n! 种 → 决策树至少 n! 个叶子
高度为 h 的二叉树最多 2^h 个叶子
需要 2^h ≥ n! → h ≥ log₂(n!)
由 Stirling 近似: log₂(n!) ≈ n·log₂(n) - n·log₂(e) = Ω(n log n)

推论：堆排序和归并排序在最坏情况下已经是最优的比较排序。

8.2 突破下界：非比较排序

算法	复杂度	条件	为什么能突破
计数排序	$O (n + k)$	整数，范围 k	不比较，直接用值做索引
基数排序	$O (d (n + k))$	d 位数字	按位分配，不比较
桶排序	$O (n)$ 期望	均匀分布	先分配再比较（桶内）

基数排序的洞见：如果 key 有固定位数（如 32 位整数），用 8 位作为基数只需要 4 轮 → $O (4 n) = O (n)$ 。

对 100 万个随机 32 位整数排序：
  基数排序 (R=8):   4 轮，每轮 O(n+256) → ~8ms
  快速排序:         O(n log n)            → ~80ms
  std::sort (C++):  Introsort              → ~60ms

基数排序在特定场景下可以碾压比较排序。

9. 并行排序

9.1 并行归并排序

归并排序的分治结构天然适合并行化：

func parallelMergeSort(arr []int, depth int) {
    if len(arr) <= 1 { return }
    mid := len(arr) / 2
    if depth < maxDepth {
        var wg sync.WaitGroup
        wg.Add(2)
        go func() { parallelMergeSort(arr[:mid], depth+1); wg.Done() }()
        go func() { parallelMergeSort(arr[mid:], depth+1); wg.Done() }()
        wg.Wait()
    } else {
        mergeSort(arr[:mid])  // 串行
        mergeSort(arr[mid:])
    }
    merge(arr, mid)
}

9.2 并行快速排序

与归并类似，分区后两个子数组可以并行处理。

关键问题：分区的 pivot 选择在并行场景下更关键——差的 pivot 导致严重的负载不均衡。

9.3 采样排序（Sample Sort）

用于大规模多机排序（如 Spark/Hadoop）：

1. 每个节点对自己负责的数据片段排序
2. 从每个节点采样一部分数据，汇总后排序
3. 根据采样结果确定全局的分区边界（splitters）
4. 按 splitter 重新分配数据 → 保证每个分区的范围不重叠
5. 每个节点对自己分到的数据排序
6. 直接拼接所有分区（已全局有序）

10. 流式/在线排序

10.1 场景

数据持续到达，需要在任意时刻能输出当前 Top K。

流式数据: [3, 1, 4, 1, 5, 9, 2, ...] → 随时要 "当前最大的 3 个"

10.2 解法

固定大小的堆：维护一个大小为 K 的最小堆。

type TopK struct {
    k    int
    heap *minHeap
}

func (t *TopK) Add(val int) {
    if t.heap.Len() < t.k {
        heap.Push(t.heap, val)
    } else if val > t.heap.Peek() {
        heap.Pop(t.heap)
        heap.Push(t.heap, val)
    }
    // 时间复杂度: O(log k)
}

func (t *TopK) Get() []int {
    // 返回当前最大的 K 个元素（不保证顺序）
}

10.3 工程实例

Prometheus TopK 查询：topk(5, http_requests_total)
Nginx 访问日志：实时 Top 10 IP
推荐系统：实时 Top N 热门商品
广告竞价：Top K 出价

11. 排序与 CPU/内存的关系 — 为什么"同样 O(n log n)"实际速度差很多

11.1 复杂度相同，真实性能差异巨大

算法	理论复杂度	100 万随机 int 实测	原因
快排 (pdqsort)	O(n log n)	~45ms	cache 友好、分支可预测
归并排序	O(n log n)	~65ms	顺序写好，但需要额外内存
堆排序	O(n log n)	~120ms	cache 极不友好

同样 O(n log n)，堆排序为什么比快排慢 2-3 倍？

11.2 Cache 局部性是关键

mermaid

flowchart LR
    subgraph QS["快排"]
        A1["分区: 从两端向中间扫描<br/>连续内存访问<br/>cache line 预取命中"]
    end
    subgraph HS["堆排"]
        A2["heapify: 父子节点跳跃<br/>index 2i, 2i+1<br/>跨越式访问, cache miss 多"]
    end
    subgraph MS["归并排"]
        A3["合并: 两个有序段顺序读<br/>写入连续输出数组<br/>顺序写极好"]
    end

具体分析：

算法	访问模式	Cache 行为	预取效果
快排	分区时从左右两端向中间扫描	连续访问，cache line 利用率高	硬件预取器能跟上
归并排	两个有序段顺序读 + 顺序写	读写都连续，但需要额外 O(n) 空间	预取效果好
堆排	父子节点 index 差距大（2i, 2i+1）	跳跃式访问，cache miss 严重	预取器跟不上
插入排	相邻元素比较和移动	极好的局部性	小数组时最优

量化差异（100 万 int，L1=32KB，cache line=64B）：

text

快排分区:
  每次 cache line 加载 16 个 int
  扫描方向固定 → 预取命中率 > 95%
  L1 miss rate: ~1-3%

堆排 heapify:
  父节点 i → 子节点 2i+1
  当 i > 4096 时，父子节点已不在同一 cache line
  当 i > 65536 时，父子节点可能不在同一 L2 区域
  L1 miss rate: ~15-30%

11.3 分支预测对排序的影响

快排的分区操作有一个核心分支：if (arr[j] <= pivot)

text

随机数据:
  pivot 大约把数据分成两半
  前半段几乎全部 <= pivot → 分支预测"跳"→ 准确率高
  后半段几乎全部 > pivot → 分支预测"不跳"→ 准确率高
  只有 pivot 附近的少量元素不可预测

结论: 快排的分支预测准确率通常 > 90%

pdqsort 为什么比传统快排更快？

pdqsort 的分区使用了一种"分支预测友好"的技巧：

text

传统 Lomuto 分区:
  每个元素都有一个 if 分支
  随机数据时预测准确率 ~50%

pdqsort 的 Hoare 分区 + 优化:
  从两端向中间扫描
  左指针一直向右走直到找到 > pivot 的
  右指针一直向左走直到找到 < pivot 的
  → 连续多次"同方向"移动 → 分支预测准确率高

11.4 归并排序的额外空间为什么有时反而是优势

text

归并排序需要 O(n) 额外空间，看起来是劣势。
但在大数据量时：

快排的分区:
  在原数组上来回交换
  当数组 > L2 cache 时，交换操作导致大量 cache miss

归并排序:
  两个有序段 → 顺序读
  输出到新数组 → 顺序写
  顺序读写对 cache 和预取器极友好
  即使多了一倍内存，吞吐可能更高

这也是为什么：

外部排序（磁盘）几乎只用归并
并行排序更偏爱归并（分治结构天然并行）
Python/Java 选择 Timsort（归并变体）而非快排

11.5 基数排序为什么在大数据量时可能变慢

基数排序理论上是 O(dn)，看起来比 O(n log n) 更优。但实际上：

text

基数排序的访问模式:
  按位分配到 256 个桶
  → 每个桶的写入位置是随机的
  → 当数据量 > L1 cache 时，写入变成随机写
  → cache miss 严重

当 n < L1 能装下时:
  基数排序碾压比较排序

当 n >> L1 时:
  每轮分配的随机写导致大量 cache miss
  实际性能可能不如 pdqsort

数据量	基数排序	pdqsort	原因
1K int	快 3×	基准	全在 L1 里
100K int	快 1.5×	基准	L2 能装下
10M int	可能更慢	基准	随机写 cache miss 严重

11.6 小数组为什么用插入排序

pdqsort/Introsort/Timsort 在子数组 < 16~32 时都切换到插入排序，原因不只是"常数因子小"：

text

1. 插入排序的比较和移动都是相邻元素
   → 极好的空间局部性
   → 几乎不会 cache miss

2. 分支模式简单
   → 分支预测器容易学习
   → 几乎没有预测失败

3. 没有递归开销
   → 没有函数调用、栈帧、寄存器保存

4. 对"几乎有序"的数据接近 O(n)
   → 递归到底层时数据通常已经"大致有序"

11.7 排序算法选择的硬件视角

mermaid

flowchart TD
    A["数据量多大?"] --> B{"< L1 cache?"}
    B -->|是| C["插入排序 / 基数排序<br/>局部性极好"]
    B -->|否| D{"< L2 cache?"}
    D -->|是| E["pdqsort / 快排<br/>分区的 cache 利用率高"]
    D -->|否| F{"在内存中?"}
    F -->|是| G["pdqsort / 归并排序<br/>归并的顺序写更友好"]
    F -->|否| H["外部归并排序<br/>顺序 I/O 是唯一选择"]

11.8 一条实战原则

text

选排序算法时，不要只看 O(n log n)。
要问：
1. 数据量相对于 cache 有多大？
2. 访问模式是连续的还是跳跃的？
3. 分支是否可预测？
4. 是否需要额外空间？额外空间换来的顺序写是否值得？

大多数时候直接用语言标准库（Go sort.Slice、C++ std::sort、Python sorted）就是最优选择——它们已经把上述所有因素都考虑进去了。

参考

Hello 算法 — 数据结构与算法基础入门教程
CLRS 第 6-8 章 — 堆排序、快速排序、线性时间排序、排序下界
pdqsort: Pattern-defeating Quicksort
Timsort 原著 (Tim Peters)
Go sort 包实现

排序与选择算法 ​

1. 基本排序算法 ​

1.1 冒泡排序（Bubble Sort） ​

1.2 插入排序（Insertion Sort） ​

1.3 选择排序（Selection Sort） ​

2. 快速排序（Quick Sort）— 实践中最快 ​

2.1 基本算法 ​

2.2 三大优化（生产级快排必备） ​

2.3 各语言快排实现 ​

2.4 Introsort (C++ STL) ​

2.5 pdqsort (Go 1.19+, Rust) ​

3. 堆排序（Heap Sort） ​

3.1 堆数据结构 ​

3.2 建堆（Build Heap）— O(n) 不是 O(n log n)！ ​

3.3 排序过程 ​

3.4 堆的数据结构特性（重要面试点） ​

4. 归并排序（Merge Sort） ​

4.1 Timsort — Python 的工程杰作 ​

5. 快速选择（Quickselect） ​

6. 排序算法对比总览 ​

6.1 选择决策树 ​

7. 外部排序（External Sort）— 数据放不下内存 ​

7.1 外部排序的优化 ​

8. 排序的理论下界 ​

8.1 比较排序的 Ω(n log n) 下界 ​

8.2 突破下界：非比较排序 ​

9. 并行排序 ​

9.1 并行归并排序 ​

9.2 并行快速排序 ​

9.3 采样排序（Sample Sort） ​

10. 流式/在线排序 ​

10.1 场景 ​

10.2 解法 ​

10.3 工程实例 ​

11. 排序与 CPU/内存的关系 — 为什么"同样 O(n log n)"实际速度差很多 ​

11.1 复杂度相同，真实性能差异巨大 ​

11.2 Cache 局部性是关键 ​

11.3 分支预测对排序的影响 ​

11.4 归并排序的额外空间为什么有时反而是优势 ​

11.5 基数排序为什么在大数据量时可能变慢 ​

11.6 小数组为什么用插入排序 ​

11.7 排序算法选择的硬件视角 ​

11.8 一条实战原则 ​

参考 ​

💬 文章评论

排序与选择算法

1. 基本排序算法

1.1 冒泡排序（Bubble Sort）

1.2 插入排序（Insertion Sort）

1.3 选择排序（Selection Sort）

2. 快速排序（Quick Sort）— 实践中最快

2.1 基本算法

2.2 三大优化（生产级快排必备）

2.3 各语言快排实现

2.4 Introsort (C++ STL)

2.5 pdqsort (Go 1.19+, Rust)

3. 堆排序（Heap Sort）

3.1 堆数据结构

3.2 建堆（Build Heap）— O(n) 不是 O(n log n)！

3.3 排序过程

3.4 堆的数据结构特性（重要面试点）

4. 归并排序（Merge Sort）

4.1 Timsort — Python 的工程杰作

5. 快速选择（Quickselect）

6. 排序算法对比总览

6.1 选择决策树

7. 外部排序（External Sort）— 数据放不下内存

7.1 外部排序的优化

8. 排序的理论下界

8.1 比较排序的 Ω(n log n) 下界

8.2 突破下界：非比较排序

9. 并行排序

9.1 并行归并排序

9.2 并行快速排序

9.3 采样排序（Sample Sort）

10. 流式/在线排序

10.1 场景

10.2 解法

10.3 工程实例

11. 排序与 CPU/内存的关系 — 为什么"同样 O(n log n)"实际速度差很多

11.1 复杂度相同，真实性能差异巨大

11.2 Cache 局部性是关键

11.3 分支预测对排序的影响

11.4 归并排序的额外空间为什么有时反而是优势

11.5 基数排序为什么在大数据量时可能变慢

11.6 小数组为什么用插入排序

11.7 排序算法选择的硬件视角

11.8 一条实战原则

参考