排序算法大概是算法入门绕不开的第一课，也是面试里被问得最多的话题之一。

但很多人学排序的方式是”背代码”，结果背了忘、忘了背。

其实只要抓住每个算法的核心思想，代码自然就能写出来。

先记住这个底线

基于比较的排序算法，时间复杂度有理论下界：O(n log n)。

也就是说，任何”靠比较大小来排序”的算法，最优也就是 O(n log n)，不可能更快（除非用计数排序、桶排序这种不基于比较的特殊算法）。

所以快排、归并、堆排，都是已经摸到比较排序天花板的算法。

快速排序：分治 + 分区

快排的核心是分区（partition）：选一个”基准值（pivot）”，把数组分成两部分——左边都比 pivot 小，右边都比 pivot 大。然后对左右两部分递归做同样的事。

1
2
3
4
5
6
void quickSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partition(arr, lo, hi);  // 分区，返回 pivot 位置
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
}
  • 平均 O(n log n)，最坏 O(n²)（比如已经有序时，pivot 选得差会退化成链表）
  • 原地排序，空间 O(log n)（递归栈）
  • 不稳定（partition 交换会打乱相同元素的相对顺序）

快排的实际性能通常是最好的，因为它是原地排序，且对 CPU 缓存友好。

归并排序：先分后合

归并的核心是合并（merge）：先把数组从中间一分为二，分别排好序，再把两个有序子数组合并成一个有序数组。

1
2
3
4
5
6
7
void mergeSort(int[] arr, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid + 1, hi);
    merge(arr, lo, mid, hi);  // 合并两个有序部分
}
  • 稳定：任何情况下都是 O(n log n)
  • 但需要 O(n) 的额外空间（合并时需要辅助数组）

归并排序的最大特点是稳定，这在”按多个字段排序”（比如先按成绩、再按姓名）时非常重要。

堆排序：利用堆的性质

前面讲堆时提过：建一个大顶堆，反复取堆顶（最大值）放到末尾。

  • 稳定 O(n log n)，原地排序，空间 O(1)
  • 不稳定

堆排序的优势是空间 O(1)，但实际速度通常不如快排，因为堆的父子节点在内存里不是连续的，缓存不友好。

三大排序对比

算法 平均 最坏 空间 稳定
快排 O(n log n) O(n²) O(log n) 否
归并 O(n log n) O(n log n) O(n) 是
堆排 O(n log n) O(n log n) O(1) 否

怎么选

  • 通用场景 → 快排（最快，实际中默认选它）
  • 需要稳定 → 归并（Java 的 Arrays.sort 对对象数组就是用归并，保证稳定）
  • 内存受限、又不想用额外空间 → 堆排

顺带说个冷知识：Java 的 Arrays.sort 对基本类型（int[]）用的是双轴快排（因为基本类型不需要稳定），对对象类型（Integer[]）用的是归并排序（因为对象要保证稳定）。

为什么”稳定”很重要

稳定性指的是：值相同的元素，排序后相对顺序不变。

举个例子，员工列表先按”部门”排序，再按”薪资”排序。如果第二次排序是稳定的，那么薪资相同的员工，还是保持部门内的顺序。不稳定的话，部门顺序就乱了。

所以在”多关键字排序”的场景，稳定性是硬需求。

写在最后

学排序，我建议这样记：

  1. 记住每个算法的核心动作：快排是”分区”、归并是”合并”、堆排是”下沉”
  2. 记住复杂度表格，尤其是稳定性和空间
  3. 手写一遍，比看十遍视频都管用

排序是算法的基础功，下一篇讲的二分查找，则是最”看似简单、实则处处是坑”的算法。