拓冰网站定制 
前阵子帮同事 review 代码发现线上一个模块里他用三层 for 循环手写了一个“冒泡排序”去排用户列表。我问他为什么不用现成的 sort他说怕库排序不稳定改了排序结果。这让我有点感慨很多写了好几年业务的同学对排序算法的理解还停留在“背代码应付面试”的阶段真正到了要选型、要解释为什么用这个不用那个的时候就抓瞎了。排序这东西说难不难说简单也不简单。说难是因为如果只看教科书上的代码冒泡、选择、插入、希尔、归并、快排、堆排、计数这八种挨个背一遍很容易背了就忘。说简单是因为只要你理解了每种排序到底在“怎么组织数据”“用了什么策略”你会发现它们之间有一条清晰的演进脉络根本不需要死记硬背。这篇文章我想用工程实践的角度把这 8 种常见排序算法从原理、代码到选型逻辑串一遍顺便把我在实际开发和面试里踩过的坑、总结的经验放进去。目标读者是两类人一类是正在准备数据结构期末复习或者面试的在校生另一类是写业务工作两三年、想系统把排序这块补扎实的同学。看完你至少能做到三件事手写核心实现不慌、别人问你为什么不稳定能答上来、遇到真实排序需求知道该选谁。1. 排序算法到底在学什么先避开两个误区1.1 误区一背代码不等于会排序我见过大量同学准备排序算法的方式是打开博客复制快排代码背下来面试现场默写。这种做法最大的问题是一旦面试官把“对数组排序”改成“对链表排序”或者改成一个自定义的比较规则很多人就懵了。排序算法的核心不是那几行代码而是三个问题的答案每一轮做了什么为什么这样做能逼近有序这个做法的代价是什么以冒泡排序为例。如果你只是背“外层循环 n-1 次内层循环 n-1-i 次相邻比较交换”那你没有真正理解它。真正的理解是“每一轮让一个未归位的最大元素通过相邻交换‘冒’到它最终该在的位置”。有了这层理解你自然会推出优化方案——如果某一轮没有任何交换说明数组已经有序直接结束。所以这篇文章里每种算法我都会先讲“它在干嘛”再给代码。代码只是结果思想才是要学的东西。1.2 误区二只盯着时间复杂度很多人评价排序算法只会一句话“快排最快Bubble 最慢。”这个认知在刷题场景下没问题但工程上一旦落到真实需求会踩大坑。时间复杂度描述的是数据量趋于无穷时的增长趋势但真实场景里数据量往往没到那个量级此时常数项、空间开销、稳定性、递归深度、甚至 CPU 缓存命中率都可能比理论复杂度更影响最终效果。举一个我实际遇到的例子一个服务里需要对某个长度在 100 到 200 之间的分页结果排序。有人坚持用快排理由是“快排平均 O(n log n) 最牛”。但测试发现这个规模下插入排序反而更快因为插入排序常数极小、局部性又好而且完全不需要递归。最后我把代码改成在数据长度小于 60 时走插入排序P99 延迟降了差不多 15%。这不是说快排不好而是说选排序算法是一个系统工程要看的维度远不止时间复杂度一个。稳定性、空间复杂度、数据本身是否近乎有序这些都是关键变量。我后面会用一整节专门讲工程选型。2. 热身组冒泡、选择、插入简单不意味着可以写错2.1 冒泡排序最直观的交换思想隐藏着一个优化点冒泡排序的思路是最朴素的从前往后扫描把相邻的两个元素中较大的那个往后换一轮下来最大的元素就“冒”到了最后面。重复这个过程每轮少看一个元素直到全部排完。基础写法void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } }这个版本能跑但有个明显的浪费如果数组在第一轮就已经有序它依然会继续跑 n-1 轮。加一个标志位就能解决void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }这个优化让冒泡排序的最好情况从 O(n²) 降到了 O(n)——当传入数据本身就是有序时第一轮扫描发现没有任何交换直接跳出。这个细节在很多面试题里会作为“你还有什么优化空间”的追问出现。稳定性上冒泡排序是稳定的因为只有在arr[j] arr[j1]时才交换相等元素不会交换位置。这一条务必记牢后面有一节专门讲稳定性的意义。2.2 选择排序交换次数最少却可能不稳定选择排序的思路是另一路每一轮找到未排序区间里的最小元素把它放到当前区间的最前面。相比冒泡排序的“频繁相邻交换”选择排序每轮最多只做一次交换总共最多交换 n-1 次。void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIndex i; for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } if (minIndex ! i) { swap(arr, minIndex, i); } } }这里有个细节值得展开如果数组元素是体积很大的对象排序过程中“比较”通常比“交换”便宜得多比较只读几个字段交换可能要移动整块数据。选择排序每轮只交换一次这个特性在“写操作代价高”的场景里很有价值。比如你在内存里排序一批 MySQL 记录的游标每个元素背后挂着几十个字段的引用这时候选择排序的交换次数优势就会被放大。但选择排序有个硬伤——它不稳定。常见解释是“最小元素和当前位置交换可能跨过多个相同元素导致相对顺序改变”。我给出一个最直观的例子数组[5a, 8, 5b, 2, 9]为了区分两个 5我加了标记 a 和 b。第一轮找到最小值 2把 2 和第一个位置的 5a 交换变成[2, 8, 5b, 5a, 9]。两个 5 的相对顺序变成了 b 在前 a 在后这就破坏了稳定性。理解这一点很重要因为很多教材只说“选择排序不稳定”却不说为什么。我建议你自己动手走一遍这个过程比背十遍结论都管用。2.3 插入排序处理“几乎有序”数据的一把好手插入排序是最接近人类本能的一种排序思路——就像你打扑克牌时摸到一张新牌会和手里已有的牌从右往左比较找到合适的位置插进去。void insertionSort(int[] arr) { int n arr.length; for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这个代码看似简单但有两个地方是面试高频追问点。第一个是内层循环的条件。必须是arr[j] key不能写成arr[j] key。如果写成了大于等于相等的元素会被强行往前移破坏稳定性。很多人在白板写代码时下意识写错这一行就是分水岭。第二个是它的时间复杂度特点。插入排序在最好情况数组已经有序下只需要一层循环比较每轮发现key已经大于前一个元素直接跳过内层循环所以最好情况是 O(n)。这个特性让它成为“近乎有序”数据的最佳选手——比如一个系统日志列表大部分时间戳本来就是有序的只有偶尔几条新插入的记录乱序这时候插入排序几乎就是 O(n) 级别的表现。这也是为什么 Java 的Arrays.sort在底层处理小数组时会把归并排序切回插入排序。不是插入排序比归并厉害而是当 n 很小时插入排序的低常数项优势远远超过了归并排序的理论复杂度优势。后面讲归并和工程选型时我会把这个逻辑串起来。3. 进阶组希尔、归并、快排、堆排序为什么它们能快那么多3.1 希尔排序插入排序的升级版插入排序有个明显的短板如果一个很小的元素在数组最后面它要一步一步地往前挪这趟路很长。希尔排序的思路是先让元素“跳着走”在相隔较远的位置之间做插入排序缩小“路途”等整体大体有序后再做一次普通插入排序。希尔排序的关键是步长序列gap 序列。我给出一个最常见、也最好写的版本初始 gap 为数组长度的一半每次减半直到 gap 为 1。void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i; while (j - gap 0 arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } }理解这段代码的关键是gap 为 g 时你其实是在同时对 g 个子序列分别做插入排序。比如 gap 4 时位置 0, 4, 8… 是一组位置 1, 5, 9… 是另一组以此类推。每个子序列内部使用插入排序由于每个子序列的元素数量只有总长度的 1/g整体开销大幅下降。随着 gap 不断缩小子序列数量变少、长度变长但数据已经越来越接近有序插入排序的“近乎有序”优势开始发挥。希尔排序的时间复杂度取决于 gap 序列的选择。简单减半序列的平均复杂度大致在 O(n^1.3) 附近这档最坏情况下仍是 O(n²)比如某些经典序列。实践中更优秀的增量序列有 Hibbard 序列、Sedgewick 序列等它们能把最坏复杂度压到 O(n log n) 量级但实现复杂一些一般考试和面试不会要求。稳定性方面希尔排序是不稳定的。因为元素在按 gap 跳跃时相同大小的元素可能被分到不同的子序列里然后在后续过程中相对位置发生交错。这个问题和选择排序不稳定一样属于“结构上注定”的不是写坏了。3.2 归并排序稳定的分治选手归并排序是我个人最喜欢给新人讲的一种算法因为它把“分治”思想体现得最干净把一个数组从中点切开分别排好两个子数组再把两个有序数组合并成一个有序数组。递归到底层一个元素天然有序所以关键在于“合并有序数组”这一步。void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid (left right) 1; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } void merge(int[] arr, 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) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int p 0; p temp.length; p) { arr[left p] temp[p]; } }稳定性写在merge函数的那个if里当左边元素小于等于右边元素时先取左边的。这样相等元素的相对顺序在合并过程中不会改变所以归并排序是稳定的。如果你把写成稳定性的结论就不成立了——这是很多细节控面试官喜欢挖的点。归并排序的最大代价是空间。每次合并都要申请一个长度和当前区间相同的临时数组最终递归过程中总的空间复杂度是 O(n)。这不是小开销在内存紧张的嵌入式环境里可能直接不适合用。但归并排序有一个相当重要的工程应用外部排序。当数据量大到无法全部加载进内存时只能对磁盘里的数据分块排序再不断归并这些块整个思路就是归并排序的扩展。另外对链表排序时归并排序因为不需要随机访问数据而且链表上做归并不需要额外数组空间只需要改指针反而是最合适的选择。如果要在归并这里记一句心得我建议记这句递归思想看归并原地性能看快排。3.3 快速排序性能好但不稳定pivot 选择是灵魂聊排序绕不开快排。它也是分治思想但和归并排序的区别在于归并排序的难点和重点是“合”而快排的重点在“分”。快排的做法是选一个基准值pivot把数组分成“比 pivot 小的”和“比 pivot 大的”两部分然后对这两部分递归做同样的事情。void quickSort(int[] arr, int left, int right) { if (left right) { return; } int p partition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p 1, right); } int partition(int[] arr, int left, int right) { int pivotIndex left (right - left) / 2; swap(arr, pivotIndex, right); int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, right); return i; }这个partition用的是 Lomuto 分区方案逻辑简单i指向“比 pivot 小的区域”的下一位置j从 left 扫到 right-1遇到比 pivot 小的就放进 i 的位置。最后把 pivot 换到 i 处。这种方式笔试写起来容易但它有个不足当数组里有很多重复元素时它会做大量无意义的交换此时三路快排把等于 pivot 的单独放中间更好。快排最关键的工程问题是 pivot 怎么选。上面这个例子我直接取了中间位置这在绝大多数情况下表现可以但如果你取的是数组的第一个或最后一个元素并且输入数组恰好是近乎有序的分区结果会严重偏斜递归深度接近 n时间复杂度退化到 O(n²)。解决办法有三个思路第一是随机化 pivot。每次在区间里随机选一个位置和末尾元素交换这样最坏情况出现的概率被摊薄了。第二是三数取中法。取区间首、中、尾三个位置的元素选这三个数的中间值作为 pivot能有效避免有序数组的退化问题。第三是内省排序。设置一个递归深度阈值当递归深度超过 2 log n 时切换到堆排序兜底。C 的std::sort实际就是用的第三种策略这是快排在工程里的终极版本。快排不稳定的原因很直接partition过程中有大量的跨区间交换相等元素的相对顺序完全可能被打乱。所以如果需求要求排序后相同元素的先后顺序不能变快排不能直接用哪怕它平均性能再好也不行。3.4 堆排序原地排序里的大块头堆排序的思路是借用一个数据结构而不是一种新的“排序思想”。它的分治意识没那么强更多是“反复取出堆顶”的逻辑把数组调整成一个大顶堆堆顶就是最大值把它和当前末尾元素交换然后把堆的大小减一再调整重复这个过程。void heapSort(int[] arr) { int n arr.length; for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } for (int i n - 1; i 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i); } } void siftDown(int[] arr, int i, int n) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest ! i) { swap(arr, i, largest); siftDown(arr, largest, n); } }这段代码里最容易被忽略的是siftDown的边界条件。建堆时i从n / 2 - 1开始是因为这个位置正是最后一个非叶子节点的索引对于 0 起始的完全二叉树叶子节点从n / 2开始。从下往上做下沉调整才能让所有子树先有序建堆总开销是 O(n)这个结论很多人记不住但它是堆排序的亮点之一堆排序在堆有序时也不会有额外开销复杂度在最坏、最好、平均情况下都是 O(n log n)。我不止一次看到有人写堆排序时把largest的初始值写成0这是从示例代码里照抄的坏习惯——siftDown被递归调用时当前节点不一定是 0。每次进入函数largest必须先等于i当前子树的根再和左右孩子比较更新。这种细节看似不起眼却直接决定代码对不对。堆排序的空间复杂度是 O(1)是“原地排序”里性能最稳定的大哥但它在实际工程中的使用频率远低于快排和归并。原因有两个一是它的常数项较大siftDown过程虽然只有 O(log n) 次操作但每次操作都要算左孩子右孩子索引CPU 缓存命中率不如快排二是不稳定。所以堆排序适合的场景通常是要求原地排序、不允许额外空间、同时不要求稳定性的情况。4. 计数排序不靠比较的排序如何突破 O(n log n)4.1 为什么比较排序快不过 O(n log n)前面写到的七种排序本质上全是“基于比较”的排序。它们的通用决策过程是每次比较两个元素得到一个“谁大谁小”的信息然后据此调整位置。你可能会想为什么找不到一种比较排序能突破 O(n log n)那是因为 N 个元素的排列有 N! 种可能每次比较最多只能帮你排除一部分可能性理论上你至少需要 log2(N!) 次比较才能唯一确定排列顺序而 log2(N!) ≈ N log2 N。这个基于决策树的证明是所有基于比较的排序算法不可逾越的天花板。那有没有办法绕过这个天花板有。思路是放弃“比较”这个动作。4.2 计数排序的完整实现与两个容易踩的坑计数排序的思路是既然比较太贵那我干脆不比较。先统计每个值出现了多少次再根据统计信息直接把每个元素放到它该在的位置上。它的前提是数据范围max - min不能太大而且数据最好是整数。void countingSort(int[] arr, int min, int max) { int k max - min 1; int[] count new int[k]; for (int v : arr) { count[v - min]; } for (int i 1; i k; i) { count[i] count[i - 1]; } int[] output new int[arr.length]; for (int i arr.length - 1; i 0; i--) { int v arr[i]; output[count[v - min] - 1] v; count[v - min]--; } System.arraycopy(output, 0, arr, 0, arr.length); }这里面有两个坑我都在真实代码里踩过。第一个坑是负数数据。很多人写的计数排序只支持从 0 开始遇到负数就数组越界。解决办法就是上面代码里的min参数统计时下标用v - min这样即便最小值是 -100000也能正常处理。映射回原值时再加回min。本质上就是把数据整体“平移”到从 0 开始的区间。第二个坑是稳定性。如果你只是统计出现次数然后从头到尾填回原数组排序结果是对的但相同值的元素相对顺序会被打乱。要让计数排序稳定必须用“累加 从后往前放”这个写法count数组先做前缀和让count[v - min]表示“小于等于 v 的元素个数”然后从原数组的末尾开始遍历每遇到一个元素 v就放到output的第count[v - min] - 1个位置同时把对应的计数减一。这样保证了顺序和原数组一致。计数排序的时间复杂度是 O(n k)其中 k 是数据范围。当 k 远小于 n 时它是严格快于任何比较排序的而且这还是稳定排序。一个经典的面试例子给 0 到 100 分的考试分数做排名数据量有上万人计数排序只需要一个长度为 101 的计数数组效率碾压快排。不过它确实有两个硬性限制第一只能用于整数或者可以映射到整数且大小范围可控的数据第二如果 k 非常大比如要对 32 位整数排序计数数组直接爆内存这时候应该用基数排序等其他线性排序方案但基数排序不在今天的 8 种清单里感兴趣可以自己延伸看。5. 八种排序一张表复杂度、稳定性与适用场景5.1 八种排序算法复杂度对照表理论说了这么多落到一张表上最直观。这张表建议保存下来无论是期末复习还是面试前突击先把它背明白再去抠代码细节。排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序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(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 log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(k)稳定5.2 怎么读懂这张表这张表里最有信息量的不是时间复杂度那几列而是“稳定性”这一列。很多人不理解稳定性到底有什么用我给一个特别经典的真实业务例子你要给一批用户按“等级”从高到低排等级相同的人再按“注册时间”从早到晚排。如果只排一次那无所谓顺序只在这一次里定义。但常见做法是先按注册时间升序排一遍再按等级降序排一遍。如果第二次排序用的是不稳定的算法等级相同的人注册时间顺序会被打乱结果就错了。稳定排序保证了多次排序时上一次排序建立的相对顺序不会被破坏。这就是为什么后端排序用户列表时最后一步排序必须用稳定算法的原因。再细看最坏情况的快排O(n²)。这个结论让很多初学者恐慌那快排是不是根本靠不住事实是快排在工程里的“最坏情况”几乎可以通过随机化 pivot 和混合策略规避掉所以它依然是默认排序工具里最常被选用的那一档。大厂面试问“快排为什么快”通常是想听你讲出“分治 数据局部性 缓存友好”这三个层次而不是只背复杂度。还有希尔排序那一行我特意写了“取决于增量序列”。因为希尔排序的复杂度不像其他排序有统一结论不同增量序列差异很大。期末复习如果考到希尔务必先确认考试教材用的是哪个增量公式再决定填什么复杂度。6. 工程选型逻辑为什么成熟库从不只用一种排序6.1 一个排序函数背后的混合策略如果你打开 Java 的Arrays.sort源码会发现它内部根本不是单一的排序算法。对基本类型数组它用双轴快速排序对对象数组它用 TimSort一种对归并排序和插入排序的混合改进。Python 的sorted也是 TimSortC 的std::sort则是“快排 插入 堆排”的内省排序。为什么官方库要做这么复杂的混合因为没有任何一种排序算法在所有数据形态下都最优。TimSort 的思路特别值得我们工程师借鉴它先扫描数据里已经有序的片段run把这些天然有序的段直接保留再用归并的方式把它们合并起来。这个设计的价值非常明确——真实世界的数据里有大量“部分有序”的片段。用户列表按时间戳插入、日志按日期追加、成绩单按学号分组这些数据天然带有序结构。TimSort 把这些结构当作免费的午餐效率远高于对所有元素一视同仁的普通快排。我建议你把这个思路带到自己的代码里写排序之前先看看你的数据是不是“几乎有序”。如果是插入排序或者归并排序的变体可能会比无脑快排快得多如果不是再回归快排或 TimSort。6.2 工程中比算法实现更重要的三件事第一件事是明确排序需求的两个前提是否要求原地排序是否要求稳定。这两个前提直接决定了你的算法候选集。比如一个长列表但内存吃紧空间复杂度 O(n) 的归并排序可能直接出局又比如业务上需要保持上一次排序的相对顺序那么不稳定算法全部淘汰只能在冒泡、插入、归并、计数里选。第二件事是注意比较器的完整性和一致性。对自定义对象排序时很多人写的compare方法只比较了一个字段导致两个不同对象的字段相等时返回 0而在某些语言/库的实现里这会让两个“相等”的对象在排序后相对顺序变得不可预期。写比较器时请遵循返回值要和equals的结果保持一致否则就老老实实写一个明确的“决出胜负”的次级比较规则。第三件事是警惕递归深度带来的栈溢出。快排和归并排序在极端数据分布下递归深度都可能很深尤其快排遇到坏 pivot 时会退化到接近 n 层递归。生产环境里我见过因为排序导致栈溢出的线上事故解决方案有两个一是设置递归深度阈值超过就切堆排序兜底内省排序二是把递归写法改成迭代写法用显式栈模拟递归。我自己的一个习惯是在排序函数入口处先处理边界条件数组为空或长度为 1 时直接返回。这个判断看似微不足道却能在框架里减少很多无意义的递归调用。很多从示例代码复制粘贴的同学恰恰漏了这两行。6.3 我的自测清单与学习建议如果你现在准备复习排序算法我分享一份我当年用过的自测清单按顺序过一遍基本能确认自己对这 8 种算法是真懂还是假懂能不能不看代码用语言说清楚每个算法每一轮在做什么。能不能自己推导出每种算法的稳定性结论并举出反例。能不能解释为什么快排平均 O(n log n)最坏却 O(n²)。能不能说清归并排序为什么需要 O(n) 的空间而堆排序为什么只需要 O(1)。能不能在“有序数组”“逆序数组”“大量重复值”“小规模数据”四种数据集上预判哪种算法表现最好。能不能手写完成的排序代码通过随机测试建议自己写测试工具生成包含空数组、单元素、升序、降序、重复元素的测试集。最后一个建议手工走到排序过程中间去。我见过最有意思的复习方法是拿一叠扑克牌按插入排序、快排、归并的思路各手动理一遍牌。当你亲眼看着牌逐渐变得有序很多停留在一知半解的“为什么”会瞬间清晰。排序算法说到底就是一门“让无序变有序”的手艺该动手时就动手光看不练永远差一层。 深入理解8种排序算法：原理、复杂度与工程选型指南
前阵子帮同事 review 代码发现线上一个模块里他用三层 for 循环手写了一个“冒泡排序”去排用户列表。我问他为什么不用现成的 sort他说怕库排序不稳定改了排序结果。这让我有点感慨很多写了好几年业务的同学对排序算法的理解还停留在“背代码应付面试”的阶段真正到了要选型、要解释为什么用这个不用那个的时候就抓瞎了。排序这东西说难不难说简单也不简单。说难是因为如果只看教科书上的代码冒泡、选择、插入、希尔、归并、快排、堆排、计数这八种挨个背一遍很容易背了就忘。说简单是因为只要你理解了每种排序到底在“怎么组织数据”“用了什么策略”你会发现它们之间有一条清晰的演进脉络根本不需要死记硬背。这篇文章我想用工程实践的角度把这 8 种常见排序算法从原理、代码到选型逻辑串一遍顺便把我在实际开发和面试里踩过的坑、总结的经验放进去。目标读者是两类人一类是正在准备数据结构期末复习或者面试的在校生另一类是写业务工作两三年、想系统把排序这块补扎实的同学。看完你至少能做到三件事手写核心实现不慌、别人问你为什么不稳定能答上来、遇到真实排序需求知道该选谁。1. 排序算法到底在学什么先避开两个误区1.1 误区一背代码不等于会排序我见过大量同学准备排序算法的方式是打开博客复制快排代码背下来面试现场默写。这种做法最大的问题是一旦面试官把“对数组排序”改成“对链表排序”或者改成一个自定义的比较规则很多人就懵了。排序算法的核心不是那几行代码而是三个问题的答案每一轮做了什么为什么这样做能逼近有序这个做法的代价是什么以冒泡排序为例。如果你只是背“外层循环 n-1 次内层循环 n-1-i 次相邻比较交换”那你没有真正理解它。真正的理解是“每一轮让一个未归位的最大元素通过相邻交换‘冒’到它最终该在的位置”。有了这层理解你自然会推出优化方案——如果某一轮没有任何交换说明数组已经有序直接结束。所以这篇文章里每种算法我都会先讲“它在干嘛”再给代码。代码只是结果思想才是要学的东西。1.2 误区二只盯着时间复杂度很多人评价排序算法只会一句话“快排最快Bubble 最慢。”这个认知在刷题场景下没问题但工程上一旦落到真实需求会踩大坑。时间复杂度描述的是数据量趋于无穷时的增长趋势但真实场景里数据量往往没到那个量级此时常数项、空间开销、稳定性、递归深度、甚至 CPU 缓存命中率都可能比理论复杂度更影响最终效果。举一个我实际遇到的例子一个服务里需要对某个长度在 100 到 200 之间的分页结果排序。有人坚持用快排理由是“快排平均 O(n log n) 最牛”。但测试发现这个规模下插入排序反而更快因为插入排序常数极小、局部性又好而且完全不需要递归。最后我把代码改成在数据长度小于 60 时走插入排序P99 延迟降了差不多 15%。这不是说快排不好而是说选排序算法是一个系统工程要看的维度远不止时间复杂度一个。稳定性、空间复杂度、数据本身是否近乎有序这些都是关键变量。我后面会用一整节专门讲工程选型。2. 热身组冒泡、选择、插入简单不意味着可以写错2.1 冒泡排序最直观的交换思想隐藏着一个优化点冒泡排序的思路是最朴素的从前往后扫描把相邻的两个元素中较大的那个往后换一轮下来最大的元素就“冒”到了最后面。重复这个过程每轮少看一个元素直到全部排完。基础写法void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } }这个版本能跑但有个明显的浪费如果数组在第一轮就已经有序它依然会继续跑 n-1 轮。加一个标志位就能解决void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); swapped true; } } if (!swapped) { break; } } }这个优化让冒泡排序的最好情况从 O(n²) 降到了 O(n)——当传入数据本身就是有序时第一轮扫描发现没有任何交换直接跳出。这个细节在很多面试题里会作为“你还有什么优化空间”的追问出现。稳定性上冒泡排序是稳定的因为只有在arr[j] arr[j1]时才交换相等元素不会交换位置。这一条务必记牢后面有一节专门讲稳定性的意义。2.2 选择排序交换次数最少却可能不稳定选择排序的思路是另一路每一轮找到未排序区间里的最小元素把它放到当前区间的最前面。相比冒泡排序的“频繁相邻交换”选择排序每轮最多只做一次交换总共最多交换 n-1 次。void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIndex i; for (int j i 1; j n; j) { if (arr[j] arr[minIndex]) { minIndex j; } } if (minIndex ! i) { swap(arr, minIndex, i); } } }这里有个细节值得展开如果数组元素是体积很大的对象排序过程中“比较”通常比“交换”便宜得多比较只读几个字段交换可能要移动整块数据。选择排序每轮只交换一次这个特性在“写操作代价高”的场景里很有价值。比如你在内存里排序一批 MySQL 记录的游标每个元素背后挂着几十个字段的引用这时候选择排序的交换次数优势就会被放大。但选择排序有个硬伤——它不稳定。常见解释是“最小元素和当前位置交换可能跨过多个相同元素导致相对顺序改变”。我给出一个最直观的例子数组[5a, 8, 5b, 2, 9]为了区分两个 5我加了标记 a 和 b。第一轮找到最小值 2把 2 和第一个位置的 5a 交换变成[2, 8, 5b, 5a, 9]。两个 5 的相对顺序变成了 b 在前 a 在后这就破坏了稳定性。理解这一点很重要因为很多教材只说“选择排序不稳定”却不说为什么。我建议你自己动手走一遍这个过程比背十遍结论都管用。2.3 插入排序处理“几乎有序”数据的一把好手插入排序是最接近人类本能的一种排序思路——就像你打扑克牌时摸到一张新牌会和手里已有的牌从右往左比较找到合适的位置插进去。void insertionSort(int[] arr) { int n arr.length; for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这个代码看似简单但有两个地方是面试高频追问点。第一个是内层循环的条件。必须是arr[j] key不能写成arr[j] key。如果写成了大于等于相等的元素会被强行往前移破坏稳定性。很多人在白板写代码时下意识写错这一行就是分水岭。第二个是它的时间复杂度特点。插入排序在最好情况数组已经有序下只需要一层循环比较每轮发现key已经大于前一个元素直接跳过内层循环所以最好情况是 O(n)。这个特性让它成为“近乎有序”数据的最佳选手——比如一个系统日志列表大部分时间戳本来就是有序的只有偶尔几条新插入的记录乱序这时候插入排序几乎就是 O(n) 级别的表现。这也是为什么 Java 的Arrays.sort在底层处理小数组时会把归并排序切回插入排序。不是插入排序比归并厉害而是当 n 很小时插入排序的低常数项优势远远超过了归并排序的理论复杂度优势。后面讲归并和工程选型时我会把这个逻辑串起来。3. 进阶组希尔、归并、快排、堆排序为什么它们能快那么多3.1 希尔排序插入排序的升级版插入排序有个明显的短板如果一个很小的元素在数组最后面它要一步一步地往前挪这趟路很长。希尔排序的思路是先让元素“跳着走”在相隔较远的位置之间做插入排序缩小“路途”等整体大体有序后再做一次普通插入排序。希尔排序的关键是步长序列gap 序列。我给出一个最常见、也最好写的版本初始 gap 为数组长度的一半每次减半直到 gap 为 1。void shellSort(int[] arr) { int n arr.length; for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key arr[i]; int j i; while (j - gap 0 arr[j - gap] key) { arr[j] arr[j - gap]; j - gap; } arr[j] key; } } }理解这段代码的关键是gap 为 g 时你其实是在同时对 g 个子序列分别做插入排序。比如 gap 4 时位置 0, 4, 8… 是一组位置 1, 5, 9… 是另一组以此类推。每个子序列内部使用插入排序由于每个子序列的元素数量只有总长度的 1/g整体开销大幅下降。随着 gap 不断缩小子序列数量变少、长度变长但数据已经越来越接近有序插入排序的“近乎有序”优势开始发挥。希尔排序的时间复杂度取决于 gap 序列的选择。简单减半序列的平均复杂度大致在 O(n^1.3) 附近这档最坏情况下仍是 O(n²)比如某些经典序列。实践中更优秀的增量序列有 Hibbard 序列、Sedgewick 序列等它们能把最坏复杂度压到 O(n log n) 量级但实现复杂一些一般考试和面试不会要求。稳定性方面希尔排序是不稳定的。因为元素在按 gap 跳跃时相同大小的元素可能被分到不同的子序列里然后在后续过程中相对位置发生交错。这个问题和选择排序不稳定一样属于“结构上注定”的不是写坏了。3.2 归并排序稳定的分治选手归并排序是我个人最喜欢给新人讲的一种算法因为它把“分治”思想体现得最干净把一个数组从中点切开分别排好两个子数组再把两个有序数组合并成一个有序数组。递归到底层一个元素天然有序所以关键在于“合并有序数组”这一步。void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid (left right) 1; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } void merge(int[] arr, 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) { if (arr[i] arr[j]) { temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) { temp[k] arr[i]; } while (j right) { temp[k] arr[j]; } for (int p 0; p temp.length; p) { arr[left p] temp[p]; } }稳定性写在merge函数的那个if里当左边元素小于等于右边元素时先取左边的。这样相等元素的相对顺序在合并过程中不会改变所以归并排序是稳定的。如果你把写成稳定性的结论就不成立了——这是很多细节控面试官喜欢挖的点。归并排序的最大代价是空间。每次合并都要申请一个长度和当前区间相同的临时数组最终递归过程中总的空间复杂度是 O(n)。这不是小开销在内存紧张的嵌入式环境里可能直接不适合用。但归并排序有一个相当重要的工程应用外部排序。当数据量大到无法全部加载进内存时只能对磁盘里的数据分块排序再不断归并这些块整个思路就是归并排序的扩展。另外对链表排序时归并排序因为不需要随机访问数据而且链表上做归并不需要额外数组空间只需要改指针反而是最合适的选择。如果要在归并这里记一句心得我建议记这句递归思想看归并原地性能看快排。3.3 快速排序性能好但不稳定pivot 选择是灵魂聊排序绕不开快排。它也是分治思想但和归并排序的区别在于归并排序的难点和重点是“合”而快排的重点在“分”。快排的做法是选一个基准值pivot把数组分成“比 pivot 小的”和“比 pivot 大的”两部分然后对这两部分递归做同样的事情。void quickSort(int[] arr, int left, int right) { if (left right) { return; } int p partition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p 1, right); } int partition(int[] arr, int left, int right) { int pivotIndex left (right - left) / 2; swap(arr, pivotIndex, right); int pivot arr[right]; int i left; for (int j left; j right; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, right); return i; }这个partition用的是 Lomuto 分区方案逻辑简单i指向“比 pivot 小的区域”的下一位置j从 left 扫到 right-1遇到比 pivot 小的就放进 i 的位置。最后把 pivot 换到 i 处。这种方式笔试写起来容易但它有个不足当数组里有很多重复元素时它会做大量无意义的交换此时三路快排把等于 pivot 的单独放中间更好。快排最关键的工程问题是 pivot 怎么选。上面这个例子我直接取了中间位置这在绝大多数情况下表现可以但如果你取的是数组的第一个或最后一个元素并且输入数组恰好是近乎有序的分区结果会严重偏斜递归深度接近 n时间复杂度退化到 O(n²)。解决办法有三个思路第一是随机化 pivot。每次在区间里随机选一个位置和末尾元素交换这样最坏情况出现的概率被摊薄了。第二是三数取中法。取区间首、中、尾三个位置的元素选这三个数的中间值作为 pivot能有效避免有序数组的退化问题。第三是内省排序。设置一个递归深度阈值当递归深度超过 2 log n 时切换到堆排序兜底。C 的std::sort实际就是用的第三种策略这是快排在工程里的终极版本。快排不稳定的原因很直接partition过程中有大量的跨区间交换相等元素的相对顺序完全可能被打乱。所以如果需求要求排序后相同元素的先后顺序不能变快排不能直接用哪怕它平均性能再好也不行。3.4 堆排序原地排序里的大块头堆排序的思路是借用一个数据结构而不是一种新的“排序思想”。它的分治意识没那么强更多是“反复取出堆顶”的逻辑把数组调整成一个大顶堆堆顶就是最大值把它和当前末尾元素交换然后把堆的大小减一再调整重复这个过程。void heapSort(int[] arr) { int n arr.length; for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } for (int i n - 1; i 0; i--) { swap(arr, 0, i); siftDown(arr, 0, i); } } void siftDown(int[] arr, int i, int n) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) { largest left; } if (right n arr[right] arr[largest]) { largest right; } if (largest ! i) { swap(arr, i, largest); siftDown(arr, largest, n); } }这段代码里最容易被忽略的是siftDown的边界条件。建堆时i从n / 2 - 1开始是因为这个位置正是最后一个非叶子节点的索引对于 0 起始的完全二叉树叶子节点从n / 2开始。从下往上做下沉调整才能让所有子树先有序建堆总开销是 O(n)这个结论很多人记不住但它是堆排序的亮点之一堆排序在堆有序时也不会有额外开销复杂度在最坏、最好、平均情况下都是 O(n log n)。我不止一次看到有人写堆排序时把largest的初始值写成0这是从示例代码里照抄的坏习惯——siftDown被递归调用时当前节点不一定是 0。每次进入函数largest必须先等于i当前子树的根再和左右孩子比较更新。这种细节看似不起眼却直接决定代码对不对。堆排序的空间复杂度是 O(1)是“原地排序”里性能最稳定的大哥但它在实际工程中的使用频率远低于快排和归并。原因有两个一是它的常数项较大siftDown过程虽然只有 O(log n) 次操作但每次操作都要算左孩子右孩子索引CPU 缓存命中率不如快排二是不稳定。所以堆排序适合的场景通常是要求原地排序、不允许额外空间、同时不要求稳定性的情况。4. 计数排序不靠比较的排序如何突破 O(n log n)4.1 为什么比较排序快不过 O(n log n)前面写到的七种排序本质上全是“基于比较”的排序。它们的通用决策过程是每次比较两个元素得到一个“谁大谁小”的信息然后据此调整位置。你可能会想为什么找不到一种比较排序能突破 O(n log n)那是因为 N 个元素的排列有 N! 种可能每次比较最多只能帮你排除一部分可能性理论上你至少需要 log2(N!) 次比较才能唯一确定排列顺序而 log2(N!) ≈ N log2 N。这个基于决策树的证明是所有基于比较的排序算法不可逾越的天花板。那有没有办法绕过这个天花板有。思路是放弃“比较”这个动作。4.2 计数排序的完整实现与两个容易踩的坑计数排序的思路是既然比较太贵那我干脆不比较。先统计每个值出现了多少次再根据统计信息直接把每个元素放到它该在的位置上。它的前提是数据范围max - min不能太大而且数据最好是整数。void countingSort(int[] arr, int min, int max) { int k max - min 1; int[] count new int[k]; for (int v : arr) { count[v - min]; } for (int i 1; i k; i) { count[i] count[i - 1]; } int[] output new int[arr.length]; for (int i arr.length - 1; i 0; i--) { int v arr[i]; output[count[v - min] - 1] v; count[v - min]--; } System.arraycopy(output, 0, arr, 0, arr.length); }这里面有两个坑我都在真实代码里踩过。第一个坑是负数数据。很多人写的计数排序只支持从 0 开始遇到负数就数组越界。解决办法就是上面代码里的min参数统计时下标用v - min这样即便最小值是 -100000也能正常处理。映射回原值时再加回min。本质上就是把数据整体“平移”到从 0 开始的区间。第二个坑是稳定性。如果你只是统计出现次数然后从头到尾填回原数组排序结果是对的但相同值的元素相对顺序会被打乱。要让计数排序稳定必须用“累加 从后往前放”这个写法count数组先做前缀和让count[v - min]表示“小于等于 v 的元素个数”然后从原数组的末尾开始遍历每遇到一个元素 v就放到output的第count[v - min] - 1个位置同时把对应的计数减一。这样保证了顺序和原数组一致。计数排序的时间复杂度是 O(n k)其中 k 是数据范围。当 k 远小于 n 时它是严格快于任何比较排序的而且这还是稳定排序。一个经典的面试例子给 0 到 100 分的考试分数做排名数据量有上万人计数排序只需要一个长度为 101 的计数数组效率碾压快排。不过它确实有两个硬性限制第一只能用于整数或者可以映射到整数且大小范围可控的数据第二如果 k 非常大比如要对 32 位整数排序计数数组直接爆内存这时候应该用基数排序等其他线性排序方案但基数排序不在今天的 8 种清单里感兴趣可以自己延伸看。5. 八种排序一张表复杂度、稳定性与适用场景5.1 八种排序算法复杂度对照表理论说了这么多落到一张表上最直观。这张表建议保存下来无论是期末复习还是面试前突击先把它背明白再去抠代码细节。排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序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(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 log n)O(n log n)O(n log n)O(1)不稳定计数排序O(n k)O(n k)O(n k)O(k)稳定5.2 怎么读懂这张表这张表里最有信息量的不是时间复杂度那几列而是“稳定性”这一列。很多人不理解稳定性到底有什么用我给一个特别经典的真实业务例子你要给一批用户按“等级”从高到低排等级相同的人再按“注册时间”从早到晚排。如果只排一次那无所谓顺序只在这一次里定义。但常见做法是先按注册时间升序排一遍再按等级降序排一遍。如果第二次排序用的是不稳定的算法等级相同的人注册时间顺序会被打乱结果就错了。稳定排序保证了多次排序时上一次排序建立的相对顺序不会被破坏。这就是为什么后端排序用户列表时最后一步排序必须用稳定算法的原因。再细看最坏情况的快排O(n²)。这个结论让很多初学者恐慌那快排是不是根本靠不住事实是快排在工程里的“最坏情况”几乎可以通过随机化 pivot 和混合策略规避掉所以它依然是默认排序工具里最常被选用的那一档。大厂面试问“快排为什么快”通常是想听你讲出“分治 数据局部性 缓存友好”这三个层次而不是只背复杂度。还有希尔排序那一行我特意写了“取决于增量序列”。因为希尔排序的复杂度不像其他排序有统一结论不同增量序列差异很大。期末复习如果考到希尔务必先确认考试教材用的是哪个增量公式再决定填什么复杂度。6. 工程选型逻辑为什么成熟库从不只用一种排序6.1 一个排序函数背后的混合策略如果你打开 Java 的Arrays.sort源码会发现它内部根本不是单一的排序算法。对基本类型数组它用双轴快速排序对对象数组它用 TimSort一种对归并排序和插入排序的混合改进。Python 的sorted也是 TimSortC 的std::sort则是“快排 插入 堆排”的内省排序。为什么官方库要做这么复杂的混合因为没有任何一种排序算法在所有数据形态下都最优。TimSort 的思路特别值得我们工程师借鉴它先扫描数据里已经有序的片段run把这些天然有序的段直接保留再用归并的方式把它们合并起来。这个设计的价值非常明确——真实世界的数据里有大量“部分有序”的片段。用户列表按时间戳插入、日志按日期追加、成绩单按学号分组这些数据天然带有序结构。TimSort 把这些结构当作免费的午餐效率远高于对所有元素一视同仁的普通快排。我建议你把这个思路带到自己的代码里写排序之前先看看你的数据是不是“几乎有序”。如果是插入排序或者归并排序的变体可能会比无脑快排快得多如果不是再回归快排或 TimSort。6.2 工程中比算法实现更重要的三件事第一件事是明确排序需求的两个前提是否要求原地排序是否要求稳定。这两个前提直接决定了你的算法候选集。比如一个长列表但内存吃紧空间复杂度 O(n) 的归并排序可能直接出局又比如业务上需要保持上一次排序的相对顺序那么不稳定算法全部淘汰只能在冒泡、插入、归并、计数里选。第二件事是注意比较器的完整性和一致性。对自定义对象排序时很多人写的compare方法只比较了一个字段导致两个不同对象的字段相等时返回 0而在某些语言/库的实现里这会让两个“相等”的对象在排序后相对顺序变得不可预期。写比较器时请遵循返回值要和equals的结果保持一致否则就老老实实写一个明确的“决出胜负”的次级比较规则。第三件事是警惕递归深度带来的栈溢出。快排和归并排序在极端数据分布下递归深度都可能很深尤其快排遇到坏 pivot 时会退化到接近 n 层递归。生产环境里我见过因为排序导致栈溢出的线上事故解决方案有两个一是设置递归深度阈值超过就切堆排序兜底内省排序二是把递归写法改成迭代写法用显式栈模拟递归。我自己的一个习惯是在排序函数入口处先处理边界条件数组为空或长度为 1 时直接返回。这个判断看似微不足道却能在框架里减少很多无意义的递归调用。很多从示例代码复制粘贴的同学恰恰漏了这两行。6.3 我的自测清单与学习建议如果你现在准备复习排序算法我分享一份我当年用过的自测清单按顺序过一遍基本能确认自己对这 8 种算法是真懂还是假懂能不能不看代码用语言说清楚每个算法每一轮在做什么。能不能自己推导出每种算法的稳定性结论并举出反例。能不能解释为什么快排平均 O(n log n)最坏却 O(n²)。能不能说清归并排序为什么需要 O(n) 的空间而堆排序为什么只需要 O(1)。能不能在“有序数组”“逆序数组”“大量重复值”“小规模数据”四种数据集上预判哪种算法表现最好。能不能手写完成的排序代码通过随机测试建议自己写测试工具生成包含空数组、单元素、升序、降序、重复元素的测试集。最后一个建议手工走到排序过程中间去。我见过最有意思的复习方法是拿一叠扑克牌按插入排序、快排、归并的思路各手动理一遍牌。当你亲眼看着牌逐渐变得有序很多停留在一知半解的“为什么”会瞬间清晰。排序算法说到底就是一门“让无序变有序”的手艺该动手时就动手光看不练永远差一层。