比较排序通关攻略：冒泡到堆排，复杂度与稳定性全解析

提到数据结构排序算法，最让大家头疼的往往不是背代码，而是代码能写出来、但说不清背后的取舍。排序算法里又有一大类叫比较排序：冒泡、选择、插入、希尔、归并、快排、堆排，全都靠元素之间的两两比较来决定顺序。这篇《排序算法通关攻略：比较排序篇》就是把这条线从青铜到王者重新走一遍，适合刚学完基础概念但总写错边界条件的同学，也适合打算突击面试、想一次性把复杂度、稳定性和工程优化串起来的开发者。示例代码我统一用C语言写，因为C语言没有太多库函数帮忙，数组下标、递归栈、临时内存分配这些坑全都暴露出来，你用Java、Python、Go去对照也完全没有障碍。后边每一级我都会讲清楚原理、代码、复杂度以及我实际踩过的问题。

1. 青铜起步：选择排序与冒泡排序，先搞懂比较与交换

1.1 冒泡排序：相邻比较与交换，先把最大的“顶”上去

只要写过排序，十个里有八个第一版是冒泡。思路很直白：每一轮从头往后扫描，相邻两个元素如果前一个比后一个大，就交换它们，一轮下来最大的数就像气泡一样被顶到数组末尾。下一轮再把剩下 n-1 个元素里最大的顶到倒数第二个位置，n-1 轮之后整个数组有序。

C语言实现：

void bubble_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; for (int j = 0; j < n - 1 - i; j++) { if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; swapped = 1; } } if (!swapped) break; } }

很多人觉得冒泡是最没用的算法，但它其实是理解“比较排序”最好的起点。这里的核心动作只有两个：比较和交换。每一轮都确定一个元素的最终位置，这是选择排序同样使用的思想。带 swapped 标记之后，如果某轮没有发生交换，说明数组已经有序，直接结束，这就是冒泡最好情况能做到 O(n) 的原因。

需要注意的点：外层循环只需要到 n-1，最后一个元素在只剩它一个时自然归位；内层循环上界是 n-1-i，因为每轮已经排好了 i 个最大值；用大于号而不是大于等于，是为了保证相等元素的相对顺序不乱，这是稳定排序的基本要求。我之前见过不少同学写成a[j] >= a[j+1]，虽然结果也是升序，但相等元素被交换过，稳定性丢了，后边遇到需要稳定排序的场景就会出问题。

复杂度上，平均和最坏都是 O(n^2)，空间只有 O(1)。你要是拿冒泡去排十万个随机数，基本会被秒杀，但排基本有序的小数组时它其实不慢，因为一旦发现没有交换就退出了。所以冒泡不是一无是处，而是要看输入数据长什么样。

1.2 选择排序：每次挑一个最小值，和冒泡死磕同一复杂度

选择排序的思路比冒泡更“暴力”：从左到右扫描一遍，找到最小的元素，把它放到下标 0；再从剩下元素里找最小，放到下标 1；以此类推。它的核心是“选择”而不是“交换”，一轮只交换一次，但依然要做完 n(n-1)/2 次比较。

C语言实现：

void selection_sort(int a[], int n) { for (int i = 0; i < n - 1; i++) { int min_idx = i; for (int j = i + 1; j < n; j++) { if (a[j] < a[min_idx]) { min_idx = j; } } if (min_idx != i) { int tmp = a[i]; a[i] = a[min_idx]; a[min_idx] = tmp; } } }

选择排序比冒泡有优势的地方在于交换次数少，最多 n-1 次交换；但它的比较次数是固定的，不管原始数据是否有序，都是 O(n^2)。这意味着面对“已经排好序”的数组，它不会像冒泡那样提前退出，性能反而更差。这一点在算法面试里经常被拿来考：问你冒泡、选择、插入三个 O(n^2) 排序哪个更适合近乎有序的数据，答案是插入，不是选择。

