排序算法：从比较排序到工程选择

以前看到“排序算法：从比较排序到工程选择”，我会下意识去找一份模板保存下来。后来发现这样学得很快，忘得也快，因为我曾经认真背过每一种排序的代码，却没有想过真实项目里为什么通常直接调用库函数，以及什么时候库函数也不够。所以这篇不从标准答案起步，而是顺着我当时的疑问一点点往下拆。

排序算法是算法学习里绕不开的一章。它表面是在把数据排成顺序，背后其实包含了比较、交换、分区、合并、稳定性、空间取舍和数据分布判断。

不要把排序学成“背十个算法的复杂度表”。真正重要的是：面对不同输入条件，你知道为什么该选某一种排序。

它从哪里来

排序曾直接受穿孔卡片和机械设备影响，读写次数与内存限制决定算法选择。归并排序适合顺序合并，Hoare 在 1959 年设计的快速排序擅长内存内分区，堆排序提供稳定的最坏界。现代标准库通常组合多种方法，而不是迷信单一冠军。

排序算法选择地图

图：排序算法需要按数据规模、稳定性、额外空间和数据范围选择

排序最常见的评价维度：

稳定性在业务系统里很重要。比如先按时间排序，再按优先级稳定排序，如果算法不稳定，前一次排序结果可能被破坏。

基础排序：用于理解，不用于大规模

冒泡排序

冒泡每轮把最大值“冒”到末尾。

void bubbleSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

冒泡平均和最坏都是 O(n²)，但有一个好处：基本有序时可以提前结束。

选择排序

选择排序每轮找最小值放到当前位置。

它交换次数少，但不稳定，时间复杂度始终 O(n²)。它适合教学，不适合常规工程排序。

插入排序

插入排序维护一个局部有序区，把新元素插入合适位置。

void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int x = a[i], j = i - 1;
        while (j >= 0 && a[j] > x) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = x;
    }
}

插入排序在小数组和基本有序数组上表现很好，很多工程排序实现会在分治到小区间时切换到插入排序。

归并排序

归并排序的思想是：先把数组拆小，分别排好，再合并。

void mergeSort(int[] a, int l, int r, int[] temp) {
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(a, l, m, temp);
    mergeSort(a, m + 1, r, temp);
    merge(a, l, m, r, temp);
}

归并排序时间稳定是 O(n log n)，并且可以做到稳定排序，缺点是需要 O(n) 额外空间。

链表排序常用归并，因为链表合并不需要像数组那样大量搬移元素。

快速排序

快速排序通过一个 pivot 把数组分成两侧：

• 小于 pivot 的放左边。
• 大于 pivot 的放右边。
• 再递归处理两边。

平均复杂度是 O(n log n)，但如果 pivot 总是选得很差，最坏会退化成 O(n²)。

void quickSort(int[] a, int l, int r) {
    if (l >= r) return;
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

工程里常用随机 pivot、三数取中、三路切分来降低退化风险。重复元素很多时，三路快排会明显更稳。

堆排序

堆排序先建最大堆，然后反复把堆顶最大值放到数组末尾。

它的时间复杂度稳定是 O(n log n)，额外空间 O(1)，但不稳定，缓存局部性通常不如快排。

堆排序更大的意义是帮助理解优先队列和 Top K。实际业务里“只要前 K 个最大元素”时，没必要完整排序，维护一个大小为 K 的小根堆即可。

非比较排序

比较排序的下界是 O(n log n)，但如果数据有特殊条件，可以更快。

计数排序适合整数范围不大：

int[] countSort(int[] a, int maxValue) {
    int[] count = new int[maxValue + 1];
    for (int x : a) count[x]++;
    int[] ans = new int[a.length];
    int idx = 0;
    for (int v = 0; v <= maxValue; v++) {
        while (count[v]-- > 0) ans[idx++] = v;
    }
    return ans;
}

桶排序适合数据均匀分布，基数排序适合按位处理整数或定长字符串。它们不是通用神器，前提条件比比较排序更强。

复杂度对比

工程场景

实际开发中，大多数时候应该使用语言标准库排序，而不是手写排序。但懂排序仍然很重要，因为你要知道：

• 数据量小且基本有序时，插入排序可能很快。
• 需要稳定排序时，不能随便换成不稳定算法。
• 只取 Top K 时，堆比完整排序更合适。
• 数据范围很小且频繁统计时，计数排序或桶思想很有价值。
• 外部排序、大文件排序通常依赖归并思想。

面试题

1. 快排为什么平均快，最坏为什么会退化？
2. 归并排序为什么稳定？代价是什么？
3. 什么是排序稳定性？业务里有什么用？
4. Top K 为什么不一定要完整排序？
5. 计数排序为什么不是通用排序？

小结

排序算法不是越高级越好，而是约束不同，取舍不同。学排序最重要的是形成选择能力：规模、稳定性、空间、输入分布、是否只要 Top K。能说清这些，比背复杂度表更接近真实工程。