常用排序算法深度解析：从冒泡到快排、归并与堆排序的选型指南

1. 排序算法这桌菜，为什么值得一盘一盘重新品？

说到数据结构与算法中最绕不开的一组基本功，排序算法绝对排得进前三。我这些年带团队、做技术面试，几乎每年都会让候选人现场写一道排序，而且多数情况下会要求用C语言手写，因为内存边界、循环条件都要自己管，稍微不留神就是段错误或者死循环。很多时候候选人能背出"快排平均O(n log n)"这句话，但真让他用十几分钟完整写一个不出错的快排，一下子就暴露了功底。所以这篇内容虽然讲的是"常用的排序算法"这种老话题，我还是想用自己实际的踩坑经历和总结习惯，把冒泡、选择、插入、快排、归并、堆排序，以及计数、基数、桶这类非比较排序盘一遍，重点不只是贴代码，而是把每个算法背后的选型逻辑、稳定性陷阱和应用场景讲透。适合准备笔试面试的人，也适合工作中想知道"什么时候不要无脑调库"的开发者。

1.1 从“手写排序”到“会选排序”，差的不只是代码量

我见过不少工作了几年、平时写业务代码很顺的同事，遇到需要自定义排序的场景还是只会调用语言自带的sort函数。能用sort当然是好事，谁都别闲得慌去造轮子，但麻烦在于：很多场景并不是"给个数组升序排一下"那么简单。

举个我实际遇到过的例子。早期做日志分析系统时，有一批原始日志要按照时间戳升序展示，同一条时间戳内部必须保持采集端的原始顺序。这就是典型的稳定性需求。如果你直接用一个不稳定的排序把整个结构体按时间戳排一遍，结果就是相同时间戳的记录顺序全乱了，看起来像随机抖动，排查半天才发现是排序算法稳定性在作怪。这时候如果只懂"sort一下"，根本不知道该怎么补救；而如果你脑子里有"归并排序是稳定的""快排是不稳定的"这样的坐标系，就知道要么换稳定排序，要么给结构体加一个原始序号做第二关键字。

另一类更常见的情况是性能和内存的取舍。在嵌入式环境或者内存受限的服务里，跑一个归并排序要额外开一块和原数组等长的临时空间，很多时候是不可接受的；而原地排序的堆排序、优化后的快排、插入排序，占用的额外空间几乎可以忽略。不知道这些底牌，选型就只能靠猜测，这也是我建议每个开发者认真过一次排序算法的根本原因：排序不只是"怎么排"，更是"在什么条件下、用什么代价去排"。

1.2 先建立坐标：比较排序与非比较、原地与非原地

在把每个算法拆开之前，我习惯先画一张分类地图，这样后面读代码才不会迷路。

按排序思路，算法分两大类：一类是基于元素之间两两比较的比较排序，包括冒泡、选择、插入、希尔、快排、归并、堆排序；另一类是不靠比较、直接借助数据本身的分布特性来排的非比较排序，典型就是计数排序、基数排序、桶排序。比较排序有一个理论下界，平均时间复杂度下界是O(n log n)，这是信息论决定的，因为每次比较最多帮你区分两种结果，要确定n个元素的唯一排列，至少需要log2(n!)次比较。非比较排序之所以能出现O(n)级别的复杂度，是因为它跳出了"两两比较"的框架，它的代价不是比较次数，而是额外空间和数据范围限制。

另一个维度是原地和非原地。原地排序指不需要和原数组等长的辅助存储，比如插入排序、堆排序、优化后的快排；归并排序因为需要临时数组合并两组有序序列，所以是非原地的。还有一个维度是稳定性，即相等元素的相对顺序在排序后是否保持不变。稳定排序常见的有插入、冒泡、归并、计数、基数；不稳定排序常见的有选择、快排、堆排序、希尔排序。稳定性的重要性我在上文日志案例里已经提过，后面还会反复强调。

先把这个坐标立起来，接下来讲诸算法的时候就顺了。下面从最基础的三兄弟开始。

2. O(n²)级别的基础三兄弟：冒泡、选择、插入的真实定位