关于稳定性，选择排序是不稳定的。经典例子是5 5 3：第一轮找到最小值 3，把 3 和第一个 5 交换，数字顺序就变成了3 5 5，原本在前面的 5 跑到了另一个 5 的后面。如果你在业务代码里依赖稳定性，用选择排序就得谨慎。其实工程里我们几乎不手写这两种 O(n^2) 排序，但理解它们能帮你打下“比较交换”和“原地排序”的直觉，这是后边所有高级算法的基础。

2. 白银进阶：插入排序与希尔排序，让数据局部有序

2.1 插入排序：像打扑克一样整理数组，小数组王者

插入排序的直觉我特别喜欢：摸牌的时候，把新摸到的牌从右往左比较，找到合适位置插进去。实现的时候，数组左边永远是已排序的部分，右边是待处理部分。对于下标 i，先把值存到 key，然后不断向左移动，找到第一个不大于 key 的位置，把 key 插进去。

C语言实现：

void insertion_sort(int a[], int n) { for (int i = 1; i < n; i++) { int key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } }

插入排序最值得记的性能特征是“对近乎有序的数据接近 O(n)”。如果数据已经有序，每次循环里 while 判断a[j] > key第一个就不成立，整轮只做一次比较和一次赋值。所以它非常适合：数据量小、局部有序、以及作为高级排序的递归退出条件。像 C++ 的std::sort在快排递归深度到小数组时切到插入排序，Python 的 TimSort 也会对小块用插入排序。

它也是最稳的 O(n^2) 排序，因为相等元素不会被移动到前边，排序是稳定的。空间 O(1)。缺点就是逆序数据时和冒泡一样悲催，最坏 O(n^2)。

常见错误是 while 里忘了j >= 0的边界判断，或者把a[j] > key写成>=，后者会让排序变得不稳定。尤其要注意，插入排序中“寻找插入位置”的过程就是不断右移记录，移动次数比想象中多，这个行为在后续的希尔排序中会直接影响效率。

2.2 希尔排序：让元素先跳到远处，再慢慢归位

希尔排序可以理解成“分组的插入排序”。直接插入排序的问题是每次只能交换相邻元素，逆序多的时候要搬很多次家。希尔排序先选一个较大的间隔 gap，把相隔 gap 的元素看成一组，对每组做插入排序；然后缩小 gap，再排；直到 gap=1，再做一次全量插入排序。因为大间隔让元素能快速跨越大范围移动，最后一次普通的插入排序工作量就小很多。

C语言实现（简单的希尔增量）：

void shell_sort(int a[], int n) { for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i < n; i++) { int key = a[i]; int j = i - gap; while (j >= 0 && a[j] > key) { a[j + gap] = a[j]; j -= gap; } a[j + gap] = key; } } }

注意这里内层不是严格的“分组排序”写法，而是从 gap 位置开始往后遍历，每次把 a[i] 当成新元素，和同一组里前面的元素做插入。这比写多重分组循环更容易理解，效率也一样。gap 序列的选择直接影响复杂度，希尔增量是 n/2 每次减半，最坏 O(n^2)；Hibbard 增量或者 Sedgewick 增量能到 O(n^1.5) 甚至更好。工程上已经不太用希尔排，但很多教材和考试还爱考，你得知道 gap 最后一步必须是 1，否则数组不会整体有序。

希尔排序是不稳定的，因为相等的元素可能被分到不同的组里，跨组移动会破坏相对顺序。另外我在写希尔的时候踩过的坑是 gap 缩到 0 之后的死循环，以及内层把j -= gap写成了j--，这会导致分组逻辑错乱。验证时用一个简单的[5, 2, 3, 1, 4]手跑一遍插入过程，比Debug还快。

3. 黄金分治：归并排序，稳定与确定性的权衡

3.1 归并排序的灵魂：把两个有序数组合到一起

归并排序是第一个真正意义上的 O(n log n) 排序，也是学习分治思想的经典案例。它的做法很清晰：把数组从中间分成两半，分别排序，再把两个有序子数组合并成一个整体。递归拆到只剩一个元素时，它天然有序，合并过程就能向上回溯。

