面试的时候八大排序倒背如流，工作几年后发现实际开发里真用得上的就那么两三个。整理一下哪些该深挖、哪些面试背完就得了。
先放结论：实际开发 90% 的场景，直接用语言自带的排序就够了。 Java 的 Arrays.sort()、Python 的 sorted()，底层都是经过高度优化的（ Tim Sort / 双轴快排），比你手写的任何排序都快。手写排序的意义在于理解原理和应对面试，不是让你在生产环境替代标准库。
逐个说：
快速排序 — 唯一值得深挖的
实际工程里接触最多的排序底层就是快排。Java Arrays.sort() 对基本类型用双轴快排（ Dual-Pivot Quicksort ），理解快排的分区逻辑对你看懂标准库源码有帮助。
关键点不是怎么写，是怎么选 pivot。取第一个元素是教科书写法，实际遇到已排序数组直接退化到 O(n²)。三数中值法（左端、右端、中位数的中间值）是基本操作，更稳的是随机选 pivot 。
// 核心：分区，不是排序本身
int partition(int[] a, int low, int high) {
int pivot = a[low]; // 实际用三数中值法
while (low < high) {
while (low < high && a[high] >= pivot) high--;
a[low] = a[high];
while (low < high && a[low] <= pivot) low++;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
平均 O(nlogn)，最坏 O(n²)，不稳定。但实际优化后（随机 pivot + 小数组切插入排序）极难触发最坏情况。
归并排序 — 理解 Tim Sort 的基础
Tim Sort （ Python/Java 对象排序用的）就是归并的变种。归并排序本身在面试里考得多，实际手写场景少。
几个容易被问的细节：
- 时间复杂度最好最坏都是 O(nlogn)，稳定
- 额外空间是 O(n)，不是 O(1)——需要临时数组，这点很多人记错
- 适合链表排序（不需要随机访问）、外部排序（数据量大到内存放不下）
堆排序 — 知道原理就行
面试会问 Top-K 问题，本质就是堆。但手写堆排序的场景我工作几年没遇到过。理解大根堆/小根堆的调整逻辑，知道 PriorityQueue 怎么用，够了。
时间复杂度 O(nlogn)，不稳定。堆排序的常数比快排大，实际跑起来比快排慢，所以标准库基本不用纯堆排序。
插入排序 — 小数据量王者
这个反而容易被忽略。当数据量小（通常 < 47 ）时，插入排序比快排快——没有递归开销，常数小。Java 的 Arrays.sort() 在子数组小于阈值时就会切到插入排序（双轴快排里叫 "insertion sort on small arrays"）。
大部分已排序时效率高，最好情况 O(n)。稳定，额外空间 O(1)。
冒泡排序 — 面试背完就得了
唯一的价值是理解"交换排序"的思路。实际开发没有任何场景该用冒泡。加 flag 优化的版本最好情况 O(n)，但插入排序同样能做到且常数更小。
别拿冒泡去面试写手撕代码，写快排或归并。
选择排序 — 同上
不稳定，且最好最坏都是 O(n²)。没有任何实际优势，唯一的教学价值是理解"选择"思路。
希尔排序 — 知道是插入排序的改进就行
希尔排序是插入排序的分组改进版，通过增量序列逐步缩减让元素大致有序。时间复杂度取决于增量序列，最好可以到 O(nlogn)，最坏 O(n²)。
实际工程基本不用，但面试偶尔会问"希尔排序和插入排序的关系"。
桶排序 / 计数排序 — 特定场景才用
非比较排序，时间复杂度可以到 O(n)，但限制大：
- 值域必须是可枚举的整数范围
- 值域 k 和数据量 n 接近时才划算（ k >> n 时空间浪费严重）
- **额外空间 O(k)**，不是 O(1)
实际场景：给百万级年龄数据排序（ 0-150 的值域），计数排序秒杀一切比较排序。但你给字符串排序就别想了。
一张表总结（修正了常见错误）：
| 排序 | 平均时间 | 最坏 | 稳定 | 额外空间 | 实际价值 |
|---|---|---|---|---|---|
| 快排 | O(nlogn) | O(n²) | 不稳定 | O(logn) | ★★★ 最高 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(n) | ★★★ Tim Sort 基础 |
| 堆排 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | ★★ Top-K 场景 |
| 插入 | O(n²) | O(n²) | 稳定 | O(1) | ★★★ 小数据量王者 |
| 希尔 | O(nlogn) | O(n²) | 不稳定 | O(1) | ★ 知道原理就行 |
| 冒泡 | O(n²) | O(n²) | 稳定 | O(1) | ✗ 教学用 |
| 选择 | O(n²) | O(n²) | 不稳定 | O(1) | ✗ 教学用 |
| 桶/计数 | O(n+k) | O(n+k) | 稳定 | O(k) | ★★ 特定场景 |
网上很多教程的总结表把归并的额外空间写成 O(1)、桶排序写成 O(1)，都是错的。归并需要临时数组 O(n)，桶/计数排序需要计数数组 O(k)。
所以面试该重点准备哪些？
快排（必手撕）、归并（必手撕）、堆排（理解 + Top-K ）、插入排序（能说出小数据量优势）。其余的知道原理和复杂度就行，别花时间手写。
原文有完整的 Java 代码实现（八种排序全有），在我博客上 tanqingbo.cn/Eight-sorting-algorithms ，需要的自查。
Select Language