排序算法的评价从来不止”快”一个维度：时间、空间、稳定性是三把基本尺子。比较类排序无法突破 Ω(n log n) 的比较下界，非比较类则利用值域、分布、位数等额外信息换取线性时间。本文按”比较 vs 非比较”两大阵营梳理十种经典算法，重点拆透工程中最常用的快排与归并。

它解决什么问题

排序解决的是”为一组记录建立全序”的问题，它既是独立需求（排行榜、分页），也是其他算法的前置步骤（二分查找、去重、贪心）。选型的难点在于没有银弹：数据规模、初始有序度、值域范围、内存预算、稳定性要求，每一项都会改变最优解。理解排序的关键不是背十个名字，而是吃透四类机制：交换、插入、分治、计数。

核心原理

比较类：交换与插入一族

  • 冒泡排序：相邻元素两两比较、逆序即交换，每轮把最大值”浮”到末尾。加提前退出标志后最好 O(n)，平均与最坏 O(n²)，空间 O(1)，稳定。教学价值大于实用价值。
  • 选择排序：每轮从未排序区挑出最小值，放到已排序区末尾。任何输入都是 O(n²)，但交换次数最多 n-1 次，写入昂贵的场景偶有优势；不稳定。
  • 插入排序：像整理扑克牌，把新元素插进已排序区。近乎有序时 O(n)，平均 O(n²)，稳定。小规模数据上常数极小，是工业级排序的”收尾刀”。
  • 希尔排序：插入排序的推广，按递减步长分组插入，大步长快速消减逆序对，步长收敛到 1 时数组已近有序。复杂度依赖步长序列：Shell 原始增量最坏 O(n²)，Sedgewick 等序列可达约 O(n^4/3)；不稳定。

比较类：分治一族

  • 归并排序：递归拆半，各自排好后线性合并。任何输入都是 O(n log n)，稳定，代价是 O(n) 辅助空间。
  • 快速排序：选枢轴分区，小的放左、大的放右，再递归两侧。平均 O(n log n)、最坏 O(n²)，原地但不稳定。
  • 堆排序：建最大堆后反复弹出堆顶放到末尾。任何输入 O(n log n)、空间 O(1)，但不稳定，且访问模式跳跃、缓存不友好，实践中常输给快排。

非比较类：计数一族

  • 计数排序：用值当下标统计出现次数，再按累计次数回填。O(n+k)，k 为值域跨度；值域小则飞快，值域大则空间爆炸。稳定。
  • 桶排序：把值域映射到若干桶，桶内排序后拼接。分布均匀时期望接近 O(n+k)，全部挤进一个桶则退化为桶内算法的复杂度；稳定性取决于桶内排序。
  • 基数排序：按位从低到高做多轮稳定的分配收集，通常以计数排序作子过程。O(d(n+r))，d 为位数、r 为基数。稳定。

深入机制

快排：分区策略决定生死

分区（partition）是快排的灵魂。Lomuto 方案以尾元素为枢轴、单指针维护”小于枢轴”的边界，好写但交换偏多；Hoare 方案用首尾双指针向中间夹逼，比较和交换更少，但边界更难写对。无论哪种，固定选首尾元素作枢轴都会在已排序数组上退化到 O(n²)——递归树退化成链。对策是随机化选枢轴（或三数取中），让坏输入无法被刻意构造，期望时间回到 O(n log n)：

int partition(int[] a, int lo, int hi) {
    int r = lo + ThreadLocalRandom.current().nextInt(hi - lo + 1);
    swap(a, r, hi);                 // 随机枢轴换到末尾
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) swap(a, i++, j);
    }
    swap(a, i, hi);
    return i;                       // 枢轴最终落位
}

大量重复键会让二路分区把相等元素全堆到一侧，递归深度接近 n。三路划分（Dutch National Flag）把区间切成 <pivot、=pivot、>pivot 三段，相等元素一次性归位、不再参与递归，重复键越多反而越快：