C语言实现：

void merge_sort(int a[], int left, int right, int tmp[]) { if (left >= right) return; int mid = left + (right - left) / 2; merge_sort(a, left, mid, tmp); merge_sort(a, mid + 1, right, tmp); merge(a, left, mid, right, tmp); } void merge(int a[], int left, int mid, int right, int tmp[]) { int i = left, j = mid + 1, k = 0; while (i <= mid && j <= right) { if (a[i] <= a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } while (i <= mid) tmp[k++] = a[i++]; while (j <= right) tmp[k++] = a[j++]; for (int p = 0; p < k; p++) { a[left + p] = tmp[p]; } }

合并函数是核心：两个有序区间从头开始比，谁小谁先进临时数组。必须用<=而不是<，这样当左右两半出现相等元素时，左边先进来，排序就是稳定的。时间复杂度永远 O(n log n)，和输入顺序无关，空间 O(n) 需要一块临时数组，稳定。

归并排序的应用场景很明确：外部排序。当数据量大到放不进内存，比如几十 GB 的日志，没法用快排或堆排直接原地搞，只能按块读入内存排序，写到磁盘，再通过多路归并合并。因为归并排序是顺序读写，对磁盘友好。链表排序也通常用归并，因为它不需要随机访问，只要改指针。

3.2 递归写法与小段优化，稳定性的代价

用递归写归并最容易犯的错误是mid的边界。我习惯写int mid = left + (right - left) / 2;，而不是(left + right) / 2，后者在数组很大时可能整数溢出。虽然日常不会遇到几亿长度的数组，但面试官喜欢问这种细节，改一下又不用花钱。

性能上归并排序有明显的优化空间。第一个优化是当区间足够小（比如小于等于 16 或 32 个元素）时，直接改用插入排序，而不是继续递归切分。递归本身有函数调用开销，插入排序在小数组上更快，这一步几乎能让整体性能提升百分之二三十。第二个优化是临时数组一次性分配，不要每次递归都 malloc，避免反复申请内存。第三个优化是在合并前判断if (a[mid] <= a[mid + 1])，如果两个子数组的最高位小于等于后一个的最低位，说明它们已经有序，可以直接返回，不用合并。这个判断对局部有序数据特别有效。

稳定性是归并排序最大的卖点，但也意味着合并时要多花一点内存和拷贝时间。如果你写完一个归并发现输出不对，先检查临时数组的索引k和回写位置left + p是不是对上了，这是我见过最多的问题。另一个常见的坑是递归终止条件只写left == right，万一传入的区间奇怪（比如 left > right），就会越界，所以写left >= right更安全。

4. 铂金策略：快速排序，平均最快的通用算法

4.1 快排的partition：选一个基准，把数组分成两半

快排的流行程度不用多说，大多数语言内置排序的核心都是它或者它的变体。核心概念是 partition：选一个元素作为基准 pivot，把数组重新整理，让 pivot 左边都小于等于它，右边都大于等于它，然后递归处理左右两边。分完一次，pivot 就到了它最终的位置，和归并的“先拆再合”不同，快排是“边分边排”。

C语言实现（霍尔分区法）：

int partition(int a[], int low, int high) { int pivot = a[low]; int i = low, j = high; while (i < j) { while (i < j && a[j] >= pivot) j--; a[i] = a[j]; while (i < j && a[i] <= pivot) i++; a[j] = a[i]; } a[i] = pivot; return i; } void quick_sort(int a[], int low, int high) { if (low < high) { int p = partition(a, low, high); quick_sort(a, low, p - 1); quick_sort(a, p + 1, high); } }

这里的 partition 每次从右边找一个小于 pivot 的元素填到左边，从左边找一个大于 pivot 的元素填到右边，最后把 pivot 放回 i 的位置。循环条件是重点：while (i < j && a[j] >= pivot)必须用大于等于，否则遇到和 pivot 相等的元素时会一直交换，造成死循环。退出后low < high才能递归，等于的情况不需要处理。

平均复杂度是 O(n log n)，最坏 O(n^2)。最坏发生在每次划分都极度不均衡，比如数组本身有序时如果每次选到的是最小或最大值作为 pivot。空间上递归栈平均 O(log n)，最坏 O(n)，不稳定。所以工程上必须对 pivot 的选取做手脚，这也就是下一节的内容。

4.2 优化三板斧：随机化、三数取中、小数组切插入

快排的优化值得单独聊，因为“实现一个能用的快排”和“实现一个生产级快排”差的真的太远了。第一板斧是随机选取 pivot，让最坏情况变成概率事件；第二板斧是三数取中，取 low、mid、high 三个位置的中位数当 pivot，对抗基本有序数组；第三板斧是小数组切到插入排序，减少递归到底的调用开销。

我一般会在 partition 开始之前先选 pivot 并交换到首位：

void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int pick_pivot(int a[], int low, int high) { int mid = low + (high - low) / 2; if (a[mid] < a[low]) swap(&a[mid], &a[low]); if (a[high] < a[low]) swap(&a[high], &a[low]); if (a[high] < a[mid]) swap(&a[high], &a[mid]); swap(&a[mid], &a[low]); return a[low]; }

选完之后把 pivot 交换到a[low]，再走统一的霍尔分区。三数取中本质上降低了最坏情况的触发概率，比纯随机更稳定。

还有一个进阶点是三路快排：当数据里大量重复元素时，标准快排会退化成 O(n^2)。三路快排把数组分成小于 pivot、等于 pivot、大于 pivot 三段，等于 pivot 的部分不参与递归，这样重复多的数据也能保持 O(n log n)。Java 的基本类型排序在双轴快排里也用到了类似思想。

快排在业务里的下场其实很矛盾：很多同学面试时能写出标准快排，但一放大数组就爆栈，因为递归深度无法控制。后面我会单独聊爆栈问题，这里先记住一点：任何时候递归版都要用随机化或中位数优化，并且给递归加一个深度上限，一旦超过上限就切换堆排序。这就是工业级内省排序的做法，第六节和第七节会说清楚。

5. 钻石进阶：堆排序，用二叉树思维排序

5.1 堆化细节：为什么从最后一个非叶节点开始

堆排序依赖完全二叉树，但不额外建树，直接在数组上操作。大顶堆要求父节点不小于子节点，堆顶就是最大值。排序过程分两步：先把数组堆化，让最大值到堆顶；然后把堆顶和最后一个元素交换，堆大小减一，再对根节点做一次下沉调整，就能反复取出剩余最大值。

C语言实现：

void sift_down(int a[], int n, int i) { while (i < n) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && a[left] > a[largest]) largest = left; if (right < n && a[right] > a[largest]) largest = right; if (largest == i) return; int tmp = a[i]; a[i] = a[largest]; a[largest] = tmp; i = largest; } } void heap_sort(int a[], int n) { for (int i = n / 2 - 1; i >= 0; i--) { sift_down(a, n, i); } for (int i = n - 1; i > 0; i--) { int tmp = a[0]; a[0] = a[i]; a[i] = tmp; sift_down(a, i, 0); } }

