面试的时候八大排序倒背如流，工作几年后发现实际开发里真用得上的就那么两三个。整理一下哪些该深挖、哪些面试背完就得了。

先放结论：实际开发 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 ，需要的自查。