很多科班出身的开发者对排序的认知是从冒泡开始的，这没毛病，但要注意：考试喜欢考，不代表生产环境适合用。冒泡、选择、插入三个算法平均复杂度都是O(n²)，但这三兄弟在特定场景下的表现差异非常大，别把它们一概而论。

2.1 冒泡排序：从相邻交换到提前终止

冒泡排序的直观描述就是"每一轮把最大的元素一路交换到末尾，像气泡一样浮上去"。它的实现很朴素，两层循环，内层不断比较相邻元素，如果前一个比后一个大就交换。

void bubble_sort_c(int arr[], int n) { for (int i = 0; i < n - 1; i++) { int swapped = 0; for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; swapped = 1; } } // 某一轮完全没有交换，说明数组已经有序 if (!swapped) break; } }

这里面最关键的一行是if (!swapped) break;，也就是提前终止优化。如果一个数组已经有序，加了这行之后算法只需要扫一轮就能结束，最好情况时间复杂度降到O(n)。我见过一些人面试时写冒泡排序不带这个标记，虽然也能跑通，但一追问"最好情况下还能优化吗"就卡壳，很可惜。

冒泡排序还有一个变体叫双向冒泡，也叫鸡尾酒排序，每轮从左往右把最大值送到右边，再从右往左把最小值送到左边。比如一个数组是2 3 4 5 6 1，单向左冒泡第一轮要把1一路上浮到最前方，中间会有很多无意义的扫描；双向冒泡可以让小值快速到左端。这个优化对小规模乱序数据有一定效果，但它改变不了平均O(n²)的本质。

坦率地说，冒泡排序在工程里几乎不会单独用，数据量一大就是灾难。它最大的价值是教学：代码短、边界直观、能很容易讲清楚"相邻比较+交换"的分治思想是怎么萌芽的。如果你打算在简历里写"熟悉常用排序算法"，至少得能把这个简单版本连同优化一起写出来，否则在面试官那里的第一印象会打折扣。

2.2 选择排序：交换次数少但会把稳定性换掉

选择排序的思路比冒泡更直接：每一轮从待排序区间里选出最小值，把它放到区间最前面，然后缩小区间继续。

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

这里就出现了一个值得深挖的问题：选择排序稳定吗？答案是：不稳定。很多人会愣住，因为选择排序明明只在内存循环里找最小值，并没有跨越式地交换相同元素啊？问题恰恰出在那个交换上。

举个例子，数组是[5, 3, 5, 1]，第一轮找到最小值1，下标是3，然后把下标3的元素和下标0的元素交换，结果数组变成[1, 3, 5, 5]。原来下标0的那个5被换到了下标3的位置，而原来下标2的那个5留在原地，两个5的相对顺序颠倒了。这在只需要比较值时无所谓，但如果你按某个字段排序且对稳定性有要求，就是问题。

选择排序一个常被提起的优点是交换次数少：n个元素的数组，最多进行n-1次交换，比冒泡的交换次数少一个数量级。所以在写操作远贵于比较操作的场景，大到"移动一个元素要付出很高代价"的情况下，选择排序反而可能更合适。当然，这个优势也要辩证看：因为它的比较次数固定是O(n²)，即使交换少，整体效率依然上不了台面。我觉得它在工程里更像一个教学用的参照物，它的价值在于提醒我们"循环找最值"这个思路衍生出来的堆排序，后面会讲。

2.3 插入排序：近乎有序时性价比最高的“元老”

插入排序是我个人比较偏爱的一个基础算法。它的过程很像打扑克牌时整理手牌：左手拿着已经排好序的牌，右手摸到一张新牌，就把它从右往左比，插进合适的位置。代码也很适合用C语言写：

void insertion_sort(int arr[], int n) { 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; } }

插入排序的时间复杂度虽然也是O(n²)，但它有一个隐藏得很深的优点：最好情况下，也就是数组已经有序或接近有序时，时间复杂度是O(n)。细想一下就很合理——每个元素只需要跟前面的少数几个元素比较，甚至一次比较都不用移动，整体效率极高。

这个特性让插入排序成为很多高级排序的"润滑剂"。我们之后会讲到快排和归并的工程实现，几乎都会有一个优化：当待排序区间长度小于某个阈值（比如16、48、64）时，不再继续递归或继续分治，而是直接改用插入排序。原因就是小区间内元素基本有序的概率高，插入排序的常数非常小，反而比递归下去更划算。Java内置排序中也有类似的逻辑。