细节都藏在索引里。数组下标从 0 开始，那么节点 i 的左孩子是2*i+1，右孩子是2*i+2，最后一个非叶节点是n/2 - 1。从它开始往前循环，逐个下沉，才能保证每一个子树都满足大顶堆。如果你从 0 开始正着做，叶子节点没有孩子，不处理是可以的，但分组调整的顺序就不对了。

建堆的时间复杂度是 O(n)，不是 O(n log n)。推导起来不复杂：高度越低的节点数量越少，综合下来每层工作量是 O(height)，总数趋近于 O(n)。排序阶段每次把堆顶放到底部，交换后再下沉 O(log n)，所以总复杂度 O(n log n)。空间 O(1)，原地排序，但不稳定，比如相同值的元素可能因为下沉交换位置。

5.2 堆排序没快排快，但TopK离不开它

为什么实际排序不用堆排？因为堆排序的访问模式是跳跃式的，对 CPU 缓存不友好，而快排是顺序访问，缓存命中率高得多。堆排的常数比较大，在大多数输入下跑不过快排。但它有一个优点：最坏情况就是 O(n log n)，不存在退化到 O(n^2) 的风险。因此很多异常对抗场景或者实时系统里，宁可选择堆排或内省排序中的堆排兜底。

堆真正的用武之地是优先队列和 TopK 问题。你要在几亿个数据里找最大的一百个，没必要把所有数据排一遍，建一个小顶堆，不断用新元素替换堆顶并下沉，堆大小维持 100，最后堆里的就是 Top100。这个过程时间复杂度 O(n log k)，k 是 100 的话几乎就是线性的。理解堆排以后，写这些工具函数就是顺手的事。

