如果让我列一份程序员最熟悉的陌生算法清单排序绝对排第一。你会调Arrays.sort能背出冒泡和快排的流程但一旦真让你在白板上把八大排序一个一个写出来很多人当场就会露馅——快排分区写成死循环、归并的临时数组开错位置、稳定的排序被写得不稳定、有序数组直接让快排退化成平方级。八大排序这个题目看起来是面试八股实际上是把递归、分治、数据结构、复杂度推导和工程取舍一次性全考一遍这也是为什么它永远出现在面试题和算法课里。这篇文章我打算从实现角度把八大排序逐个拆开用 Java 给出可以直接跑的版本把每个算法的复杂度来源讲清楚再补一张直观的对比表和一组工程选型建议最后聊聊我自己手写排序时踩过的坑。你如果正在准备算法面试或者被要求手写排序但心里没底这篇应该能帮你把背代码变成真的懂。1. 八大排序是哪八个以及理解它们的三把尺子1.1 这八个成员都是谁八大排序并不是按同一流派统一归纳出来的组合它是面试、算法课和工程实践中高频出现的一集散装算法冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序。这八个算法覆盖了完全不同的三种思路前三个是朴素的比较 交换/移动靠两两比较逐步把序列排好希尔是插入排序的进阶版通过大步长分组让序列先接近有序归并、快排、堆是分治思想或堆数据结构在排序上的典型应用计数排序则彻底跳出比较的框架直接统计值出现的次数。把这八个混在一起学容易乱但只要你抓住每类算法解决什么问题、用什么代价解决它们之间的关系就清楚了。这也是我下面第 2 章要做的分档。1.2 评价排序算法的三把尺子任何排序算法工程上就看三个维度。时间复杂度算法在大规模数据下跑得快不快通常看平均复杂度和最坏复杂度。比如快排平均 O(n log n)但最坏会退化到 O(n²)这是选型时必须知道的隐患。空间复杂度排序过程额外占多少内存。原地排序比如快排、堆排几乎不占额外空间归并排序每次要开一块长度等同于区间的临时数组处理海量数据时内存开销不可忽略。稳定性如果两个相等元素在排序后保持原有先后顺序这个排序就是稳定的。很多人觉得稳定性没卵用但等你做多关键字排序的时候就会发现不稳定算法会在你完全没意识到的情况下打乱之前排好的顺序。这一点我在第 4 章专门展开。这三把尺子对应你到底该在什么场景用哪种排序。背下所有实现不代表会选型但理解这三个维度之后选型就是自然的事。2. 先按复杂度把八大排序分成三档思路就顺了抛开具体代码不谈八大排序的复杂度分布在三个层级上按层级学习会比逐个死记高效得多。2.1 O(n²) 档冒泡、选择、插入这三个算法都是两重循环的老实人平均复杂度 O(n²)适合小规模数据和教学入门。冒泡的价值在于它是相邻比较最直观的写法而且带提前终止优化后对基本有序的数组能降到 O(n)。选择的特殊点在于它的交换次数是所有排序中最少的——无论如何最多交换 n-1 次就能把整个数组排好写起来也最不容易出错。插入排序则是三个里面工程价值最高的。它实现简单、常数极小对近乎有序的数组可以跑到 O(n)所以 Timsort 和 JDK 的对象排序里对小规模子序列用的就是插入排序。很多新手低估它实际上它是 O(n²) 档里唯一值得在正式代码里出现的算法。2.2 希尔排序的位置有点特殊希尔排序是插入排序的升级版先按大步长分组做插入排序不断缩小步长最后一趟步长为 1 时整个数组已经接近有序插入排序退化为近乎 O(n)。理论上它没有稳定地进入 O(n log n) 档平均复杂度取决于步长序列的选择常见实现约在 O(n^1.3) 左右。它属于比 O(n²) 快一截、但很难说清确切复杂度的中间派。考虑到它代码量只比插入排序多一层循环实战里想原地排序又不想写归并的时候希尔是个不错的折中。2.3 O(n log n) 档归并、快排、堆这是工业界的绝对主角三种算法都能达到 O(n log n)但性格完全不同。归并排序稳定、复杂度恒定代价是额外 O(n) 空间实现是典型的分治流程。它对链表尤其友好——链表归并不需要额外空间只要调整指针。快排是综合常数最小的原地排序JDK 对基本类型的排序就是基于快排双轴快排但它最怕有序数组和固定选 pivot 的组合会退化到 O(n²)。堆排序用最大堆的堆顶必然是最大值这一点每次把堆顶挪到末尾最坏也是 O(n log n) 且原地但常数偏大实际速度通常不如快排。我自己的经验是三个 O(n log n) 里最需要手写熟练的是快排和归并因为它们的分治模板在其它算法题里也大量复用堆排序更多考察你对堆这个数据结构的理解。2.4 计数排序跳出比较框架的另类计数排序的时间是 O(nk)k 是数据范围它压根不比较元素大小而是把每个值出现的次数统计到数组里再按次数回填。正因为不做比较它突破了比较排序最好 O(n log n)的下界。当然它有前置条件数据必须是有确定范围、比较密集的整数。你给一组小数或者范围大到 2^31 的数据计数排序立刻原地爆炸。它更大的意义是作为基数排序的地基。3. 逐个手写实现代码、复杂度推导和易错点都放在这下面按从简单到复杂的顺序给实现。所有代码我都是用 Java 写的用其它语言也完全能对上思路。3.1 冒泡与选择两种老实人写法冒泡排序的代码非常好懂public static 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]) { swap(a, j, j 1); swapped true; } } if (!swapped) break; // 这一轮没交换说明已经有序 } }复杂度推导很简单最外层跑 n-1 轮第 i 轮内层比较 n-1-i 次总比较次数约 n(n-1)/2所以平均和最坏都是 O(n²)。加了swapped提前中断后输入已经有序时外层只跑一轮最好变成 O(n)。注意两个细节相等时不要交换否则稳定被破坏内层循环的i是已经冒到末尾的元素个数j的上限要减掉它。选择排序则是每轮找到剩下部分的最小值放到当前位置public static void selectionSort(int[] a) { for (int i 0; i a.length - 1; i) { int minIdx i; for (int j i 1; j a.length; j) { if (a[j] a[minIdx]) minIdx j; } if (minIdx ! i) swap(a, i, minIdx); } }它的复杂度是严格的 O(n²)因为无论输入是否有序内层比较一次都不能省。但它的交换次数不多于 n-1 次适合交换成本远高于比较成本的极端场景。选择排序为什么不稳定举个例子[5a, 5b, 1]第一轮找到最小值 1和位置 0 的 5a 交换5a 就跑到 5b 后面去了。这个例子我在面试里被问到过希望你也记住。3.2 插入与希尔从局部有序到大步逼近插入排序的核心思想跟打扑克理牌完全一样——把新摸到的牌插到手里已经排好序的牌里。public static void insertionSort(int[] a) { for (int i 1; i a.length; i) { int cur a[i]; int j i - 1; while (j 0 a[j] cur) { a[j 1] a[j]; j--; } a[j 1] cur; } }每次把cur前面的元素逐个右移找到它的正确位置放回去。最好情况是数组已经有序while 循环一次都不进整体只有一层循环复杂度 O(n)。最坏和平均都是 O(n²)。实现时最容易犯的错是把a[j] cur写成a[j] cur。后者会让相等元素也产生移动破坏稳定性。另外j 0和a[j] cur的顺序不能反过来否则 j 已经变成 -1 时会抛数组越界。希尔排序就是在插入排序外套一层递减的 gappublic static void shellSort(int[] a) { for (int gap a.length / 2; gap 1; gap / 2) { for (int i gap; i a.length; i) { int cur a[i]; int j i - gap; while (j 0 a[j] cur) { a[j gap] a[j]; j - gap; } a[j gap] cur; } } }gap 从 n/2 开始每次减半每一轮把相距 gap 的元素看作一组做插入排序。因为插入排序对接近有序的序列很快希尔就是先通过大步长让序列快速趋向有序最后一轮 gap1 时已经省了大量移动。希尔的不稳定性来自分组两个相等的 key 可能被分到不同的 gap 组里跨越多个位置交换相对顺序就没法保证。复杂度推导比较麻烦常见实现约在 O(n^1.3) 附近不同的 gap 序列会产生不同的复杂度表现。3.3 归并与快排分而治之的两条路线归并排序的分治逻辑很干净先让左半边有序再让右半边有序最后两个有序子序列合并成一个。递归终止条件是区间只剩一个元素。public static void mergeSort(int[] a, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, left, mid); mergeSort(a, mid 1, right); merge(a, left, mid, right); } private static void merge(int[] a, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { temp[k] a[i] a[j] ? a[i] : a[j]; } while (i mid) temp[k] a[i]; while (j right) temp[k] a[j]; System.arraycopy(temp, 0, a, left, temp.length); }复杂度推导每次对半分递归深度是 log n 层每层合并的总代价是 O(n)所以总时间是 O(n log n)最好最坏都一样。空间复杂度是 O(n)因为每层合并都需要临时数组存放有序结果。注意int mid left (right - left) / 2而不是(left right) / 2后者在 left 和 right 都很大的时候可能溢出。这块代码我在第 6 章还会提到它的一个性能坑。快速排序则是另一个思路先选一个 pivot把小于 pivot 的元素放到它左边、大于的放右边这样 pivot 在本次分区后位置就固定了再递归排两侧。public static void quickSort(int[] a, int left, int right) { if (left right) return; int idx partition(a, left, right); quickSort(a, left, idx - 1); quickSort(a, idx 1, right); } private static int partition(int[] a, int left, int right) { int pivot a[right]; int i left; for (int j left; j right; j) { if (a[j] pivot) { swap(a, i, j); i; } } swap(a, i, right); return i; }partition 的逻辑是用i记录小于 pivot 的元素应该放到的位置遍历j发现a[j]小于 pivot 就把它换到 i 位置并 i。最后把 pivot 从 right 换到 ii 就是 pivot 的最终位置同时也是左右分区的分界线。复杂度上理想情况每次对半分递归 log n 层每层遍历 n 个元素平均 O(n log n)。最坏情况比如数组已经有序且每次都选最后一个元素当 pivot每次分区只能消掉一个元素递归深度变成 n总时间退化 O(n²)。快排的不稳定性来自交换跨越相等的元素在分区时可能被 swap 到另一个相等元素后面相对顺序无法保留。这些内容我在避坑章节还会再展开。3.4 堆排序用堆这个数据结构换来的 O(n log n)堆排序的思路浓缩成一句同一个数组先把它整理成一个大顶堆然后每次把堆顶也就是当前最大值和数组末尾交换再把剩余部分重新调整成堆。每轮确定一个最大值到末尾n 轮搞定。public static void heapSort(int[] a) { int n a.length; for (int i n / 2 - 1; i 0; i--) { siftDown(a, i, n); } for (int i n - 1; i 0; i--) { swap(a, 0, i); siftDown(a, 0, i); } } private static void siftDown(int[] a, int i, int n) { while (i n / 2) { int child 2 * i 1; if (child 1 n a[child 1] a[child]) child; if (a[child] a[i]) break; swap(a, i, child); i child; } }n / 2 - 1是最后一个非叶子节点的下标从它开始往前逐个 siftDown才能在 O(n) 时间里完成建堆。这个 O(n) 很多人不理解直觉以为每次 siftDown 是 O(log n)n/2 个节点是 O(n log n)但叶子更多、非叶子更少且越靠近堆顶节点越少算总账后是 O(n)。后面每轮交换堆顶和末尾再对堆顶 siftDown 一次是 O(log n)n-1 轮加起来 O(n log n)所以整体 O(n log n)。空间上完全原地只有递归/循环里的常数开销这是它和归并本质的区别。堆排序不稳定很好解释堆顶元素会与数组末尾元素交换这个远距离交换会把相等元素的相对顺序打乱。比如两个相等的最大值一个在堆顶一个在堆里堆顶先被换到末尾另一个后来才被换到它前面。3.5 计数排序跳出比较框架的另类计数排序用一句话说就是先数出每个值出现了多少次再根据次数把值填回数组。public static void countingSort(int[] a) { int min a[0], max a[0]; for (int v : a) { if (v min) min v; if (v max) max v; } int[] count new int[max - min 1]; for (int v : a) count[v - min]; for (int i 1; i count.length; i) count[i] count[i - 1]; int[] temp new int[a.length]; for (int i a.length - 1; i 0; i--) { temp[--count[a[i] - min]] a[i]; } System.arraycopy(temp, 0, a, 0, a.length); }这个版本做了两件事第一偏移处理——用min把数据映射到从 0 开始的下标所以支持负数也不浪费太长的数组第二前缀和保证稳定——count做完前缀和后count[v - min]表示小于等于 v 的元素有多少个从后往前填是为了让相同值的元素按原顺序填入最终位置这样计数排序就是稳定的。复杂度上找最值 O(n)统计 O(n)前缀和 O(k)回填 O(n)总时间 O(nk)。空间用了count和temp两个数组O(nk)。如果你不需要稳定可以直接遍历 count 数组覆盖回原数组空间能省掉 temp。但既然计数排序常用的地方是基数排序的底层稳定版本更有用所以这里给的是稳定版实现。4. 稳定性排序算法里最容易被低估、却在业务里最致命的一环4.1 什么是稳定排序稳定性说的是两个相等的元素排序前 a 在 b 前面排序后如果 a 仍然在 b 前面这个排序就是稳定的如果位置反了就是不稳定的。注意稳定的定义只针对相等元素不相等元素的顺序本来就要改变跟稳定性无关。为什么要关心这个最常见的场景是多关键字排序。比如系统里订单列表业务方要求先按创建时间升序同一时间内再按订单金额降序。你的自然做法是先按金额排序再按时间排序。如果第二步按时间排序用的是不稳定算法那么同一时间里的订单金额顺序就被打乱了结果跟着错。这就是上一个排序的结果被下一个不稳定排序破坏的典型踩坑现场。4.2 八大排序稳定性一览我把八大排序的稳定性整理一下排序稳定性原因简述冒泡稳定相邻比较相等时不交换选择不稳定最小值和远处元素直接交换可能跳过相等元素插入稳定严格大于才移动等于时保持原位插入希尔不稳定分组跨越移动相等元素可能被分到不同组归并稳定合并时左半先出相等时优先取左半快排不稳定分区交换会跨越多个相等元素堆排序不稳定堆顶与末尾元素远距离交换计数稳定前缀和 从后往前填保证相同值原序十个字总结稳的是冒泡、插入、归并、计数不稳的是选择、希尔、快排、堆。这里有个面试常考点归并排序为什么稳定因为在合并时如果左右两边的元素相等我们总是先拿左边的所以相等元素的相对顺序被保留。代码里那句a[i] a[j] ? a[i] : a[j]就是稳定的关键——用而不是。4.3 一个会真实发生的业务事故我记得有次做一个对账报表线上导出数据后用户反馈同一天的记录顺序和页面上不一致。排查到最后发现是同事在组装报表时用了快排做二次排序而它把之前按时间排好的顺序打乱了。这类 bug 非常隐蔽因为它不是崩溃也不是数据错误而是顺序看起来不对。如果刚好遇上需要严格顺序的导出场景比如银行流水、批次对账、按时间追溯一次不稳定排序足以让整份报表返工。从那之后我写排序代码第一反应就是确认这个问题要不要稳定要稳定就选归并或直接给对象加一个序号字段做 tie breaker。5. 一张总表加一个选型思路别背快排最快这种口诀5.1 八大排序全参数对比把第 3 章的复杂度推导汇总成一张表方便你面试前快速过排序平均最好最坏空间稳定性实现难度冒泡O(n²)O(n)O(n²)O(1)稳定低选择O(n²)O(n²)O(n²)O(1)不稳定低插入O(n²)O(n)O(n²)O(1)稳定低希尔O(n^1.3) 左右O(n)随步长序列可达 O(n²)O(1)不稳定中归并O(n log n)O(n log n)O(n log n)O(n)稳定中快排O(n log n)O(n log n)O(n²)O(log n)~O(n)不稳定中堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定中计数O(nk)O(nk)O(nk)O(nk)稳定低几个容易记错的点快排空间复杂度是递归栈的 O(log n)不是 O(1)希尔最坏复杂度不固定取决于 gap 序列计数排序空间如果只要稳定版就是 O(nk)纯遍历覆盖可以只留 O(k)。5.2 选型准则按工程经验我会按下面几条走基本已经覆盖绝大多数场景。数据量很小几十个以内直接插入排序。代码最短、常数最小快排这种带递归调度的算法在小数据上反而吃亏。数据接近有序插入排序它能在 O(n) 里完成其它 O(n log n) 算法在这种场景下跑不过它。必须稳定选归并对象排序场景通常也是 Timsort 的活。如果做链表排序归并更是首选因为链表归并不需要额外空间。内存受限选堆排序或快排。堆排序最坏也是 O(n log n)但常数大快排正常更快但要处理好 pivot 才能避免最坏退化。数据范围已知且 k 远小于 n计数排序比如对 10 万个 0~100 的分数排序O(nk) 直接秒杀所有比较排序。没有特殊要求直接用 JDK 的Arrays.sort。它对 int 等基本类型用双轴快排对对象用 TimSort库函数已经针对各种场景做过深度优化。面试之外手写排序的机会其实很少选型的意义更多在于你知道库里在用什么以及为什么。6. 手写排序时最容易踩的五个坑这一章是我实际写代码、看同事代码、帮别人查 bug 过程中踩过和见过的坑拿出来集中说一遍省得大家再走弯路。6.1 快排固定 pivot 遇上有序数组上面 3.3 的快排实现里pivot 固定取最后一个元素。数组有序时每次分区后 pivot 正好是最大值右侧分不到元素问题退化成 n (n-1) ... 次比较就是 O(n²)。更糟的是递归深度变成 n甚至可能栈溢出。我见过不少人拿这个实现去跑大数据量结果直接 StackOverflow还以为是代码写错了。工程上最常见的解法是三数取中取 left、mid、right 三个位置的中位数作为 pivot这样最坏情况基本不会出现在现实数据上。也可以用随机 pivot避免恶意构造有序序列。面试时如果你把这个优化说出来含金量会明显高于只写一个基础 partition。6.2 归并排序反复 new 临时数组3.3 的写法里每次merge都new int[right - left 1]。从功能上看没有任何问题但从性能上看一次排序要创建 O(n log n) 个不同大小的临时数组GC 压力巨大。数据量到几十万就明显可以看到耗时飙升。优化是排序开始前一次性创建好一个长度等于原数组的temp层层传入 mergepublic static void mergeSort(int[] a) { mergeSort(a, new int[a.length], 0, a.length - 1); } private static void mergeSort(int[] a, int[] temp, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(a, temp, left, mid); mergeSort(a, temp, mid 1, right); merge(a, temp, left, mid, right); }merge 里不再 new只往temp里写对应区间。JDK 对象排序的底层也是这个套路你可以把它当作标准答案。6.3 堆排序的 siftDown 写错方向堆排序最容易错的地方是把siftDown下沉写成向上冒泡。建堆和堆顶交换后的调整逻辑都是从某个节点往下看把较大的子节点换上来方向必须是向下的。我第一次写堆排序时把调整写成 while 向上循环结果建出来的堆根本不成形排序结果乱成一团。另外child 1 n a[child 1] a[child]这行的顺序也有讲究先假设左孩子更大再看右孩子存不存在且更大如果存在就切换到右孩子。漏掉child 1 n越界了才知道错。6.4 计数排序忘了偏移和负数直接拿数组元素当下标遇到负数会立刻炸因为下标不能是负数。遇到最大值特别大的数据比如 100 万和 100直接开new int[max]内存也会被白白浪费一大截。正确做法是先扫描一遍找 min 和 max所有下标都减去 min。这样负数变成了非负索引数组长度也压缩到max - min 1两全其美。我在前面 3.5 的实现里已经把这个处理写进去了。6.5 插入排序的边界和稳定性细节插入排序里我见过有人把while (j 0 a[j] cur)写成while (a[j] cur j 0)。看起来只是顺序不同但j减到 -1 时前者因为短路根本不会执行a[-1]后者会直接数组越界。还有一个隐藏细节和决定了稳定性。用相等元素也会被往右移新元素会跑到相等元素前面排序结果就不稳定了。用严格大于相等时不动新元素插入到它们后面稳定性就保住了。两字符的差别很多人写完了根本不知道自己写错了排序的稳定性。最后分享一个个人经验。我以前带一个学弟做导出功能他图省事把 Redis 里取出来的数据直接用Arrays.sort排了一遍却忽略了业务要求先按时间升序、再按优先级降序的多关键字顺序。Arrays.sort对对象用的是 TimSort稳定所以结果碰巧是对的。但如果他换成对基本类型数组排序或者语言/库的排序不稳定整份报表顺序就会对不上。从那以后我写任何排序都会先问三个问题数据量多大要不要稳定键的分布是什么样这三个问题问完选型根本不用背口诀。排序这个东西真正难的从来不是写出来一种而是知道在哪种场合用哪一种并且能说出为什么。