另外，插入排序是稳定的，这为它在工程中赢得了一席之地。希尔排序其实就是对插入排序的改进，先把相隔一定间距的元素做插入排序，逐步缩小间距，最后一轮gap为1时做完整的插入排序。它把"远距离大数"快速移动到位，平均复杂度可以降到O(n log² n)量级。在排序算法的演进史里，插入排序算得上真正的"元老"，我建议不要因为它是O(n²)就小看它，手写的时候能写出"哨兵优化"或者"折半插入"版本，在面试里往往是加分项。

3. 分治双雄：快速排序与归并排序的底牌和取舍

如果说前面三个O(n²)算法是开胃菜，那么快速排序和归并排序就是排序算法里的主菜。这两个算法都用分治策略，平均复杂度都是O(n log n)，但在稳定性、空间占用、适用场景上走了完全不同的两条路。我每次写排序总结都愿意把它们放在一起对比，因为只有理解了它们的差异，才能真正理解为什么语言内置排序经常是"混合体"而不是单纯某一个算法。

3.1 快速排序：pivot选法和退化问题是核心

快速排序的核心思想是选一个枢纽元素pivot，把数组分成"小于pivot"和"大于pivot"两拨，然后分别递归排序。我最常用的一种写法是双指针从两端向中间扫的版本，它比教科书上的Lomuto分区更容易一次写对：

void quick_sort(int arr[], int low, int high) { if (low >= high) return; int pivot = arr[(low + high) / 2]; int i = low, j = high; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } } quick_sort(arr, low, j); quick_sort(arr, i, high); }

这个写法的好处是循环终止条件比较清晰，i <= j而不是i < j，否则容易漏掉中间元素的处理。递归调用时左半区是[low, j]，右半区是[i, high]，因为当i和j交错时，pivot已经被放到某个合理位置。如果这里写错，最常见的表现就是栈溢出或者结果没排对。

快排最大的痛点是它"怕极端"。如果每次选的pivot都刚好是区间里的最小值或最大值，比如对一个已经有序的数组选固定第一个元素作为pivot，那么每次划分都极端不平衡，递归深度变成n，时间复杂度退化成O(n²)。所以工程实现很少直接取arr[low]当pivot，而是用三数取中：取区间首、中、尾三个元素的中位数作为pivot，能有效规避多数退化场景。还有更激进的做随机选pivot，把最坏情况变成概率事件。

稳定性方面，快排在partition过程中的交换是跨越式的，相同元素的相对顺序无法保证，所以快排是不稳定的。这一点在后面讲选型时很重要。不过它也有巨大的优势：平均情况下常数非常小，原地处理只需要O(log n)的递归栈空间，对缓存比较友好，这也是为什么它能在工程中称霸多年。我的体会是，面试考快排往往不只是考"会不会写"，而是考"能不能说清楚退化原因、三数取中的来由、为什么内置排序要掺入插入排序补强"。别只背一个版本，要能横向展开。

3.2 归并排序：用O(n)空间换稳定的分治

归并排序的思路是"先拆后合"：把数组对半拆到底，然后逐层把两个有序数组合并成一个有序数组。它是教科书级别的稳定排序，时间复杂度稳定在O(n log n)，无论输入数据有多乱，它都不会像快排那样退化。代价是它需要一个和原数组等长的临时数组，空间复杂度O(n)。

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

注意合并时用的是arr[i] <= arr[j]，也就是左半区相等元素优先进入结果。正是这个细节保证了归并的稳定性：左半区在整体顺序上原本就在右半区之前，合并后依然保持这个相对顺序，稳定性就传下去了。如果粗心写成<，相等元素里右半区的会先出来，稳定性就丢了。

归并排序还有一个工程上很重要的变体叫自底向上归并，也叫迭代归并。它不需要递归，从长度为1的区间开始，两两合并，长度翻倍，最终排好整个数组。自底向上归并的额外空间可以做到只用一个临时数组的缓冲交换，对外排序尤其有意义。我后来做大数据量文件排序时用到的外部排序，核心机制就是归并——内存里装不下的数据切块排序并写出临时文件，再用多路归并把所有有序块合并起来。所以别觉得归并排序只能用来应付面试，它是真实出现在大规模数据处理基础设施里的基础算法。