常见的堆排错误有两个。一个是在 heapify 循环里只传 n 而忽略当前子树的范围，下沉时把已经排定位置的后缀也算进去，破坏了排序阶段的结果；另一个是递归版 sift_down 在小堆上没问题，但在大数组中递归深度其实只有 log n，用递归还行，不过迭代版更稳，能避免不必要的函数调用。我建议把这套代码背到滚瓜烂熟，因为它不仅是排序，还是很多高级数据结构的根。

6. 王者升华：工业级混合排序与比较排序的边界

6.1 工业级排序：std::sort、Arrays.sort、TimSort各自怎么混

到了这个段位，你已经知道没有银弹。纯快排最坏 O(n^2)，纯归并需要 O(n) 空间，纯堆排常数太大，所以工业级排序基本都是混合体。C++ 的std::sort用的是内省排序：初始走快速排序，但设置一个递归深度限制，一旦递归太深就不再快排，改成堆排序兜底；当区间缩小到一定阈值（通常是 16 或 24）时，切换到插入排序。这样既有快排的平均速度，又避免了最坏情况的灾难。

Java 的Arrays.sort()分成两条线：对基本类型用双轴快速排序，对对象用 TimSort。为什么？因为对对象排序，用户可能依赖稳定性，所以用稳定排序；基本类型相等元素没有身份区分，稳定性没有意义，就用更快的双轴快排。双轴快排选两个 pivot，把数组分成三段，比单轴快排平均比较次数更少。Python 内置排序也是 TimSort，重点是它利用了数据中天然存在的“run”（连续递增或递减段），先把 run 识别出来，再用归并思路合并，所以对真实世界的有序片段特别友好。

从这些实现能看到一个共同规律：算法基础不是让你背 API，而是让你理解“快排+插入排序兜底”、“归并+稳定性”、“堆排+最坏保证”这三个组合的动机。面试里被问到std::sort原理，如果能讲出这些细节，基本就稳稳过关了。

6.2 比较排序的极限：Ω(n log n)是怎么来的

既然有这么多技巧，那么基于比较的排序能不能突破 O(n log n)？答案是不能。这里有一个经典的决策树证明：n 个元素的排列一共有 n! 种可能，而一次比较最多把可能性分成两个分支。如果决策树高度是 h，最多能区分 2^h 种结果，所以要满足 2^h ≥ n!。两边取对数，h ≥ log2(n!)，用斯特林公式展开就是 n log2 n 的数量级。也就是说，不管怎么设计，最坏情况至少需要 n log n 次比较。

这个结论的意义不是让你放弃优化，而是帮你划定边界：通用比较排序，最好平均也就是 O(n log n)。所以当有人说发明了 O(n) 的通用比较排序时，第一反应应该是质疑。但非比较排序不在此列，计数排序、基数排序、桶排序通过利用数据范围或分布的假设，可以做到 O(n+k)，代价是对输入有额外限制。比如手机号排序可以用基数排序，成绩排序可以用桶排序。实际选型时就按这个逻辑来：数据分布有规律、取值范围有限，优先非比较；数据通用、不确定，交给比较排序中的工业混合实现。

