看到“算法——C/C”这个标签我的第一反应是排序算法。不是因为它简单恰恰是因为它足够复杂复杂到能牵出内存布局、递归开销、缓存命中、模板抽象、标准库实现等一系列C/C特有的问题。很多人在LeetCode上能轻松写出快排但落到工程里几百万条数据的排序就把程序干崩了也有人把std::sort当成万能药直到某天线上出现诡异崩溃才发现自己对排序的底层一无所知。这篇文章我想借“排序”这个最经典的算法切口把C/C里真正在考、在用的东西说透——包括手写排序的细节、标准库的内幕、什么时候该自己动手以及我在实际项目中踩过的那些坑。无论你是准备面试的在校生还是写业务代码多年的工程师这篇文章都能让你对“用C/C写算法”这件事有一个更立体的认知。1. 排序算法在C/C里的分量它牵出的不止是“排好序”排序在算法题里被归为“基础”但基础不等于简单。C/C的排序难点从来不在“怎么排”的逻辑而在“怎么把逻辑写得又快又稳”。我见过太多人用C写排序时纠结“用std::sort还是手写”这个纠结本身说明他们还没意识到排序考的是什么。C/C排序背后至少有四层东西第一层是纯粹的算法逻辑。快排、堆排、归并、计数排序、基数排序各自的时间复杂度、空间复杂度、稳定性、适用场景。这一层是数据结构教材的内容属于必须要背熟的部分。第二层是内存与缓存模型。同样的快排代码处理数组和链表表现天差地别同样是堆排序为什么实际表现往往不如快排这涉及数组的连续内存访问和CPU缓存行的命中率。C/C程序员如果不懂缓存写出来的算法在纸面上再漂亮跑起来也可能是一塌糊涂。第三层是递归与函数调用开销。递归深度、栈溢出、尾递归优化、函数指针的间接调用——这些都是C/C特有的“算法之外的算法”。用Java写快排递归深了不过是堆内存的事用C写快排一个最坏情况的大数组就能让程序直接崩溃。第四层是泛型与抽象能力。C用模板把排序抽象成sort(begin, end, comp)但泛型不只是简单地把int换成double还要考虑迭代器、比较器、移动语义、异常安全。写一个算法容易写一个像标准库那样能应对各种数据类型的算法才是真正考验C功底的地方。正因为这四层东西互相缠绕排序才成了C/C算法场景里绕不开的试金石。你在刷题时把它过了只是过了第一层在工程里能跑得又快又稳才算真正吃透了所谓“C/C算法”。我自己就对一次面试印象深刻。面试题不复杂让我手写快排。我很快写完面试官追问了一句这个实现最坏情况会栈溢出怎么解决我当时愣住了——所有教材都说快排最坏O(n²)但我从来没想过递归栈也会跟着爆。这个问题直接决定了我后面写排序代码时对“递归深度”三个字的敏感度今天也写进这篇博文希望读者少走这个弯路。2. 手写快速排序为什么同样代码性能可以差出几倍快排应该是大家最熟悉的排序算法平均O(n log n)、原地排序、实际性能优秀。但手写快排时“能用”和“好用”之间隔着一整条优化链。我按递进的顺序把决定性能的几个关键细节拆开讲。2.1 三数取中用最少成本干掉最坏情况最原始的快排选第一个元素当枢轴pivot这在数据已经有序的场景下直接退化成O(n²)。教科书会说“随机选枢轴”但rand()本身有开销而且随机数质量不好的话依然可能退化成最坏情况。工程上最实惠的办法是三数取中median-of-three从lo、mid、hi三个位置取中间值当枢轴。int median3(int a[], int lo, int hi) { int mid lo (hi - lo) / 2; if (a[mid] a[lo]) std::swap(a[mid], a[lo]); if (a[hi] a[lo]) std::swap(a[hi], a[lo]); if (a[hi] a[mid]) std::swap(a[hi], a[mid]); return a[mid]; // a[lo] a[mid] a[hi] }三数取中的好处在于它基本消除了“有序数组导致快排退化”这个最常见的坑而且成本极低三次比较加最多三次交换。即使数据是随机分布它也比固定选边更稳。这里还有一个小细节mid lo (hi - lo) / 2而不是(lo hi) / 2。不是炫技而是当lo hi超过int上限时后者会整数溢出面试官看这个细节就知道你有没有写过大数据量的代码。2.2 单边循环partition写法最不容易错分区partition是快排的核心。网上一搜常见写法有挖坑法、左右指针法、单边循环法。我自己最推荐单边循环法代码短、边界不易错而且在各种教材里出现频率高不容易写出隐藏bug。int partition(int a[], int lo, int hi) { int pivot median3(a, lo, hi); // 为了统一处理把枢轴换到 hi 位置 std::swap(a[mid], a[hi]); int i lo; for (int j lo; j hi; j) { if (a[j] pivot) { std::swap(a[i], a[j]); i; } } std::swap(a[i], a[hi]); return i; }思路很简单拿一个指针i维护“小于枢轴的区间”的末尾然后让j从lo扫到hi - 1遇到比枢轴小的元素就丢到前面去。循环结束后a[i]就是枢轴应该在的位置。这个写法唯一的缺点是交换次数比双指针略多一点但换来的是边界极简、几乎不会写错性价比非常高。如果你追求极致性能可以改成从两端向中间收缩的双指针写法但必须非常小心i和j的边界否则数组越界排查起来相当要命。2.3 阈值16以内改用插入排序快排在数据规模很小时递归调用的开销会压过排序本身的收益。工程上常见的做法是设一个阈值比如16或者25当区间长度小于阈值时改用插入排序。void insertionSort(int a[], int lo, int hi) { for (int i lo 1; i hi; i) { int key a[i]; int j i - 1; while (j lo a[j] key) { a[j 1] a[j]; j--; } a[j 1] key; } } void quickSort(int a[], int lo, int hi) { if (hi - lo 16) { insertionSort(a, lo, hi); return; } int p partition(a, lo, hi); quickSort(a, lo, p - 1); quickSort(a, p 1, hi); }插入排序对于16个元素的数据来说几乎是“顺水推舟”而且它还有额外的好处当整个数组接近有序时插入排序的常数极小。像std::sort也是这么做的只是阈值选得可能更细。这里有一个大多数教材不讲的点——建完堆后最后对整个数组插入排序。这样既能利用内置排序在小规模数据上的高效又能利用堆排序对全局几乎有序数据的友好性。实际上很多工业级实现包括部分std::sort的实现思路会在快排过程中不断递归直到区间足够小然后对整个“近乎有序”的数组做一次统一插入排序。这个操作是安全的因为快排的每次partition都保证了左半部分小于右半部分整体是有序程度的保证。2.4 递归深度控制避免最坏情况栈溢出回到文章开头面试官问我的那个问题。快排最坏情况是每次partition只分出一个元素递归深度达到O(n)。数据量大时递归栈会直接爆掉。怎么解决几个方向第一个方向是“尾递归消除”。快排的两次递归调用其实后一次完全可以改成迭代。因为递归处理完左子区间后右子区间可以通过把lo设为p 1再进入下一轮循环来处理从而把递归深度减半。void quickSort(int a[], int lo, int hi) { while (lo hi) { if (hi - lo 16) { insertionSort(a, lo, hi); break; } int p partition(a, lo, hi); // 递归处理小的一侧循环处理大的一侧 if (p - lo hi - p) { quickSort(a, lo, p - 1); lo p 1; } else { quickSort(a, p 1, hi); hi p - 1; } } }这个写法的妙处在于每次都只递归处理较短的那一侧而把较长的一侧交给下一轮循环递归深度被限制在O(log n)量级栈溢出问题基本消失。第二个方向是直接用std::sort它内部就是introsort——快排为主当递归深度超过2log₂N时自动切换为堆排序从机制上保证最坏O(n log n)。这一点在后面的章节会详细说。2.5 处理大量重复元素三向切分如果数组里有大量重复元素普通快排依然会很慢。因为即使选中了一个“中间值”partition后等于枢轴的元素会分散在两侧下一轮递归依然要处理一堆相等的值。经典解法是“三向切分”3-way partition把数组分成小于、等于、大于三段。这一步在C里还有一个更简洁的实现手段如果只关心结果可以借助std::partition但若追求极致性能手动实现迪杰斯特拉提出的三向快排更稳。我不过度展开代码但想提醒一句很多大厂压轴问“大量重复数据时排序怎么优化”其实就是在等“三向切分”这个答案。3. 堆排序与归并排序稳定性的代价和内存的账要算清快排是“主场选手”但堆排序和归并排序各自有不可替代的价值。我当年分不清什么时候该用哪个吃了不少亏这里把两者的账一起算清楚。3.1 堆排序原地的优势为何被缓存打败堆排序的最大卖点是原地排序、最坏O(n log n)。它不依赖额外的数组这在内存受限的嵌入式场景里相当有吸引力。标准实现分两步建堆、反复取堆顶。void heapify(int a[], int n, int i) { int largest i; int l 2 * i 1; int r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { std::swap(a[i], a[largest]); heapify(a, n, largest); } } void heapSort(int a[], int n) { for (int i n / 2 - 1; i 0; i--) heapify(a, n, i); for (int i n - 1; i 0; i--) { std::swap(a[0], a[i]); heapify(a, i, 0); } }注意堆化的三个细节建堆循环从n / 2 - 1开始。因为n/2到n-1是叶子节点叶子不需要堆化从最后一个非叶子节点开始就能保证每个子树都是堆。排序时heapify(a, i, 0)的第二个参数是剩余堆的规模i不是n。写错的话已经排好的最大元素会被重新拉进堆里排序直接失败。这是我见过程序员写堆排序最常见的bug。堆排序处理数组时访问是跳跃式的2*i、2*i1不像快排那样顺序访问缓存命中率低。所以在现代CPU上堆排序的理论复杂度虽然和快排同阶实际跑起来往往要慢2~4倍。你在性能敏感场景选型时先把这层常数放在心上。3.2 归并排序稳定但需要付内存租金归并排序的核心是分治加合并。它的最大优势是稳定——等于的元素不会因为排序而交换相对位置。这在需要多关键字排序时尤其重要比如先按时间排序、再按优先级排序第二趟排序不能破坏第一趟的相对顺序。经典递归版归并需要额外O(n)的内存void mergeSort(int a[], int tmp[], int lo, int hi) { if (hi - lo 1) return; int mid lo (hi - lo) / 2; mergeSort(a, tmp, lo, mid); mergeSort(a, tmp, mid, hi); int i lo, j mid, k lo; while (i mid j hi) tmp[k] a[i] a[j] ? a[i] : a[j]; while (i mid) tmp[k] a[i]; while (j hi) tmp[k] a[j]; for (i lo; i hi; i) a[i] tmp[i]; }这里有工程上容易被忽略的三点**归并是稳定排序前提是左侧相等元素优先写入。**在合并时如果a[i] a[j]必须先把左侧的a[i]写进临时数组才能保证稳定性。你把写成的瞬间稳定性就没了。**额外内存的账要算。**如果数据量是几十万O(n)的额外数组也就几MB问题不大但如果是几GB的数据归并的那份“租金”就很肉痛了。这时候要么选快排/堆排这种原地算法要么设计外部排序方案——把数据分块排序、再多路合并归并排序的思想在外部排序里才是真正的主场。**自底向上归并可以避免递归栈。**递归版归并的深度是log₂N一般不会爆栈但递归的调用开销仍然存在。自底向上的版本从长度为1的块开始两两合并循环实现不递归代码更稳。3.3 三个排序的选型对照我把核心差异收成一张表方便你按场景直接选排序平均时间最坏时间额外空间稳定性适用场景快速排序O(n log n)O(n²)可优化O(log n)栈不稳定通用首选内存敏感堆排序O(n log n)O(n log n)O(1)不稳定最坏时间有要求的场景归并排序O(n log n)O(n log n)O(n)稳定需要稳定、链表排序选型的逻辑链其实很清晰默认快排或std::sort要求最坏情况可控就上堆排序或introsort要求稳定就上归并数据量特别大且在磁盘上就上外部归并。把这条决策链背熟比死记硬背一堆性质表有用得多。4. 进阶玩法计数排序与基数排序跳出不基于比较的圈子接下来这段写的是“不基于比较”的排序算法。很多人学排序学到归并就停了导致后面遇到“O(n)排序数据”的题毫无头绪——其实计数排序和基数排序在某些约束下可以做到线性复杂度。4.1 计数排序适用范围窄但速度快得吓人计数排序的思路朴素得可爱如果数据都是0到K之间的整数那我先数清每个值出现几次再按顺序把数值回填。void countingSort(int a[], int n, int maxVal) { std::vectorint cnt(maxVal 1, 0); for (int i 0; i n; i) cnt[a[i]]; for (int i 1; i maxVal; i) cnt[i] cnt[i - 1]; std::vectorint out(n); for (int i n - 1; i 0; i--) { out[--cnt[a[i]]] a[i]; } for (int i 0; i n; i) a[i] out[i]; }第一遍循环统计频数第二遍循环把频数数组转成前缀和这样cnt[v]表示“小于等于v的元素有多少个”第三遍循环从后往前遍历把每个元素放到最终位置。第三遍从后往前是为了稳定——等值元素的相对顺序不会被颠倒。计数排序有两个使用前提数据必须是非负整数或者能映射成非负整数数据范围不能太大。如果数据范围是0到2³¹你不可能开一个20亿长度的数组。所以它通常被用在“数据密集且范围有限”的场景比如统计年龄分布、对学生按分数段排序。我在某个项目里处理过千万级带有0~255灰度值的像素数据计数排序跑一次不到100毫秒比快排快了一个数量级。4.2 基数排序把“多关键字”拆成“逐位排序”当数据范围很大、但位数有限的时候基数排序就登场了。它的核心思想是把一个整数看成由多个“位”组成的关键字从最低位到最高位逐位排序LSD每一轮用稳定的计数排序来排当前位。用2进制位做个简单示例假设只排8位以内的非负整数void radixSortLSD(std::vectorint a, int bits) { for (int shift 0; shift bits; shift) { int cnt[2] {0, 0}; std::vectorint out(a.size()); for (int x : a) cnt[(x shift) 1]; cnt[1] cnt[0]; for (int i (int)a.size() - 1; i 0; i--) { int b (a[i] shift) 1; out[--cnt[b]] a[i]; } a.swap(out); } }这里每一轮按当前位分成两类用稳定的计数排序保证上一轮排好的位序不会被破坏。8位要跑8轮每轮O(n)总时间O(wn)w是位数。当w远小于log₂n时基数排序可能比基于比较的排序更快尤其是在数据量巨大且位数固定的场景——比如对20位长度的身份证号排序或者对日期字符串排序。不过基数排序的常数比快排大。位数太多、数据量又不大时它反而可能不如一次快排。选型建议是n再10万以上、数据位数确定且不大值得试基数排序否则别折腾std::sort已经够强了。4.3 从“非比较排序”带出的算法思维计数和基数排序看起来只是“奇技淫巧”但它们背后其实有更通用的思想——用空间换时间、利用数据本身的约束。这种思维在更高级的算法里反复出现布隆过滤器用有限空间近似判断元素是否存在位图用比特位压缩数据哈希表用预计算的散列值换O(1)查询。学会了在“数据有特殊结构”时跳出比较排序的框架你写代码时会多一层选择——很多时候最快的算法不是更聪明的算法而是更好地利用了数据特征的算法。我在实际编码里也验证过这件事。处理一批固定长度字符串排序时我用基数排序从底层开始按字节排性能比std::sort快一大截。原因很简单字符串比较函数的代价比整数比较高而基数排序直接把每次比较拆成了逐字节的稳定桶操作把比较的“大开销”拆成了“小开销”自然快了。5. 工程视角std::sort为什么稳定可靠什么时候你该自己写聊了这么多手写算法回到一个躲不掉的问题C工程里到底该不该自己写排序我的答案是分情况但大多数时候直接用std::sort绝不会错。5.1 标准库排序的内部策略introsort如何驯服快排std::sort在大多数实现里用的是introsort它是快排的“加强版”以快排为主但在递归深度超过某阈值时切换为堆排序避免最坏情况退化同时在小数据段上使用插入排序。这样它同时获得了快排的常数小、堆排序的最坏时间有保障、插入排序在小规模时的高效三种优势集于一身。std::sort为什么不容易写崩因为它的迭代器抽象和比较器约束把一堆容易踩的坑都帮你拦住了。但用它有个前提比较器必须满足“严格弱序”strict weak ordering。也就是说对于任意两个元素a和bcomp(a, a)必须为false若comp(a, b)为true则comp(b, a)必须为false若comp(a, b)为true且comp(b, c)为true则comp(a, c)必须为true这个约束最大的坑是“相等元素的比较不能返回true”。很多人写比较器时图省事写了一个return a.m_value b.m_value;结果在某次std::sort里直接崩溃或者产生不可预期的顺序。原因就是当a b时comp(a, b)和comp(b, a)都是true违反了严格弱序排序算法内部的很多假设直接失效。正确的写法永远是return a.m_value b.m_value;脑子里把这个规矩刻死。5.2std::stable_sort和std::partial_sort该用就用力std::stable_sort是稳定版本的排序底层通常是归并排序需要额外空间。std::partial_sort用来取前K小或前K大的元素底层是堆排序你只要传递begin到begin K作为排序范围性能比全量排序后截取高得多。求“Top K”时不要自己写堆直接std::partial_sort(v.begin(), v.begin() k, v.end(), std::greaterint());如果你要的“Top K”不需要保证内部有序可以用std::nth_element它只保证第n个位置的元素是全局排好序后应该在那里的元素左侧都小于等于它右侧都大于等于它复杂度平均O(n)。这比排序再截取快得多但要注意它不保证左侧或右侧内部有序。5.3 什么时候应该手写排序标准库不是万能的下面几种情况你必须考虑自己动手需要特殊的数据结构支持。std::sort要求随机访问迭代器链表排不了。链表排序可以用std::list::sort它内部是归并更底层的场景你只能手写链表的归并排序注意用dummy节点避免边界判断。**内存极度受限。**嵌入式环境或者某段内存直接malloc失败时std::stable_sort那种额外O(n)内存就没法接受。这时哪怕性能差一点也要选原地排序算法。**数据形态特殊。**数据是0~255的字节、固定长度字符串、或者一堆RGB像素值用计数/基数排序能跑出比通用std::sort高一个量级的性能。我在做图像处理的工具时遇到过这种情况自己写基于字节的基数排序把一批样本的排序耗时从秒级压到百毫秒级。**数据规模巨大、要外部排序。**内存装不下时就只能走“分块排序多路归并”的路线。这里的“排序算法”已经不只是算法本身而是写入策略、缓冲区管理、IO调优等多个工程问题。6. 我总结的几条排错经验和一道经典练习这段是纯经验分享。C/C排序相关的bug大多数不是算法逻辑错了而是低级的边界、内存、比较器问题这里把我印象最深几条罗列出来**整数溢出问题。**计算中点用lo (hi - lo) / 2不要用(lo hi) / 2。不只是排序里有这个问题二分查找、线段树、分治算法里全有。这个习惯越早养成越好。**插入排序的循环边界。**手写插入排序时while (j lo a[j] key)里的j lo容易丢。丢掉之后j减到-1还继续访问a[-1]经典越界。**比较器违反严格弱序。**前面说过不能当比较器。还有种隐蔽写法是函数里用了全局状态或者浮点NaN也会让排序行为完全不可预测。**归并的临时数组大小。**只开(hi - lo)大小却在写tmp[k]时按全局索引越界。临时数组每次只用区间大小开全局的反而容易在分治过程中越界建议要么开全局n大小并用分区索引要么分段开别混用。**std::sort不保证稳定。**有些人在业务里依赖std::sort的稳定性数据一换平台就出bug。要稳定就用std::stable_sort不要赌编译器实现。这些坑几乎都是真实生产环境里出现过的有的甚至是线上事故级别的。C/C的算法题和工程实践最大的差距就在这种细节里。最后给一道我经常用来检验自己、也推荐给别人练习的题目纯算法题不涉及具体业务题目实现一个函数对单向链表进行O(n log n)时间、O(1)额外空间的排序。思路提示链表没有随机访问快排退化成O(n²)普通归并需要额外数组但链表归并可以直接改next指针不需要额外存储。核心是三步——用快慢指针找中点、递归排序两段、按节点合并。这题把分治思想、链表操作、内存意识全考了一遍比单纯写数组快排能学到的多得多。我每年都会拿这道题给自己的代码热身写一遍就能发现最近手生没生。C/C算法的乐趣就在这里同样的逻辑不同的实现性能能差一个数量级同样的算法不同的人写bug率也差一个数量级。排序只是一个起点沿着“为什么快排快”“为什么堆排要这样堆化”“为什么标准库这么设计”这些问题追下去你对C和C的理解会跟着一起加深。希望这篇从排序展开的梳理能帮你少踩几个我踩过的坑。