3.3 高级语言内置排序为什么都在做“混合”

研究各个语言的内置排序源码，是理解"实际工程选择"最好的入口。Python内置的sort基于TimSort，它结合了归并排序和插入排序：先扫描出天然有序的片段，把这些片段作为归并的初始块，块内部如果长度很小时用插入排序处理，然后按特定规则做归并。TimSort对真实世界中出现大量"部分有序"数据的场景格外友好，所以成为Python的标准排序。

Java早期版本对大数组用双基准快速排序Dual-Pivot QuickSort，对小数组用插入排序；到了JDK 14之后，对象数组的排序则改用TimSort实现，因为对象排序需要稳定性。而C标准库的qsort并没有强制规定必须用哪种算法，但常见的glibc实现走的是快速排序加堆排序兜底的混合策略，当递归深度过深时切换到堆排序防止退化。很多开发者不知道这一点，以为C的qsort就是纯快排，其实它连空间复杂度都做了明确限制。

这些内置排序的共同逻辑充分说明了一个观点：没有一个排序算法在所有维度上都占优。快排快但怕退化、不稳定；归并稳定但占空间；堆排序空间省但不稳定且常数略高。工程师真正要做的是根据数据规模、内存限制、稳定性需求做组合。理解了这些底牌，你再看qsort、TimSort的源码，就不会觉得那是黑魔法，而是能看懂每一步取舍。

4. 堆排序：适合Top-K和内存受限场景的原地选择型选手

堆排序在面试里的出现率很高，但很多人只是背了代码，不知道它为什么被设计成那个样子，也不知道它在工程里真正擅长什么。堆排序本质上是"选择排序的改进版"：选择排序每次用线性扫描找最小值，堆排序则用堆这种数据结构，让"找最值"的代价从O(n)降到O(log n)。

4.1 堆排序核心：一次建堆、N次下沉

堆是一棵完全二叉树，在数组里可以用下标索引表示，父节点下标i，左孩子是2i+1，右孩子是2i+2。堆排序的思路分两步：先把整个数组建成一个大顶堆，保证堆顶是最大值；然后反复把堆顶和当前末尾元素交换，交换后剔除末尾，再把剩余部分重新调整成堆。