这一章的最后，我想再说一个实际体会：工业级排序的很多优化，都是对“最坏情况”和“常数因子”的反复较量。你光会用sort当然可以，但在分布式热点数据、实时流 TopK、外部归并这类场景里，只有把比较排序的思想吃透，才能在出问题时快速定位到底是算法问题还是数据问题。

7. 常见问题与排查技巧实录

7.1 越界死循环：手写排序最常见的翻车现场

手写排序，百分之六十的 bug 都在边界上。冒泡容易把内层j < n - i写成j < n，导致每轮多比较一个已经排好的尾部；选择排序容易在找最小值后忘记min_idx != i判断，原地自交换也行，但没必要；快排的 partition 一旦用了a[j] > pivot而不是>=，遇到大量等于 pivot 的元素就可能来回交换死循环。排查这类问题别只靠眼睛，拿一个 10 个元素的乱序数组，把每轮数组状态打印出来，哪儿越界、哪儿没交换，一眼就能看到。

还有一个隐藏很深的越界：归并排序的临时数组。如果你在递归里分配int tmp[n]，区间长度计算错就会读超出栈；如果合并时回写位置写错，数组会变得乱七八糟。我的做法是统一在排序入口分配一块长度为 n 的临时数组，递归函数只传指针和左右边界，这样既不反复分配内存，也减少了越界概率。

7.2 递归深度爆栈：怎么定位和改写成非递归

快排和归并都有递归版本，递归深度和区间划分相关。快排最坏情况下递归深度等于数组长度，10 万元素有序且每次选到边界 pivot 时，直接栈溢出。定位它非常简单：在递归函数入口打印 low 和 high，如果看到区间长度下降得非常慢，说明 partition 几乎没把数组分开，pivot 选得有问题。解法优先用随机化或三数取中；如果还不够，就设置深度阈值，超过阈值改用堆排序，这就是内省排序。

真要彻底避免递归，可以改成显式栈。快排用一个栈存[low, high]区间，每次弹出一个区间 partition，把左右子区间再压栈。注意压栈顺序无所谓，但别把新区间和旧区间搞混。归并改成迭代也容易：从长度为 1 的子数组开始，不断按 2 倍长度合并，这就是自底向上的归并排序。它不需要递归栈，但需要处理好最后一个不完整区间的边界。工程上，我建议先优化递归而不是一上来就非递归，因为非递归的边界错误更难调。

7.3 稳定性错乱：工程里翻车最隐晦的一次

稳定性是最容易被忽略的比较排序属性。我见过一个真实案例：线上按时间排序用到一个自写的插入排序，后来数据源加了优先级字段，需求变成“先按优先级排，同优先级按时间排”，同事直接把插入排序换成了快速排序，结果大量数据的相对时间顺序乱了，排查了很久才发现是稳定性问题。这个教训非常典型：当排序关键字是复合的，而且存在“主关键字 + 次关键字”时，稳定排序能直接用单次排序搞定；不稳定排序要么额外处理倒序，要么就翻车。

所以面试和实际写代码时，先问自己一句：这次排序需要稳定吗？需要的话老老实实用归并、插入或 TimSort；不需要的话随便用快速排序。很多语言内置排序已经帮你做了决定，但 C 语言里你自己手写时，必须对每个算法的稳定性如同条件反射一样清楚。我把这张常用的复杂度对照表背得很熟，关键时候能救命：

最后再分享一个从我踩坑里长出来的习惯：写完任何手写排序，先跑三组数据，一组乱序、一组基本有序、一组全部相同。乱序验证正确性，基本有序验证有没有利用局部有序的能力，全部相同则能暴露>=和<=这些边界条件写得对不对。这三组数据一过，绝大多数排序实现的隐藏问题都会现原形。