排序到底能有多快？

比较排序的下界

比较排序了解数据的唯一途径是问"a 是否小于 b？"。令人意外的是，仅凭这个问题就限制了任何此类排序能有多快：没有任何比较排序能在最坏情况下突破 Ω(n log n)。因此归并排序和调校良好的快速排序在比较排序中本质上已是最优。

直觉是一棵决策树。每次比较有两种结果，所以高度为 h 的是非答案树至多能区分 2^h 种情形。要排好 n 个元素，你必须分辨全部 n! 种可能的排列，于是需要 2^h ≥ n!，即 h ≥ log2(n!)。而 log2(n!) 的增长形如 n log n——这就是那道墙，无需繁重的证明。

Decision tree to sort 3 elements a, b, c (each leaf = one ordering):

                a<b ?
              /       \
           yes          no
          b<c?          a<c?
         /    \        /    \
     a<b<c   a<c?   b<a<c   b<c?
            /   \          /   \
        a<c<b  c<a<b   b<c<a  c<b<a

  3! = 6 leaves -> tree must be tall enough; height ~ log2(6).

不靠比较，越过这道墙

这道墙只约束比较型排序。如果你改为把键本身当作下标，就能逃出它。计数排序对范围在 0..k 内的 n 个整数排序：统计每个值出现的次数，再按顺序写出来——O(n + k)，完全不做比较。

// counting sort for values in [0, k]
void countingSort(int a[], int n, int k) {
    std::vector<int> count(k + 1, 0);
    for (int i = 0; i < n; i++) count[a[i]]++;   // tally each value
    int idx = 0;
    for (int v = 0; v <= k; v++)                 // write back in order
        while (count[v]-- > 0) a[idx++] = v;
}

堆排序：原地的 O(n log n)

在比较排序中还有一个值得认识：堆排序。它从数组建出一个堆（一种树形的优先级结构，你将在下一级见到），然后反复取出最大值并缩小堆。它是最坏 O(n log n)——与归并排序的保证相当——而且原地进行，只用 O(1) 额外空间。

1. 归并排序：永远 O(n log n)，稳定，O(n) 空间。
2. 快速排序：平均 O(n log n) / 最坏 O(n^2)，不稳定，原地，实践中最快。
3. 堆排序：最坏 O(n log n)，不稳定，原地——以 O(1) 空间换取最坏情况保证。
4. 计数 / 基数排序：O(n + k) / O(d·(n+基数))，但仅限小整数键。

把它们串起来

所以"排序能有多快？"有两个答案。如果你只能比较，Ω(n log n) 就是地板，归并/快速/堆排序正好踩在上面。如果你的键有结构——小整数——你就能改用计数而非比较，降到线性时间。

下一级我们告别线性数据：展开到树、为堆排序提供动力的堆，以及图——而递归会一路同行。