void sort3Way(int[] a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[lo], lt = lo, i = lo + 1, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot) swap(a, lt++, i++);
        else if (a[i] > pivot) swap(a, i, gt--);
        else i++;
    }
    sort3Way(a, lo, lt - 1);
    sort3Way(a, gt + 1, hi);
}

归并：稳定性的来源与外部排序

归并的稳定来自合并时”相等先取左半”这一条规则——左半元素在原数组中本就靠前：

while (i <= mid && j <= hi) {
    tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];  // <= 保证左先右后
}

归并的另一大战场是外部排序：数据放不进内存时，先分块读入、各自内排后写回磁盘，形成若干有序段（run），再做 k 路归并——借助大小为 k 的小顶堆或败者树，每次从 k 个段头取最小者写出，一趟 O(n log k)。数据库排序溢出到磁盘、海量日志归并，都是这个套路。

工程实践

工业实现从不单押一种算法：Java 的 Arrays.sort 对基本类型用双枢轴快排，对对象用 TimSort（归并加插入的混合，善于利用数据中天然存在的有序段）；C++ 的 std::sort 是内省排序——快排递归深度超限就转堆排，小区间转插入。启示是：小规模用插入、怕退化用堆排兜底、要稳定用归并，这些判断完全可以组合进同一个实现。

对比与权衡

算法 平均时间 最坏时间 空间 稳定性 适用场景
冒泡 O(n²) O(n²) O(1) 稳定 教学演示
选择 O(n²) O(n²) O(1) 不稳定 写入代价极高的小数据
插入 O(n²) O(n²) O(1) 稳定 小规模、近乎有序
希尔 依赖步长 O(n²)~O(n^4/3) O(1) 不稳定 中等规模原地排序
归并 O(n log n) O(n log n) O(n) 稳定 链表、外部排序、要求稳定
快排 O(n log n) O(n²) O(log n) 栈 不稳定 通用内存排序主力
堆排 O(n log n) O(n log n) O(1) 不稳定 内存紧张且要最坏保证
计数 O(n+k) O(n+k) O(n+k) 稳定 值域小的整数
桶 期望 O(n+k) 取决于桶内 O(n+k) 取决于桶内 均匀分布的数据
基数 O(d(n+r)) O(d(n+r)) O(n+r) 稳定 定长整数、定长字符串

选型口诀：通用内存排序用优化快排；要求稳定或排序链表用归并；空间极限紧张又要 O(n log n) 上界用堆排；小数组或近有序用插入；整数且值域小、位数少时，计数与基数能跑到线性。

面试视角

快排最坏 O(n²) 怎么来的，怎么防？ 每次分区都选中极值，递归树退化成链，比较次数是 n+(n-1)+…+1。防御靠随机选枢轴或三数取中，把退化概率压到极低；重复键多时再上三路划分。

归并为什么稳定，代价是什么？ 合并时相等元素优先取左半，相对次序不变。代价是 O(n) 辅助空间——原地归并理论上存在，但实现复杂、常数大，工程上不值得。

堆排同样 O(n log n)，为什么实践中少用？ 堆的访问跨步跳跃、缓存命中率低，同数据量下常数明显大于快排；但它有最坏 O(n log n) 保证，内省排序拿它当快排深度超限时的兜底。

稳定性到底是什么，何时重要？ 相等键的相对次序在排序后保持不变。多关键字排序（先按时间排、再按分数排）依赖稳定性，否则前一轮的成果会被打乱。

小结

  • 排序选型看四个维度：规模、初始有序度、值域与分布、稳定性与空间约束。
  • 快排的竞争力在分区质量：随机化防退化，三路划分治重复键。
  • 归并用 O(n) 空间换来稳定性与最坏保证，也是外部排序的骨架。
  • 非比较类排序用信息换时间，离开”值域小、分布匀、位数定”这些前提就不成立。