void sift_down(int arr[], int n, int i) { while (1) { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && arr[l] > arr[largest]) largest = l; if (r < n && arr[r] > arr[largest]) largest = r; if (largest == i) break; int tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp; i = largest; } } void heap_sort(int arr[], int n) { // 从最后一个非叶子节点开始建堆 for (int i = n / 2 - 1; i >= 0; i--) { sift_down(arr, n, i); } for (int i = n - 1; i > 0; i--) { int tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp; sift_down(arr, i, 0); } }

建堆那里有个小细节经常被忽略：为什么从n/2 - 1开始向下调整？因为完全二叉树的最后一个非叶子节点下标就是n/2 - 1，从它回推到根节点逐个调整，就能保证每个子树都是堆。如果你从0开始向后调整，那属于"自顶向下建堆"的另一条路线，复杂度是O(n log n)；而从最后一个非叶子节点向前调整，每次下沉的代价总和可以在O(n)内完成。这个差异在理论分析里很重要，别写岔了。

堆排序的时间复杂度是稳定的O(n log n)，空间复杂度O(1)，是"不需要额外空间又能保证最坏情况不退化"的典型代表。从复杂度扑克牌来看，它的牌面很漂亮，尤其在内存受限的C场景里，它确实是比归并更稳的选择。我在嵌入式相关项目里遇到内存只有几十KB的场合，排序基本不敢开大数组，堆排序反而是救星。

4.2 工程里很少直接选堆排序的三个理由

虽然堆排序牌面好看，但你去看看各大语言标准库，几乎没有把它当默认排序。这里面有三个很现实的原因。

第一是常数太大。堆排序的元素访问模式看起来是原地连续数组，实际上在反复下沉过程中，索引跳来跳去，缓存命中率比快排的顺序访问差很多。在数据量大时，即使理论复杂度同一个量级，实际跑起来堆排序也常常明显慢于快排或归并。

第二是不稳定。堆排序的交换是"堆顶和末尾"这种跨越极大距离的交换，相同元素的相对顺序基本不可能保留。凡是遇到稳定性需求，它直接被排除。

第三是建堆后"最后一个元素"的处理方式对数据分布的感知很差。快排和归并都能根据不同数据特征调整策略，堆排序的运行时间基本不关心输入是否有序——这既是优点也是缺点，因为它不会在近乎有序的数据上获得额外收益。

所以我的结论是：堆排序更适合"流式Top-K"和"优先级队列"这类场景，而不是做全套排序的主力。面试时如果你能主动说出"我不建议在通用排序里选堆排序，因为它常数大且不稳定"，面试官对你的排序理解深度反而会有一个好印象。

4.3 Top-K问题才是堆排序的主场

堆排序真正的王牌应用是Top-K问题：比如从一亿个整数里找出最大的100个。最自然的思路是用一个大顶堆做全部排序，然后取前100，但那样至少要O(n log n)的时间且要处理全部数据；更聪明的方案是维护一个大小为K的小顶堆，遍历一遍数据，如果当前元素比堆顶大，就替换堆顶并做一次下沉。这样整体复杂度是O(n log K)，当K远小于n时，效率非常可观，而且堆占用的内存只有K个元素。

用堆做Top-K的好处不仅仅是快，还在于它天然适合数据流场景。数据一批一批到达，不需要全部存储，只需要维护一个固定大小的堆。我在做实时日志排行时就用过这个思路：内存里维护一个容量为10的小顶堆，每来一条新日志判断要不要插入，排名前10的热点条目始终实时可见。这就是堆排序对我而言最大的实用价值。

另外补充一句，求第K大元素还有一个跟快排相关的思路：快排的partition每轮能把pivot放到最终位置，通过判断目标K在左半区还是右半区，只需要递归一边，平均O(n)就能找到。这个算法叫quick select，面试里和Top-K经常成对出现。一个是堆路线，一个是partition路线，各有优势，建议一起掌握。

5. 不比较也能排序：计数、基数、桶的适用范围

很多人学排序学到快排和归并就觉得通关了，压根不知道还有一类算法完全不走"比较"路线，可以在特定条件下做到O(n)排序。我在面试时偶尔会问一句"什么排序能突破O(n log n)下界"，能答出"在数据范围有限的情况下用计数排序"的候选人，说明他对复杂度的来源想得很深，而不是机械记结论。

5.1 计数排序：用计数数组换O(n)

计数排序的适用条件非常苛刻但原理很简单：如果待排序的元素是非负整数，并且取值范围不大，我们可以开一个长度为maxVal+1的计数数组，把每个元素出现的次数统计出来，然后根据计数结果把元素重新放回原数组。

void counting_sort(int arr[], int n, int max_val) { int *cnt = calloc(max_val + 1, sizeof(int)); int *out = malloc(n * sizeof(int)); for (int i = 0; i < n; i++) { cnt[arr[i]]++; } // 前缀和：cnt[i] 表示小于等于 i 的元素个数 for (int i = 1; i <= max_val; i++) { cnt[i] += cnt[i - 1]; } // 从后往前遍历，确保稳定性 for (int i = n - 1; i >= 0; i--) { out[--cnt[arr[i]]] = arr[i]; } for (int i = 0; i < n; i++) { arr[i] = out[i]; } free(cnt); free(out); }

注意这里从后往前遍历数组是为了保证稳定性：相同元素中，后出现的那个会被放到更靠后的位置，从而保留原有顺序。如果你不关心稳定性，从前往后遍历也能得到一个正确排序结果，但稳定性就没了。

计数排序的复杂度是O(n + maxVal)，当maxVal和n同量级时，这就是O(n)时间。但它的空间同样受maxVal限制，处理一百万个取值范围在[0, 1000]的整数很合适；如果取值范围是[0, 10^12]，开这么长的计数数组就是灾难。所以计数排序的本质是用空间换时间，范围小才划算。另外它可以配合偏移量处理负整数，比如先整体加一个偏移让所有数非负，排完再减回来，这些细节考察的时候容易被忽略。

5.2 基数排序：按位多轮，绕开数值范围上限

基数排序是对计数排序的进一步扩展。它不再对整个数值范围开数组，而是把每个数字拆成若干位，一位一位排。最常用的是LSD，低位优先：先按个位排序，再按十位排序，再按百位排序，每轮都使用一种稳定排序作为内部工具（通常就是计数排序），排完之后整体有序。

举个例子，对[329, 457, 657, 839, 436, 720]排序，第一轮按个位得到[720, 329, 839, 436, 457, 657]，第二轮按十位稳定排，得到[720, 329, 436, 839, 457, 657]，第三轮按百位稳定排，得到[329, 436, 457, 657, 720, 839]。每一轮都稳定，上一轮的位序不会被打乱，这是基数排序正确性的关键。

基数排序的时间复杂度是O(d * (n + k))，其中d是数字位数，k是每轮的取值范围基数。d通常很小，比如十进制整数最多10位左右，所以整体可以近似看成O(n)。相比计数排序，基数排序对"数值范围大但位数有限"很友好，比如电话号码、身份证号这类长数字。我在处理一批毫秒级时间戳时也用过，先把时间戳按低位到高位做三到四轮计数排序，比直接在字符串上排序快得多。它的缺点是需要多位额外空间，并且不太适用于浮点数、字符串等不易拆位的类型。

5.3 桶排序：分布均匀是前提，别被理想复杂度骗了

桶排序的思路是：把数据按某种映射函数分到若干个桶里，每个桶内部再排序，最后把所有桶的元素按顺序拼接起来。它的理想情况是数据分布足够均匀，每个桶里元素很少，桶内排序直接退化成常数时间，整体就能到O(n)。最经典的例子是排序0到1之间均匀分布的浮点数：简单除以一个桶宽放进桶里，每个桶内数据差不多均匀。

但桶排序和计数排序、基数排序相比有一个很大的坑：它对数据分布很敏感。如果数据高度集中在某一个桶里，其他桶空着，那么所有数据都挤到一个桶里排序，复杂度直接退化到那个桶内排序的复杂度，可能是O(n²)。这就是为什么只看博客里"桶排序O(n)"就到处用的人，常常会在真实数据上翻车。我自己的建议是：桶排序最好用于你能明确预估数据分布的场景，比如按成绩分段、按区间聚合，如果分布不可控就先别用。

现实中桶排序思想的最大价值还体现在"分桶+降级"这个框架里。分布式数据库对大表排序时经常先按分区键哈希或范围分桶，每个桶各自排好，再合并结果。这和"桶排序"的内核一致，只是桶的数量和调度更复杂。从这个角度说，桶排序不是一个孤立的算法，而是一种工程策略，理解了它，你对大规模排序的分而治之思路会有更具体的认知。

6. 复杂度、稳定性与选型：一张表把排序算法的脾气摊开

讲完具体算法之后，一定要回到一个总控的视角。排序算法太多，细节容易糊成一团。我在做技术总结时习惯把所有常用算法放在一张表里比较，所有关键属性的差别一眼就能看出来。这一节我们就干这件事，顺便说清楚工程选型时到底该怎么决策。

6.1 全套复杂度对照表

下面的表梳理了我个人认为最值得记的排序算法：时间复杂度分最好、平均、最坏三档，空间复杂度是额外空间（不算输入本身），稳定性一列也给了出来。

这张表里有几个值得注意的细节。希尔排序的复杂度是一个非常模糊的"视增量序列而定"：不同的间隔序列能让它的平均复杂度在O(n^1.25)到O(n log² n)之间浮动，所以很多教科书干脆写O(n log² n)或者不写确切值。桶排序的稳定性也不是铁板一块，它取决于桶内部用的排序算法；如果桶内用了快排，整体就谈不上稳定。我之前见过有人统一把桶排序标为稳定，严格说是不准确的。

另一个细节是快排的空间复杂度。它的额外空间不是O(1)，而是递归需要的栈空间，最坏退化成O(n)，平均O(log n)。面试问"快排的空间复杂度"时，不要只答O(1)，那是不严谨的。堆排序虽然额外空间是O(1)，但它本身是非稳定排序，工程上很少用它做全局排序，这一点前面说过。

6.2 语言内置排序在用什么“黑科技”

很多人以为语言内置排序会乖乖挑一个教科书算法从头走到尾，实际并非如此。它们大多是"混合策略"，之所以这样设计，是因为没有任何单一算法能在所有情况下同时做到时间、空间、稳定性都最优。

Python的sort实现是TimSort。它的第一步是扫描数组，把天然有序的片段识别为run，这样遇到近似有序的数据时，几乎不需要做什么工作就能排好。然后它用归并的方式把多个run按特定规则合并，合并时遇到特别短的run，会先用插入排序扩展它。TimSort最经典的应用场景就是现实数据常见的"整体随机但局部有序"。Java的Arrays.sort也是类似套路，对对象数组走TimSort保证稳定，对基本类型数组走双基准快排加上插入排序的混合。

C标准库的qsort呢？它通常不是单纯快排。glibc实现里，当递归深度超过阈值时，会把当前区间切换到堆排序，用堆排序保证最坏情况复杂度不退化；区间够小时，会改用插入排序来减少递归调用开销。这就好比一辆车既有涡轮增压又配了机械增压，低转速和高转速都能兼顾。标准库不是学院派，它愿意把所有算法拿过来缝合。理解这一点，普通人写业务代码时就更没必要自己造排序轮子了，但同时也说明：造轮子的前提是你能看懂这些"缝合手术"背后的原因。

6.3 五道判断题教你现场选型

我在实际工作里遇到"该选哪个排序"的问题，一般就是按下面五条快速判断，大家可以直接把这套思路当模板用：

• 数据量很小，比如几十个元素以内？直接插入排序，写起来最简单，常数也小。
• 数据基本有序，逆序对很少？插入排序或TimSort表现极好，快排反而可能吃亏。
• 对稳定性有硬性要求，比如按多个字段依次排序？归并排序是首选，不要在快排上挣扎。
• 内存极其有限，不允许开大数组？堆排序牺牲稳定性换O(1)空间，或者用优化过的快排加三数取中。
• 数据是整数且范围有限、规模很大？先看计数排序和基数排序，它们能有O(n)的惊喜。

现实里大多数通用场景，最优解是直接用语言内置排序，尤其是内置排序已经做了稳定性妥协和退化保护的时候。只有当上面某一条成为硬约束时，才值得自己写特定算法。这也是我反复强调"先看约束再看算法"的原因。排序选择不是一个"谁快选谁"的问题，而是在时间、空间、稳定性三角里做权衡。

7. 手写排序与面试实战：高频易错点逐个攻破

最后一部分，我把这些年面试别人和自己刷题时最常见的坑集中说一遍。手写排序看着简单，真正一次写对的概率其实不高，因为里面全是细节。这个章节适合在笔试面试前临时抱佛脚，也适合刚接触排序的人对照检查。

7.1 五个最常踩的手写错误

第一个错误是循环边界写错。最典型的是冒泡排序的内层循环for (int j = 0; j < n - 1 - i; j++)，有人会把上界写成n - i，甚至直接写n，导致数组越界或者多做无效比较。快排那个版本也容易在while (i <= j)还是while (i < j)上栽跟头，用i < j时如果pivot恰好需要被划分到某一侧，循环可能提前结束，最后递归区间切错，排序结果不完整。我更推荐用i <= j的双指针版本，终止条件更直观。

第二个错误是交换逻辑冗余或错误。常见的表现是交换后忘记移动指针，比如快排里if (i <= j)交换完没有i++; j--;，循环就会卡在同一次交换上，直接死循环。堆排序里交换堆顶和末尾元素后，忘记缩小堆规模，导致下沉时又把已经排好的元素卷进来，最终排序失败。这种错误在调试时特别讨厌，因为数组大多数时候已经有序，只有某一小段乱掉。

第三个错误是递归没有写终止条件，或终止条件过松。归并排序里if (left >= right) return;必须写，快排里同样要有if (low >= high) return;。漏掉之后，递归会一直切分空区间直到栈溢出。还有一个相关问题是快排的最坏退化：如果输入是高度有序的数据，而你的pivot恰好固定取首元素或末元素，递归深度会逼近n，栈溢出几乎是必然的。

第四个错误是稳定性被无意破坏。写归并排序合并时，条件应该arr[i] <= arr[j]，但很多人会顺手写成<；写计数排序时，从后往前遍历是为了稳定，从前往后就可能丢顺序。这些点单测不一定看得出来，只有当数据里出现大量相等元素时才暴露。面试时如果面试官追问"你这段代码稳定吗"，一定要能准确回答。

第五个错误是临时变量作用域混乱。比如在C语言里，归并排序的临时数组是在每次merge内部malloc还是在函数外层统一分配？外层统一分配性能好很多，但有些人图省事在merge里反复malloc，代码能跑但是效率很差，内存碎片也更严重。面试官看到这种写法，大概率会觉得你只是背了算法，没有真正在工程里实践过。

7.2 三道高频变体题：链表排序、第K大、近乎有序

面试题目不会总是"给一个数组排序"这么直白，更多时候它会换一个壳。我总结了三道最容易出现的变体题，每个都对应一个关键知识点。

第一个是链表排序。数组排序可以用下标，链表不行，所以快排在链表上很不舒服；归并排序只需要把链表断开、合并，非常适合链表结构。对单链表做自顶向下归并或者自底向上归并，复杂度O(n log n)，额外空间O(log n)递归栈，这是链表排序的标准答案。如果你对归并不熟，这道题基本就挂掉了。

第二个是求第K大元素。这道题有两个主流解：小顶堆扫描一遍，复杂度O(n log K)，适合大规模数据流；quick select，平均O(n)，适合一次性的静态数组。我见过很多人一上来就用堆排序把整个数组排完再取下标，从面试角度来看，说明你只记住了算法名字，没有记住每个算法最适用的场景。能主动说出"数据量大用堆，数据都在内存里用quick select"，比写出来的代码更让人加分。

第三个是几乎有序的数组，每个元素离最终位置不会超过K个位置，K远小于n。这题是堆排序的经典应用：用一个大小为K+1的小顶堆，先放入前K+1个元素，每次弹出堆顶放到结果位置，再压入一个新元素。因为每个元素最多移动K位，窗口大小为K+1时，答案一定在当前窗口内。复杂度O(n log K)，比直接排序O(n log n)要好。这一类题考的其实还是"堆排序适合做Top-K和流式处理"这个核心认知，比单纯背堆排序代码管用得多。

7.3 自测脚本：跑一万组随机数据验证你的排序

最后分享一个我实践了好几年的验证方法。写完手写排序后，千万别只拿一个示例数组跑一下就完事，正确性验证需要靠随机数据配合标准库做对照。我自己在C语言里会简单写一段测试：

#include <stdio.h> #include <stdlib.h> #include <time.h> int compare_int(const void *a, const void *b) { return (*(int *)a) - (*(int *)b); } int main() { srand(time(NULL)); for (int round = 0; round < 10000; round++) { int n = rand() % 100 + 1; int arr[105], expected[105]; for (int i = 0; i < n; i++) { arr[i] = rand() % 200; expected[i] = arr[i]; } // 自己写的某种排序 // my_sort(arr, n); qsort(expected, n, sizeof(int), compare_int); for (int i = 0; i < n; i++) { if (arr[i] != expected[i]) { printf("round %d failed at %d\n", round, i); return 1; } } } printf("all tests passed\n"); return 0; }

这个测试框架有几个细节很重要。第一，数组长度要随机，不仅测固定长度，还要覆盖1到100甚至更大；第二，数据范围里刻意保留大量重复值，因为重复值是检验稳定性的天然试金石，不过要注意标准库qsort如果内部实现不稳定，你的稳定排序和它结果可能不同，所以更严格的方案是用带索引的结构体来验证稳定性；第三，每一轮用同一个种子做对比，出现失败信息时才能单独复现。我在自己调试排序代码的时候，这套脚本帮我抓到过很多肉眼根本看不出来的边界问题，尤其是快排的递归切分和堆排序的下沉边界。

这么多年下来，我的一个最大体会是排序算法真正难的不是"记住某个算法的步骤"，而是"在对应场景下想起它"。数据规模小、数据几乎有序、有稳定性要求、内存受限、数据范围有限，这五个条件几乎覆盖了日常开发里所有手动排序的需求。把这套判断逻辑刻进脑子里，比多背几份代码实在得多。