搜索过排序算法的人应该都有类似的感受网上讲归并排序的文章一抓一大把讲计数排序的也不少但很少有人把这两个放在一块讲。我其实特别建议你把它们放到一起看因为它们刚好占据了排序世界里最典型的两个位置——归并排序是比较排序里最“板正”的那个时间复杂度稳定、排序稳定性也稳定计数排序则完全跳出了“比较”的框架换了一条路利用数据本身的值域来直接定位。这两个算法放在一起理解你才能真正明白什么叫“根据数据特性去选算法”而不是拿到题目就默认快排。这篇文章我会把这两个算法的原理推演、时间复杂度推导、代码实现和常见坑一次讲清楚适合正在复习数据结构期末考试的人、备考408的学生以及准备算法面试的开发者。1. 为什么建议把归并排序和计数排序放在一起学1.1 比较排序与非比较排序的分界线排序算法从实现思路上看可以分成两大阵营一类靠比较元素大小来定顺序另一类压根不比较。冒泡、选择、插入、快排、堆排、归并都属于前者它们唯一的共同点就是依赖“比较”这个动作所以只要数据类型定义了比较规则它们就能排序通用性非常强。计数排序、基数排序、桶排序属于后者它们不直接比较元素而是利用数据自身的特殊性质比如值域有限、可以按位拆分、分布均匀等来把元素直接放到它该待的位置上。这里有一个非常关键的认知只要排序过程依赖比较它的时间复杂度下界就是O(n log n)。这个结论在很多教材里是用了决策树模型来证明的——n个元素有n!种排列方式而一次比较最多只能把可能性砍掉一半所以无论如何都需要log2(n!)次比较最终化简出来就是n log n量级。这就意味着只要你的算法还在“比较大小”就不可能突破这个天花板。那计数排序为什么能做到O(n k)不是因为技巧多高明而是因为它根本不做比较所以绕开了这个理论下界。打个比方比较排序就像两个人要比身高必须站在一起才能分出谁高计数排序则像你手里已经有一张按身高分好组的登记表每个人进来直接去自己那格报到不需要两个人碰面。搞清楚这条分界线你对排序算法的整体认知会上一个台阶。1.2 稳定性到底意味着什么“稳定性”是排序算法里经常被一笔带过、但实际很重要的概念。它的定义很简单如果两个元素的值相等在排序结束后它们的相对顺序和排序前保持一致那么这个排序就是稳定的。听起来像是个无关痛痒的性质但在实际工程里它往往决定了排序结果是否正确。举个例子你有一个学生对象数组每个对象有姓名和成绩两个字段现在想按成绩排序成绩相同的人再按姓名排。最简单的做法是先按姓名排一遍再按成绩排一遍。如果第二次用的排序算法是稳定的成绩相同的人在排完序后仍然保持姓名的字母顺序结果就完全正确如果第二次用的是不稳定的排序姓名顺序就被打乱了你又得重新处理一次。所以稳定排序不是学术上的吹毛求疵而是真实的多关键字排序场景里必不可少的能力。归并排序和计数排序正好都是稳定的这也是它们被频繁拿来做算法底层支撑的原因。归并排序的稳定来自合并时“左半边元素优先入队”的细节计数排序的稳定来自“从后往前回填”的细节后面章节我会分别拆开讲。1.3 对比学习的真正价值把归并排序和计数排序放在一起学最大的收获不是多背了两个算法而是建立起“按数据特性选算法”的判断力。归并排序适用于一切可比较的数据代价是时间下不来永远是n log n计数排序在数据范围够小的时候可以做到线性时间但限制也多数据一稀疏或者一变成浮点数就没戏了。这两种算法正好是一对互补的样本一个把分治思想发挥到极致一个把空间换时间用到极致。理解了一这一对以后再接触基数排序、桶排序、外部排序你会觉得它们都是在这个基础思路上的延伸。2. 归并排序核心原理分治三步走里的关键细节2.1 拆分阶段递归边界和中间位置怎么定归并排序的骨架是分治思想的三个动作分解、解决、合并。把一个数组从中间切一刀得到左右两个子数组然后对每个子数组递归地执行同样的操作直到子数组只有一个元素为止。一个元素天然就是有序的不用再做任何处理这就是递归的出口。这个“从一个元素开始往上合并”的过程非常像打比赛的分组淘汰赛先所有人两两分组比赛胜者进入下一轮再两两合并直到最后决出总冠军。每一轮的“比赛规则”都一样但规模在成倍扩大。写代码的时候有两个细节值得注意。第一个是递归边界的写法我习惯用left right作为返回条件这样既覆盖了区间只有一个元素的情况也天然处理了调用方可能传来的空区间比写成left right更稳妥。第二个是中间位置的计算mid left (right - left) / 2看起来比(left right) / 2多写了一点东西但它能避免两个大整数相加时可能出现的溢出。虽然日常开发里很难遇到left和right都接近int上限的情况但面试时主动写出这种写法会显得你确实理解这些细节。2.2 合并阶段两个有序序列怎么合成一个如果说拆分只是机械地切一刀那合并才是归并排序真正的灵魂。假设现在左半边是[19, 42, 57]右半边是[23, 38, 60]两个序列都已经有序要把它们合并成一个整体有序的序列做法就是双指针扫描两个指针分别指向左半边和右半边的开头比较指向的两个元素谁小就先把谁放进结果数组然后对应指针往后移一步某一半边先被取完了就把另一边剩下的元素直接全部追加到结果末尾。还是用刚刚那两组数演示一下19和23比19进结果数组42和23比23进42和38比38进42和60比42进57和60比57进最后把60收尾得到[19, 23, 38, 42, 57, 60]。整个过程一目了然每一步都在蚕食两个有序序列中较小的那个元素。合并操作的复杂度也很容易算两个序列总长度是n双指针从头扫到尾每个元素最多被比较和移动一次所以合并这一步的时间是O(n)。整体排序的时间由这个合并动作递归叠加而来也就是递归树每一层都要O(n)层数log n总时间n log n。2.3 复杂度推导为什么归并排序的时间稳定在O(n log n)我用递推公式把复杂度完整推一遍。设T(n)表示对n个元素排序需要的时间拆分和合并各占一部分可以得到T(n) 2T(n/2) O(n)。这个公式的意思是排序n个元素等于排序两个规模为n/2的子数组再加上一次合并操作的线性时间。往下展开T(n/2) 2T(n/4) O(n/2)代回去得到T(n) 4T(n/4) 2O(n)。继续展开到第k层T(n) 2^k T(n/2^k) kO(n)。当n/2^k 1时也就是拆到只剩一个元素时k log2 n此时T(n) nT(1) n log2 n所以归并排序的时间复杂度是O(n log n)。这里有个容易被忽略的优点归并排序的时间复杂度跟输入数据的初始顺序完全无关。不管输入是正序、倒序还是完全随机它都要经历同样次数的拆分和合并。所以它的最好情况、最坏情况、平均情况都是O(n log n)。相比之下快速排序最坏会退化到O(n^2)归并排序则永远有下限保证。代价就是它需要一个O(n)的额外空间来存放临时数组属于典型的时间换空间的反面——用空间换时间的稳定保障。3. 归并排序的两种代码写法递归版和迭代版怎么选3.1 递归实现逻辑最直观的写法递归版本的代码我直接贴出来这是我在面试和实际项目中用得最多的写法void merge(vectorint nums, int left, int mid, int right, vectorint temp) { int i left, j mid 1, k left; // 双指针扫描谁小谁进 temp while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } // 处理左右两边可能剩余的未合并元素 while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; // 把合并结果拷贝回原数组 for (int p left; p right; p) { nums[p] temp[p]; } } void mergeSort(vectorint nums, int left, int right, vectorint temp) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, left, mid, temp); mergeSort(nums, mid 1, right, temp); merge(nums, left, mid, right, temp); }调用入口很简单先分配一个长度跟原数组一样的临时数组然后传入mergeSortvectorint temp(nums.size()); mergeSort(nums, 0, nums.size() - 1, temp);代码里有一个细节决定了稳定性合并时判断条件是nums[i] nums[j]也就是当左右两边的元素相等时先取左半边的元素放入temp。这样相等元素的相对顺序就被保留下来了所以归并排序是稳定排序。如果把这个误写成相等的元素就会先取右半边的稳定性立刻被破坏。3.2 迭代实现自底向上的合并路线递归写法虽然清晰但并不是唯一的实现方式。递归是自顶向下不断拆分其实也可以反过来自底向上直接合并先把数组看成n个长度为1的有序子数组然后相邻两个合并成有序长度2的子数组再相邻合并成长度4的子数组不断把合并宽度翻倍直到整个数组有序。void mergeSortIterative(vectorint nums) { int n nums.size(); vectorint temp(n); // width 表示当前每个有序子数组的长度 for (int width 1; width n; width * 2) { // 每次合并两个长度为 width 的子数组 for (int left 0; left n; left 2 * width) { int mid min(left width - 1, n - 1); int right min(left 2 * width - 1, n - 1); if (mid right) { merge(nums, left, mid, right, temp); } } } }这段代码最需要小心的是边界控制。当数组长度不是2的整数次幂时最后一组可能凑不满两个完整的子数组。比如数组长度是7width为4时left为0mid被算成3right被算成6恰好能合并但如果数组长度是5width为4时mid min(04-1, 4) 3right min(08-1, 4) 4mid right成立可以合并[0..3]和[4..4]。而有时候右半边可能完全不存在所以要用mid right这个判断拦住无效合并。递归版和迭代版在时间复杂度上没有任何差异都是O(n log n)。迭代版的优势在于没有函数递归调用栈的开销也能避免深度递归在某些极限场景下的栈溢出风险。但递归版的代码更直观面试写起来更快所以我建议面试用递归版工程里如果遇到需要极致性能的大数组排序再考虑迭代版。3.3 一个影响性能的关键细节临时数组的开辟时机我见过不少人在merge函数里这样写每次合并的时候new一个新的临时数组用完之后再释放。这样写功能上没有问题但性能非常差。递归归并有log n层每一层可能执行多次合并这意味着每次合并都要重新分配和释放内存。而内存分配的开销远大于元素拷贝的开销尤其是待排序数组很大的时候这个差距会被放大到肉眼可见的程度。正确的做法是像前面代码那样主函数里一次性分配一个和原数组等长的临时数组把它作为参数传进merge所有层的合并都复用这同一个数组。这样整个排序过程只发生一次内存分配。这是归并排序实现里最值得注意的性能优化点没有之一。还有一点进阶思路递归版在合并之后把temp的数据拷贝回原数组这一步能不能省掉可以但需要你在递归的不同层之间交替使用原数组和临时数组作为排序结果写起来比标准版复杂不少一般考试和面试不会要求到这个程度。能把这个标准版写得又快又对基本功就已经很扎实了。4. 计数排序核心原理用统计代替比较的三个关键步骤4.1 计数、前缀和、回填三个动作各干什么计数排序的思想可以用一句话概括如果数据都是整数而且取值范围不大那我直接统计每个值出现了多少次然后根据这个次数把每个值放回它本来的位置。它不比较元素之间的大小关系而是用自己的值去数组里找位置。我用一个经典例子完整走一遍流程。待排序数组是[2, 5, 3, 0, 2, 3, 0, 3]最小值为0最大值为5取值范围是0到5一共6个可能的值。第一步计数。创建一个长度为6的计数数组count遍历原数组每遇到一个值v就把count[v]加1。统计完得到count [2, 0, 2, 3, 0, 1]意思是值为0的出现2次值为1的出现0次值为2的出现2次值为3的出现3次值为4的出现0次值为5的出现1次。第二步前缀和。对count数组做一次累加让每个位置变成“值小于等于当前下标的所有元素的总数”。累加之后得到count [2, 2, 4, 7, 7, 8]。这时count[i]的含义是整个数组里值i的元素一共有count[i]个。这也意味着值等于i的元素在最终排序结果中应该占据从count[i-1]到count[i]-1这连续的一段位置。第三步回填。创建一个和原数组等长的结果数组result从原数组最后一个元素开始往前遍历每遇到一个值v就先把count[v]减1然后把元素放到result的count[v]位置上。全部回填完之后result就是排序好的数组。我建议你一定要自己在纸上走一遍这组数从最后一个元素3开始count[3]先变成6所以3放到result[6]倒数第二个元素0count[0]变成10放到result[1]再前一个是3count[3]变成53放到result[5]。走完之后result是[0, 0, 2, 2, 3, 3, 3, 5]完全正确。4.2 为什么必须从后往前回填稳定性从哪来计数排序的代码里最容易让人困惑的就是回填那一步为什么要从后往前扫。答案是为了保证稳定性。你知道前缀和数组存的是“最后一个位置”。当原数组里有多个相同值v的时候正着遍历会把先出现的那个v放到更靠后的位置后出现的v反而放到更靠前的位置相同值的相对顺序被颠倒了。而stable排序是要求相等元素保持原有相对顺序的。从后往前遍历时后出现的v先被处理先占据更大的count[v]位置先出现的v后处理占据更小的位置所以它们在result里的前后顺序和原数组完全一致稳定性就保住了。如果面试官让你手写计数排序你写完了之后他大概率会追问一句“为什么从后往前”这一节的内容就是标准答案。如果你是从前往后扫代码虽然也能排对顺序但稳定性会被破坏这对计数排序来说是致命的因为计数排序最重要的应用之一就是作为基数排序的底层排序而基数排序必须要求底层是稳定排序。4.3 负数怎么处理偏移量是计数排序的常规操作很多新手写计数排序只能处理非负整数因为数组下标不能是负数。遇到负数就蒙了。其实解决方案很简单先找整个数组的最小值minVal然后把每个元素映射成nums[i] - minVal来统计。这样即使数组里有负数映射之后也全部变成非负下标了。处理完前缀和回填之后下标再加回偏移量得到的就是真实值。完整代码如下我用了minVal做了一个偏移处理这也是实际运用中比较规范的写法void countingSort(vectorint nums) { if (nums.empty()) return; int maxVal *max_element(nums.begin(), nums.end()); int minVal *min_element(nums.begin(), nums.end()); int range maxVal - minVal 1; vectorint count(range, 0); for (int num : nums) { count[num - minVal]; } for (int i 1; i range; i) { count[i] count[i - 1]; } vectorint result(nums.size()); for (int i nums.size() - 1; i 0; i--) { result[--count[nums[i] - minVal]] nums[i]; } nums result; }这段代码里--count的写法简洁且容易出错。count[nums[i] - minVal]存的是“值等于nums[i]的最大位置”先减1再使用得到的才是当前这个元素真正要放的位置。4.4 复杂度评估O(n k)只在特定条件下成立计数排序的时间复杂度是O(n k)其中k是数据范围也就是maxVal - minVal 1。遍历原数组统计每个值出现次数要O(n)遍历count数组做前缀和要O(k)最后回填要O(n)加起来是O(n k)。空间复杂度同样是O(k)因为需要一个长度为k的辅助数组。这个复杂度看着很诱人但要注意它的前提k不能太大。如果数据范围是0到1亿但实际只有1000个数据点那count数组就要开1亿个单位长度大部分位置都是浪费的。这时候计数排序就不划算甚至比普通比较排序更慢因为光是初始化一个长度为1亿的数组就要花不少时间。只有当k跟n在同一数量级或者比n小时计数排序的优势才真正体现出来。这也是为什么计数排序通常被限定在“数据范围有限”的场景中使用。5. 归并排序和计数排序怎么选差异对比与经典应用场景5.1 一张对比表看清本质差异我用表格把两组算法的核心差异列出来方便你复习的时候扫一眼就抓住重点维度归并排序计数排序排序类型比较排序非比较排序平均时间复杂度O(n log n)O(n k)最坏时间复杂度O(n log n)O(n k)额外空间复杂度O(n)O(k)稳定性稳定稳定适用数据类型任何可比较的数据值域有限的整数是否受输入初始顺序影响不受影响不受影响核心代价空间换时间空间换时间但k不能太大从这张表可以很清晰地看到两个算法的定位差异归并排序是“通吃型选手”数据形式不设限代价是稳定付出O(n log n)和O(n)空间计数排序是“特化型选手”只对有限范围的整数数据生效但在这种特定条件下它能跑到线性时间。5.2 归并排序的经典战场逆序对、外部排序、链表排序归并排序有三个在工程和面试里特别常见的应用场景每一个都值得单独说。第一个是求逆序对。给你一个数组问有多少对索引(i, j)满足i j但nums[i] nums[j]。暴力做法是双重循环O(n^2)但用归并排序可以在合并的过程中顺带统计出来当右半边的nums[j]小于左半边的nums[i]时左半边从i到mid的所有元素都比nums[j]大所以当前贡献了mid - i 1个逆序对。累加下去总复杂度就是归并排序的O(n log n)。这道题在很多大厂面试里出现频率极高核心考点就是你能不能想到“归并的合并过程天然能统计逆序对”。第二个是外部排序。当待排序的数据量大到无法一次性读入内存时常见做法是把数据切成若干个能装进内存的块每个块内部排序后写入磁盘最后用归并的思路把这些有序块多路合并成一个大文件。这个场景下归并排序不是可选项而是必经之路因为它只需要顺序读写就能完成合并非常契合磁盘的特点。第三个是链表排序。链表不支持随机访问快速排序在链表上会退化成O(n^2)而归并排序只需要顺序访问接点就能完成合并时间复杂度依然保持O(n log n)还能保证稳定性。所以如果你遇到“对链表排序”的题最好立刻就意识到归并排序才是解法。5.3 计数排序的高光时刻基数排序的基石和有限整数排序计数排序单独出现的场景反而是少数它更常见的角色是给基数排序做底层支撑。基数排序的思路是“按位排序”先按个位排一遍再按十位排一遍再按百位排一遍通过多轮“低位优先”的稳定排序最终整体有序。每轮按位的排序范围只有0到9这正好是计数排序最擅长处理的场景k极小稳定线性时间。可以说没有计数排序基数排序的实现复杂度和性能都会大打折扣。除此之外少量且值域有限的数据也适合直接用计数排序。比如给100万人的年龄排序年龄范围大概在0到120之间k非常小计数排序性能远胜任何比较排序再比如按考试成绩等级、订单状态码、颜色编号等离散字段排序都属于“值域小、数据量大”的典型场景用计数排序就是降维打击。顺便提醒一个相反的例子如果数据范围大、分布稀疏比如从0到100000之间随机取100个数那计数排序会开出一个巨大的count数组内存浪费严重这时候老老实实用快排或者归并反而更合适。判断标准跟上文说的一样看k和n的关系。6. 考试面试里的高频失分点与实用避坑经验6.1 归并排序最容易被扣分的两个位置我在带实习生的过程中发现归并排序的手写错误高发地主要集中在这两个位置。第一个是递归边界条件写错。有些人会把if (left right) return;写成if (left right) return;如果递归过程中出现左边界大于右边界的情况就会无限递归直到栈溢出。虽然归并排序的拆分过程通常不会出现left right但写成能让代码对异常输入有更好的容忍度防止在调用边界上出现意外。第二个是合并结束后忘记把temp的数据拷贝回原数组。这一步漏掉的话整个数组看起来就像没排序一样。我在面试里见过太多人在这上面翻车。写代码的时候可以在注释里把“把temp区间拷回原数组”这个动作单独标出来强迫自己不要漏。另一个类似的低错是把for (int p left; p right; p)写成p right这种边界多一格少一格的错误对归并排序来说是致命的因为最后一个元素永远不会被拷回去。6.2 计数排序的“偏移量”和“回填方向”陷阱计数排序的坑集中在下标处理和遍历方向上。第一忘了处理偏移量。如果数组里有负数或最小值不是0直接用nums[i]做count下标会数组越界。正确做法永远是先找minVal然后用nums[i] - minVal作为下标。我建议凡是写计数排序不管数据有没有负数都先做偏移这样逻辑统一也避免在数据变化时莫名其妙踩雷。第二count数组的长度错误。有人会直接new int[maxVal 1]这样在处理负数时直接崩溃在处理0开头但不是从0开始时又会浪费空间。正确的长度是maxVal - minVal 1对应的是数据的取值范围而不是最大值。这个概念虽然简单但我见过太多次因为这个小细节导致代码在边缘数据上挂掉的案例。第三回填方向。前面说了必须从后往前遍历原数组。面试时即使你已经写出了正确代码也强烈建议主动跟面试官解释一句“因为前缀和数组存的是每个值的最后一个位置从后往前遍历才能保证稳定性”。这句话能体现你不是背代码而是真的懂原理。6.3 准备笔试面试时值得养成的几个好习惯在面试和学习总结中我会刻意去养成一些习惯让我在手写算法时出错率比较低。先说归并排序。面试中大多数时候用户没有要求复杂度限制所以优先给递归版本因为它最好写、最好解释。但如果用户提到了“数据量很大”或者“递归可能会爆栈”你就要能切换到迭代版本所以两个版本都要练到能默写的程度才行。另外如果面试官让你对归并排序做时间分析一定要提到“无论输入顺序如何归并排序的时间复杂度都稳定在O(n log n)”这比单纯背一个复杂度公式深刻得多。再说计数排序。遇到“给定大量整数范围很小要求线性时间排序”这类题要立刻反应到计数排序。写代码的时候先写一圈注释把步骤列出来比如“1. 统计频率 2. 前缀和 3. 回填”这样既方便自己按步骤写也能让面试官看得清你的思路。对408和期末复习来说还要求你会记归并排序的趟数公式对n个元素做二路归并排序需要ceil(log2 n)趟。这个数经常出现在选择题里理解了递归树层数的推导就能记住不用死背。最后分享一个我自己的小经验学排序算法的时候别只看代码一定要每个算法都找一组小数据亲手在纸上走一遍全过程。归并排序就画递归树计数排序就把count数组每一步的前缀和写出来再对照代码看每一步对应的是哪一行。这个过程花不了多长时间但对记忆的锚定作用远大于刷十道题。把这两个算法用纸笔走通之后你会发现它们背后的思想——分治和用空间换时间——会浸润到你解决其他问题的思路里去。 
长河君 · 2026/9/9 18:43:51 · 阅读 1.2k 归并排序与计数排序对比：原理、复杂度与实战选择
搜索过排序算法的人应该都有类似的感受网上讲归并排序的文章一抓一大把讲计数排序的也不少但很少有人把这两个放在一块讲。我其实特别建议你把它们放到一起看因为它们刚好占据了排序世界里最典型的两个位置——归并排序是比较排序里最“板正”的那个时间复杂度稳定、排序稳定性也稳定计数排序则完全跳出了“比较”的框架换了一条路利用数据本身的值域来直接定位。这两个算法放在一起理解你才能真正明白什么叫“根据数据特性去选算法”而不是拿到题目就默认快排。这篇文章我会把这两个算法的原理推演、时间复杂度推导、代码实现和常见坑一次讲清楚适合正在复习数据结构期末考试的人、备考408的学生以及准备算法面试的开发者。1. 为什么建议把归并排序和计数排序放在一起学1.1 比较排序与非比较排序的分界线排序算法从实现思路上看可以分成两大阵营一类靠比较元素大小来定顺序另一类压根不比较。冒泡、选择、插入、快排、堆排、归并都属于前者它们唯一的共同点就是依赖“比较”这个动作所以只要数据类型定义了比较规则它们就能排序通用性非常强。计数排序、基数排序、桶排序属于后者它们不直接比较元素而是利用数据自身的特殊性质比如值域有限、可以按位拆分、分布均匀等来把元素直接放到它该待的位置上。这里有一个非常关键的认知只要排序过程依赖比较它的时间复杂度下界就是O(n log n)。这个结论在很多教材里是用了决策树模型来证明的——n个元素有n!种排列方式而一次比较最多只能把可能性砍掉一半所以无论如何都需要log2(n!)次比较最终化简出来就是n log n量级。这就意味着只要你的算法还在“比较大小”就不可能突破这个天花板。那计数排序为什么能做到O(n k)不是因为技巧多高明而是因为它根本不做比较所以绕开了这个理论下界。打个比方比较排序就像两个人要比身高必须站在一起才能分出谁高计数排序则像你手里已经有一张按身高分好组的登记表每个人进来直接去自己那格报到不需要两个人碰面。搞清楚这条分界线你对排序算法的整体认知会上一个台阶。1.2 稳定性到底意味着什么“稳定性”是排序算法里经常被一笔带过、但实际很重要的概念。它的定义很简单如果两个元素的值相等在排序结束后它们的相对顺序和排序前保持一致那么这个排序就是稳定的。听起来像是个无关痛痒的性质但在实际工程里它往往决定了排序结果是否正确。举个例子你有一个学生对象数组每个对象有姓名和成绩两个字段现在想按成绩排序成绩相同的人再按姓名排。最简单的做法是先按姓名排一遍再按成绩排一遍。如果第二次用的排序算法是稳定的成绩相同的人在排完序后仍然保持姓名的字母顺序结果就完全正确如果第二次用的是不稳定的排序姓名顺序就被打乱了你又得重新处理一次。所以稳定排序不是学术上的吹毛求疵而是真实的多关键字排序场景里必不可少的能力。归并排序和计数排序正好都是稳定的这也是它们被频繁拿来做算法底层支撑的原因。归并排序的稳定来自合并时“左半边元素优先入队”的细节计数排序的稳定来自“从后往前回填”的细节后面章节我会分别拆开讲。1.3 对比学习的真正价值把归并排序和计数排序放在一起学最大的收获不是多背了两个算法而是建立起“按数据特性选算法”的判断力。归并排序适用于一切可比较的数据代价是时间下不来永远是n log n计数排序在数据范围够小的时候可以做到线性时间但限制也多数据一稀疏或者一变成浮点数就没戏了。这两种算法正好是一对互补的样本一个把分治思想发挥到极致一个把空间换时间用到极致。理解了一这一对以后再接触基数排序、桶排序、外部排序你会觉得它们都是在这个基础思路上的延伸。2. 归并排序核心原理分治三步走里的关键细节2.1 拆分阶段递归边界和中间位置怎么定归并排序的骨架是分治思想的三个动作分解、解决、合并。把一个数组从中间切一刀得到左右两个子数组然后对每个子数组递归地执行同样的操作直到子数组只有一个元素为止。一个元素天然就是有序的不用再做任何处理这就是递归的出口。这个“从一个元素开始往上合并”的过程非常像打比赛的分组淘汰赛先所有人两两分组比赛胜者进入下一轮再两两合并直到最后决出总冠军。每一轮的“比赛规则”都一样但规模在成倍扩大。写代码的时候有两个细节值得注意。第一个是递归边界的写法我习惯用left right作为返回条件这样既覆盖了区间只有一个元素的情况也天然处理了调用方可能传来的空区间比写成left right更稳妥。第二个是中间位置的计算mid left (right - left) / 2看起来比(left right) / 2多写了一点东西但它能避免两个大整数相加时可能出现的溢出。虽然日常开发里很难遇到left和right都接近int上限的情况但面试时主动写出这种写法会显得你确实理解这些细节。2.2 合并阶段两个有序序列怎么合成一个如果说拆分只是机械地切一刀那合并才是归并排序真正的灵魂。假设现在左半边是[19, 42, 57]右半边是[23, 38, 60]两个序列都已经有序要把它们合并成一个整体有序的序列做法就是双指针扫描两个指针分别指向左半边和右半边的开头比较指向的两个元素谁小就先把谁放进结果数组然后对应指针往后移一步某一半边先被取完了就把另一边剩下的元素直接全部追加到结果末尾。还是用刚刚那两组数演示一下19和23比19进结果数组42和23比23进42和38比38进42和60比42进57和60比57进最后把60收尾得到[19, 23, 38, 42, 57, 60]。整个过程一目了然每一步都在蚕食两个有序序列中较小的那个元素。合并操作的复杂度也很容易算两个序列总长度是n双指针从头扫到尾每个元素最多被比较和移动一次所以合并这一步的时间是O(n)。整体排序的时间由这个合并动作递归叠加而来也就是递归树每一层都要O(n)层数log n总时间n log n。2.3 复杂度推导为什么归并排序的时间稳定在O(n log n)我用递推公式把复杂度完整推一遍。设T(n)表示对n个元素排序需要的时间拆分和合并各占一部分可以得到T(n) 2T(n/2) O(n)。这个公式的意思是排序n个元素等于排序两个规模为n/2的子数组再加上一次合并操作的线性时间。往下展开T(n/2) 2T(n/4) O(n/2)代回去得到T(n) 4T(n/4) 2O(n)。继续展开到第k层T(n) 2^k T(n/2^k) kO(n)。当n/2^k 1时也就是拆到只剩一个元素时k log2 n此时T(n) nT(1) n log2 n所以归并排序的时间复杂度是O(n log n)。这里有个容易被忽略的优点归并排序的时间复杂度跟输入数据的初始顺序完全无关。不管输入是正序、倒序还是完全随机它都要经历同样次数的拆分和合并。所以它的最好情况、最坏情况、平均情况都是O(n log n)。相比之下快速排序最坏会退化到O(n^2)归并排序则永远有下限保证。代价就是它需要一个O(n)的额外空间来存放临时数组属于典型的时间换空间的反面——用空间换时间的稳定保障。3. 归并排序的两种代码写法递归版和迭代版怎么选3.1 递归实现逻辑最直观的写法递归版本的代码我直接贴出来这是我在面试和实际项目中用得最多的写法void merge(vectorint nums, int left, int mid, int right, vectorint temp) { int i left, j mid 1, k left; // 双指针扫描谁小谁进 temp while (i mid j right) { if (nums[i] nums[j]) { temp[k] nums[i]; } else { temp[k] nums[j]; } } // 处理左右两边可能剩余的未合并元素 while (i mid) temp[k] nums[i]; while (j right) temp[k] nums[j]; // 把合并结果拷贝回原数组 for (int p left; p right; p) { nums[p] temp[p]; } } void mergeSort(vectorint nums, int left, int right, vectorint temp) { if (left right) return; int mid left (right - left) / 2; mergeSort(nums, left, mid, temp); mergeSort(nums, mid 1, right, temp); merge(nums, left, mid, right, temp); }调用入口很简单先分配一个长度跟原数组一样的临时数组然后传入mergeSortvectorint temp(nums.size()); mergeSort(nums, 0, nums.size() - 1, temp);代码里有一个细节决定了稳定性合并时判断条件是nums[i] nums[j]也就是当左右两边的元素相等时先取左半边的元素放入temp。这样相等元素的相对顺序就被保留下来了所以归并排序是稳定排序。如果把这个误写成相等的元素就会先取右半边的稳定性立刻被破坏。3.2 迭代实现自底向上的合并路线递归写法虽然清晰但并不是唯一的实现方式。递归是自顶向下不断拆分其实也可以反过来自底向上直接合并先把数组看成n个长度为1的有序子数组然后相邻两个合并成有序长度2的子数组再相邻合并成长度4的子数组不断把合并宽度翻倍直到整个数组有序。void mergeSortIterative(vectorint nums) { int n nums.size(); vectorint temp(n); // width 表示当前每个有序子数组的长度 for (int width 1; width n; width * 2) { // 每次合并两个长度为 width 的子数组 for (int left 0; left n; left 2 * width) { int mid min(left width - 1, n - 1); int right min(left 2 * width - 1, n - 1); if (mid right) { merge(nums, left, mid, right, temp); } } } }这段代码最需要小心的是边界控制。当数组长度不是2的整数次幂时最后一组可能凑不满两个完整的子数组。比如数组长度是7width为4时left为0mid被算成3right被算成6恰好能合并但如果数组长度是5width为4时mid min(04-1, 4) 3right min(08-1, 4) 4mid right成立可以合并[0..3]和[4..4]。而有时候右半边可能完全不存在所以要用mid right这个判断拦住无效合并。递归版和迭代版在时间复杂度上没有任何差异都是O(n log n)。迭代版的优势在于没有函数递归调用栈的开销也能避免深度递归在某些极限场景下的栈溢出风险。但递归版的代码更直观面试写起来更快所以我建议面试用递归版工程里如果遇到需要极致性能的大数组排序再考虑迭代版。3.3 一个影响性能的关键细节临时数组的开辟时机我见过不少人在merge函数里这样写每次合并的时候new一个新的临时数组用完之后再释放。这样写功能上没有问题但性能非常差。递归归并有log n层每一层可能执行多次合并这意味着每次合并都要重新分配和释放内存。而内存分配的开销远大于元素拷贝的开销尤其是待排序数组很大的时候这个差距会被放大到肉眼可见的程度。正确的做法是像前面代码那样主函数里一次性分配一个和原数组等长的临时数组把它作为参数传进merge所有层的合并都复用这同一个数组。这样整个排序过程只发生一次内存分配。这是归并排序实现里最值得注意的性能优化点没有之一。还有一点进阶思路递归版在合并之后把temp的数据拷贝回原数组这一步能不能省掉可以但需要你在递归的不同层之间交替使用原数组和临时数组作为排序结果写起来比标准版复杂不少一般考试和面试不会要求到这个程度。能把这个标准版写得又快又对基本功就已经很扎实了。4. 计数排序核心原理用统计代替比较的三个关键步骤4.1 计数、前缀和、回填三个动作各干什么计数排序的思想可以用一句话概括如果数据都是整数而且取值范围不大那我直接统计每个值出现了多少次然后根据这个次数把每个值放回它本来的位置。它不比较元素之间的大小关系而是用自己的值去数组里找位置。我用一个经典例子完整走一遍流程。待排序数组是[2, 5, 3, 0, 2, 3, 0, 3]最小值为0最大值为5取值范围是0到5一共6个可能的值。第一步计数。创建一个长度为6的计数数组count遍历原数组每遇到一个值v就把count[v]加1。统计完得到count [2, 0, 2, 3, 0, 1]意思是值为0的出现2次值为1的出现0次值为2的出现2次值为3的出现3次值为4的出现0次值为5的出现1次。第二步前缀和。对count数组做一次累加让每个位置变成“值小于等于当前下标的所有元素的总数”。累加之后得到count [2, 2, 4, 7, 7, 8]。这时count[i]的含义是整个数组里值i的元素一共有count[i]个。这也意味着值等于i的元素在最终排序结果中应该占据从count[i-1]到count[i]-1这连续的一段位置。第三步回填。创建一个和原数组等长的结果数组result从原数组最后一个元素开始往前遍历每遇到一个值v就先把count[v]减1然后把元素放到result的count[v]位置上。全部回填完之后result就是排序好的数组。我建议你一定要自己在纸上走一遍这组数从最后一个元素3开始count[3]先变成6所以3放到result[6]倒数第二个元素0count[0]变成10放到result[1]再前一个是3count[3]变成53放到result[5]。走完之后result是[0, 0, 2, 2, 3, 3, 3, 5]完全正确。4.2 为什么必须从后往前回填稳定性从哪来计数排序的代码里最容易让人困惑的就是回填那一步为什么要从后往前扫。答案是为了保证稳定性。你知道前缀和数组存的是“最后一个位置”。当原数组里有多个相同值v的时候正着遍历会把先出现的那个v放到更靠后的位置后出现的v反而放到更靠前的位置相同值的相对顺序被颠倒了。而stable排序是要求相等元素保持原有相对顺序的。从后往前遍历时后出现的v先被处理先占据更大的count[v]位置先出现的v后处理占据更小的位置所以它们在result里的前后顺序和原数组完全一致稳定性就保住了。如果面试官让你手写计数排序你写完了之后他大概率会追问一句“为什么从后往前”这一节的内容就是标准答案。如果你是从前往后扫代码虽然也能排对顺序但稳定性会被破坏这对计数排序来说是致命的因为计数排序最重要的应用之一就是作为基数排序的底层排序而基数排序必须要求底层是稳定排序。4.3 负数怎么处理偏移量是计数排序的常规操作很多新手写计数排序只能处理非负整数因为数组下标不能是负数。遇到负数就蒙了。其实解决方案很简单先找整个数组的最小值minVal然后把每个元素映射成nums[i] - minVal来统计。这样即使数组里有负数映射之后也全部变成非负下标了。处理完前缀和回填之后下标再加回偏移量得到的就是真实值。完整代码如下我用了minVal做了一个偏移处理这也是实际运用中比较规范的写法void countingSort(vectorint nums) { if (nums.empty()) return; int maxVal *max_element(nums.begin(), nums.end()); int minVal *min_element(nums.begin(), nums.end()); int range maxVal - minVal 1; vectorint count(range, 0); for (int num : nums) { count[num - minVal]; } for (int i 1; i range; i) { count[i] count[i - 1]; } vectorint result(nums.size()); for (int i nums.size() - 1; i 0; i--) { result[--count[nums[i] - minVal]] nums[i]; } nums result; }这段代码里--count的写法简洁且容易出错。count[nums[i] - minVal]存的是“值等于nums[i]的最大位置”先减1再使用得到的才是当前这个元素真正要放的位置。4.4 复杂度评估O(n k)只在特定条件下成立计数排序的时间复杂度是O(n k)其中k是数据范围也就是maxVal - minVal 1。遍历原数组统计每个值出现次数要O(n)遍历count数组做前缀和要O(k)最后回填要O(n)加起来是O(n k)。空间复杂度同样是O(k)因为需要一个长度为k的辅助数组。这个复杂度看着很诱人但要注意它的前提k不能太大。如果数据范围是0到1亿但实际只有1000个数据点那count数组就要开1亿个单位长度大部分位置都是浪费的。这时候计数排序就不划算甚至比普通比较排序更慢因为光是初始化一个长度为1亿的数组就要花不少时间。只有当k跟n在同一数量级或者比n小时计数排序的优势才真正体现出来。这也是为什么计数排序通常被限定在“数据范围有限”的场景中使用。5. 归并排序和计数排序怎么选差异对比与经典应用场景5.1 一张对比表看清本质差异我用表格把两组算法的核心差异列出来方便你复习的时候扫一眼就抓住重点维度归并排序计数排序排序类型比较排序非比较排序平均时间复杂度O(n log n)O(n k)最坏时间复杂度O(n log n)O(n k)额外空间复杂度O(n)O(k)稳定性稳定稳定适用数据类型任何可比较的数据值域有限的整数是否受输入初始顺序影响不受影响不受影响核心代价空间换时间空间换时间但k不能太大从这张表可以很清晰地看到两个算法的定位差异归并排序是“通吃型选手”数据形式不设限代价是稳定付出O(n log n)和O(n)空间计数排序是“特化型选手”只对有限范围的整数数据生效但在这种特定条件下它能跑到线性时间。5.2 归并排序的经典战场逆序对、外部排序、链表排序归并排序有三个在工程和面试里特别常见的应用场景每一个都值得单独说。第一个是求逆序对。给你一个数组问有多少对索引(i, j)满足i j但nums[i] nums[j]。暴力做法是双重循环O(n^2)但用归并排序可以在合并的过程中顺带统计出来当右半边的nums[j]小于左半边的nums[i]时左半边从i到mid的所有元素都比nums[j]大所以当前贡献了mid - i 1个逆序对。累加下去总复杂度就是归并排序的O(n log n)。这道题在很多大厂面试里出现频率极高核心考点就是你能不能想到“归并的合并过程天然能统计逆序对”。第二个是外部排序。当待排序的数据量大到无法一次性读入内存时常见做法是把数据切成若干个能装进内存的块每个块内部排序后写入磁盘最后用归并的思路把这些有序块多路合并成一个大文件。这个场景下归并排序不是可选项而是必经之路因为它只需要顺序读写就能完成合并非常契合磁盘的特点。第三个是链表排序。链表不支持随机访问快速排序在链表上会退化成O(n^2)而归并排序只需要顺序访问接点就能完成合并时间复杂度依然保持O(n log n)还能保证稳定性。所以如果你遇到“对链表排序”的题最好立刻就意识到归并排序才是解法。5.3 计数排序的高光时刻基数排序的基石和有限整数排序计数排序单独出现的场景反而是少数它更常见的角色是给基数排序做底层支撑。基数排序的思路是“按位排序”先按个位排一遍再按十位排一遍再按百位排一遍通过多轮“低位优先”的稳定排序最终整体有序。每轮按位的排序范围只有0到9这正好是计数排序最擅长处理的场景k极小稳定线性时间。可以说没有计数排序基数排序的实现复杂度和性能都会大打折扣。除此之外少量且值域有限的数据也适合直接用计数排序。比如给100万人的年龄排序年龄范围大概在0到120之间k非常小计数排序性能远胜任何比较排序再比如按考试成绩等级、订单状态码、颜色编号等离散字段排序都属于“值域小、数据量大”的典型场景用计数排序就是降维打击。顺便提醒一个相反的例子如果数据范围大、分布稀疏比如从0到100000之间随机取100个数那计数排序会开出一个巨大的count数组内存浪费严重这时候老老实实用快排或者归并反而更合适。判断标准跟上文说的一样看k和n的关系。6. 考试面试里的高频失分点与实用避坑经验6.1 归并排序最容易被扣分的两个位置我在带实习生的过程中发现归并排序的手写错误高发地主要集中在这两个位置。第一个是递归边界条件写错。有些人会把if (left right) return;写成if (left right) return;如果递归过程中出现左边界大于右边界的情况就会无限递归直到栈溢出。虽然归并排序的拆分过程通常不会出现left right但写成能让代码对异常输入有更好的容忍度防止在调用边界上出现意外。第二个是合并结束后忘记把temp的数据拷贝回原数组。这一步漏掉的话整个数组看起来就像没排序一样。我在面试里见过太多人在这上面翻车。写代码的时候可以在注释里把“把temp区间拷回原数组”这个动作单独标出来强迫自己不要漏。另一个类似的低错是把for (int p left; p right; p)写成p right这种边界多一格少一格的错误对归并排序来说是致命的因为最后一个元素永远不会被拷回去。6.2 计数排序的“偏移量”和“回填方向”陷阱计数排序的坑集中在下标处理和遍历方向上。第一忘了处理偏移量。如果数组里有负数或最小值不是0直接用nums[i]做count下标会数组越界。正确做法永远是先找minVal然后用nums[i] - minVal作为下标。我建议凡是写计数排序不管数据有没有负数都先做偏移这样逻辑统一也避免在数据变化时莫名其妙踩雷。第二count数组的长度错误。有人会直接new int[maxVal 1]这样在处理负数时直接崩溃在处理0开头但不是从0开始时又会浪费空间。正确的长度是maxVal - minVal 1对应的是数据的取值范围而不是最大值。这个概念虽然简单但我见过太多次因为这个小细节导致代码在边缘数据上挂掉的案例。第三回填方向。前面说了必须从后往前遍历原数组。面试时即使你已经写出了正确代码也强烈建议主动跟面试官解释一句“因为前缀和数组存的是每个值的最后一个位置从后往前遍历才能保证稳定性”。这句话能体现你不是背代码而是真的懂原理。6.3 准备笔试面试时值得养成的几个好习惯在面试和学习总结中我会刻意去养成一些习惯让我在手写算法时出错率比较低。先说归并排序。面试中大多数时候用户没有要求复杂度限制所以优先给递归版本因为它最好写、最好解释。但如果用户提到了“数据量很大”或者“递归可能会爆栈”你就要能切换到迭代版本所以两个版本都要练到能默写的程度才行。另外如果面试官让你对归并排序做时间分析一定要提到“无论输入顺序如何归并排序的时间复杂度都稳定在O(n log n)”这比单纯背一个复杂度公式深刻得多。再说计数排序。遇到“给定大量整数范围很小要求线性时间排序”这类题要立刻反应到计数排序。写代码的时候先写一圈注释把步骤列出来比如“1. 统计频率 2. 前缀和 3. 回填”这样既方便自己按步骤写也能让面试官看得清你的思路。对408和期末复习来说还要求你会记归并排序的趟数公式对n个元素做二路归并排序需要ceil(log2 n)趟。这个数经常出现在选择题里理解了递归树层数的推导就能记住不用死背。最后分享一个我自己的小经验学排序算法的时候别只看代码一定要每个算法都找一组小数据亲手在纸上走一遍全过程。归并排序就画递归树计数排序就把count数组每一步的前缀和写出来再对照代码看每一步对应的是哪一行。这个过程花不了多长时间但对记忆的锚定作用远大于刷十道题。把这两个算法用纸笔走通之后你会发现它们背后的思想——分治和用空间换时间——会浸润到你解决其他问题的思路里去。