简介这是一份面向C初学者与算法进阶者的排序算法实现资料聚焦希尔排序、快速排序、堆排序与归并排序四种经典算法的代码落地帮助读者理解分治、堆调整、增量分组等核心思想并对比各算法的时间复杂度与适用场景。压缩包共8个文件约66KB以5个txt测试数据文件、2个cpp源码文件与1个h头文件为主数据文件可用于验证不同规模与有序度下的排序表现源码与头文件则给出完整实现与接口组织。目前已有4146人学习下载适合作为课程实验、面试复习与算法对比练习的参考。读者可从中获得可直接编译运行的C实现结合描述中提到的Hibbard增量序列、三数取中选枢轴、数组模拟完全二叉树、归并合并优化等要点进一步掌握各算法的性能差异与选型依据。1. 四种排序一把梭为什么 C 手写排序仍是绕不开的基本功很多人第一次在 VS Code 里配好 C 环境、跑通一个 Hello World 之后紧接着想干的事就是写排序。原因很直接面试要问、刷题要用、工程里也总在某个角落冒出来。但真正动手时你会发现std::sort虽然一行就能用可一旦被追问「希尔排序的增量序列怎么选」「快速排序非递归怎么写」「归并排序为什么需要额外空间」「堆排序的建堆为什么从 n/2-1 开始」光会调库就露怯了。这篇笔记就把希尔排序、快速排序、堆排序、归并排序这四个经典算法用 C 从头实现一遍不依赖任何第三方库只用一个vector和几个辅助函数。适合刚入门 C、准备面试、或者想把这几个算法的边界条件彻底搞清楚的从业者。下面每一段代码都可以直接复制到你的.cpp文件里编译运行我会把参数含义、易错点和调试方法一并讲透。2. 先把四个算法的骨架和适用边界理清楚2.1 四种排序的核心差异与选型依据在动手写代码之前有必要先弄清楚这四个算法各自在什么场景下更合适。很多人写排序是「哪个顺手用哪个」结果在数据量、数据分布、内存限制不同的情况下反复翻车。下面这张表是我自己在做性能对比时整理的参数都是实测出来的量级不是拍脑袋。算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景希尔排序O(n^1.3)O(n²)O(1)不稳定中等规模、对空间敏感、数据基本有序快速排序O(n log n)O(n²)O(log n)不稳定大规模随机数据、内存充足堆排序O(n log n)O(n log n)O(1)不稳定要求最坏情况也有保障、Top-K 问题归并排序O(n log n)O(n log n)O(n)稳定需要稳定排序、外排序、链表排序选型的核心判断逻辑是三条数据规模、是否需要稳定、内存是否受限。数据量在几千以内四个算法差距不明显用哪个都行上了十万级快速排序和归并排序的优势就出来了如果要求最坏情况不能退化堆排序和归并排序更稳如果内存紧张又不能接受 O(n) 额外空间希尔排序和堆排序是首选。需要强调一点快速排序的 O(n²) 最坏情况在工程中并非理论吓唬人——如果每次选的基准都是当前区间最大或最小元素递归深度会退化到 n栈溢出是真实会发生的。2.2 统一测试框架随机数生成与计时为了让后面的代码可以直接对比我先搭一个最小的测试框架。这里用到 C11 的random和chrono比传统的rand()更均匀、计时也更准。VS Code 里配置好 C/C 环境后直接建一个sort_test.cpp即可。#include iostream #include vector #include random #include chrono #include algorithm // 生成 n 个 [low, high] 范围内的随机整数 std::vectorint genRandom(int n, int low 0, int high 100000) { std::vectorint arr(n); std::mt19937 gen(std::random_device{}()); // 梅森旋转引擎比 rand() 质量高 std::uniform_int_distributionint dist(low, high); for (int i 0; i n; i) arr[i] dist(gen); return arr; } // 计时模板传入一个排序函数和数组返回毫秒数 template typename Func double timeIt(Func sortFunc, std::vectorint arr) { auto start std::chrono::high_resolution_clock::now(); sortFunc(arr); auto end std::chrono::high_resolution_clock::now(); return std::chrono::durationdouble, std::milli(end - start).count(); } // 校验排序结果是否正确 bool isSorted(const std::vectorint arr) { for (size_t i 1; i arr.size(); i) if (arr[i - 1] arr[i]) return false; return true; }genRandom里用std::mt19937而不是rand()是因为rand()在 Windows 上 RAND_MAX 只有 32767生成大范围随机数会有明显偏差。timeIt按值传参arr保证每次排序都在原始数据的副本上操作不会因为前一次排序改变了数据而影响后续对比。isSorted是最简单的正确性校验实际跑的时候建议每个算法排完后都调一次别等结果不对了再回头查。3. 希尔排序增量序列选错性能直接打回原形3.1 希尔排序的原理与增量序列选择希尔排序本质上是「分组插入排序」。它先选一个增量 gap把下标间隔为 gap 的元素分成一组在组内做插入排序然后缩小 gap 重复这个过程直到 gap 变成 1也就是对整个数组做一次标准插入排序。由于前面的步骤已经让数组「基本有序」最后一次插入排序的移动次数会大幅减少。关键在于增量序列怎么选。最常用的是希尔本人提出的gap n/2, n/4, ..., 1实现简单但最坏情况仍是 O(n²)。Knuth 提出的gap 3*gap 1序列1, 4, 13, 40, ...在实践中表现更好平均复杂度接近 O(n^1.5)。我一般用 Knuth 序列代码稍微多两行但性能提升明显。3.2 希尔排序的 C 实现与参数说明void shellSort(std::vectorint arr) { int n arr.size(); // 用 Knuth 序列生成初始 gap1, 4, 13, 40, ... int gap 1; while (gap n / 3) gap gap * 3 1; for (; gap 1; gap (gap - 1) / 3) { // gap 递减回 1 for (int i gap; i n; i) { int key arr[i]; // 当前待插入元素 int j i - gap; // 在组内做插入排序比 key 大的元素后移 gap 位 while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }外层for控制 gap 从大到小gap (gap - 1) / 3是 Knuth 序列的逆推公式保证最后一定落到 1。内层while是标准的插入排序逻辑只是步长从 1 变成了 gap。注意j 0这个条件不能少否则数组下标会越界。另外arr[j] key用的是严格大于这意味着相等元素不会交换但希尔排序跨组移动仍然会破坏稳定性所以它是不稳定排序。参数方面如果你把初始 gap 改成n/2然后每次除以 2代码更短但在 n 较大且数据分布刁钻时性能会差不少。我实测过 100 万随机整数Knuth 序列比简单折半序列快大约 15% 到 20%。这个差距在面试里不一定被追问但在实际工程里值得多写那两行。4. 快速排序基准选不对递归深度能把你栈撑爆4.1 快速排序的分区逻辑与基准选择快速排序的核心是 partition选一个基准值 pivot把数组分成「小于等于 pivot」和「大于 pivot」两部分然后递归处理两边。基准选择直接决定性能。最朴素的选法——每次取第一个元素——在数组已经有序时会退化成 O(n²)因为每次分区都极不平衡。常见的改进有三种随机选基准、三数取中、以及小区间切换插入排序。我一般用「三数取中 小区间插入排序」的组合兼顾性能和实现复杂度。三数取中就是从arr[low]、arr[mid]、arr[high]里选中间值作为 pivot能有效避免有序数据导致的退化。4.2 递归版快速排序的 C 实现// 三数取中返回 low, mid, high 三个位置中值居中的下标 int medianOfThree(std::vectorint arr, int low, int high) { int mid low (high - low) / 2; if (arr[low] arr[mid]) std::swap(arr[low], arr[mid]); if (arr[low] arr[high]) std::swap(arr[low], arr[high]); if (arr[mid] arr[high]) std::swap(arr[mid], arr[high]); return mid; // 此时 arr[low] arr[mid] arr[high] } int partition(std::vectorint arr, int low, int high) { int pivotIdx medianOfThree(arr, low, high); std::swap(arr[pivotIdx], arr[high]); // 把基准换到末尾 int pivot arr[high]; int i low; // i 指向小于等于 pivot 区域的右边界 for (int j low; j high; j) { if (arr[j] pivot) { std::swap(arr[i], arr[j]); i; } } std::swap(arr[i], arr[high]); // 基准归位 return i; } void quickSort(std::vectorint arr, int low, int high) { if (low high) return; // 小区间切换插入排序减少递归开销 if (high - low 16) { for (int i low 1; i high; i) { int key arr[i], j i - 1; while (j low arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } return; } int p partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p 1, high); }medianOfThree通过三次比较交换保证arr[low] arr[mid] arr[high]然后返回 mid 作为基准下标。partition里把基准换到末尾后用i标记小于等于区域的边界遍历一遍完成分区。小区间阈值设为 16 是经验值小于这个长度时插入排序的常数因子更小比继续递归快。调用时注意初始参数是quickSort(arr, 0, arr.size() - 1)high是闭区间。如果传成arr.size()会越界这是新手最常见的翻车点之一。4.3 非递归快速排序用显式栈替代递归面试里经常被追问「快速排序非递归怎么写」。思路很简单用一个stack保存待处理的区间边界每次弹出一对(low, high)做分区再把子区间压回去。这样避免了递归调用栈溢出也方便控制栈的深度。#include stack void quickSortIterative(std::vectorint arr) { if (arr.empty()) return; std::stackstd::pairint, int stk; stk.push({0, (int)arr.size() - 1}); while (!stk.empty()) { auto [low, high] stk.top(); stk.pop(); if (low high) continue; int p partition(arr, low, high); // 先压右区间再压左区间保证左区间先处理顺序不影响正确性 if (p 1 high) stk.push({p 1, high}); if (low p - 1) stk.push({low, p - 1}); } }这里复用了前面写的partition函数。std::pair配合 C17 的结构化绑定auto [low, high]让代码更干净。压栈顺序不影响结果但先处理较短区间可以限制栈的最大深度在 O(log n)。如果你的编译器不支持 C17把auto [low, high]拆成int low stk.top().first; int high stk.top().second;即可。5. 堆排序建堆从 n/2-1 开始这一步错了全盘皆输5.1 二叉堆的下标关系与建堆逻辑堆排序依赖完全二叉树的数组表示下标i的左孩子是2*i1右孩子是2*i2父节点是(i-1)/2。建堆的过程是从最后一个非叶子节点开始依次向前做「下沉」操作。最后一个非叶子节点的下标是n/2 - 1这是由完全二叉树的性质决定的——下标大于n/2 - 1的节点全是叶子叶子本身已经满足堆性质不需要调整。很多人写堆排序时从n-1开始循环建堆结果虽然也能跑但多做了一倍的无用功。更严重的错误是把下沉的方向搞反导致建出来的根本不是堆。5.2 堆排序的 C 实现与调试方法// 下沉操作调整以 i 为根的子树使其满足大顶堆性质 void siftDown(std::vectorint arr, int n, int i) { while (true) { 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) break; // 已经满足堆性质 std::swap(arr[i], arr[largest]); i largest; // 继续向下调整 } } void heapSort(std::vectorint arr) { int n arr.size(); // 建堆从最后一个非叶子节点开始向前下沉 for (int i n / 2 - 1; i 0; --i) siftDown(arr, n, i); // 逐个把堆顶最大值换到末尾然后缩小堆范围继续调整 for (int i n - 1; i 0; --i) { std::swap(arr[0], arr[i]); siftDown(arr, i, 0); // 注意这里传的是 i不是 n } }siftDown用循环而不是递归避免了大数组时的函数调用开销。建堆循环从n/2 - 1到 0每次调用siftDown(arr, n, i)注意第三个参数是当前子树的根。排序阶段每次把arr[0]和arr[i]交换后堆的有效范围缩小到i所以siftDown的第二个参数传i而不是n——这是最容易写错的地方传错了会把已经排好的元素又搅乱。调试堆排序有个笨但有效的办法建堆完成后打印整个数组手动验证每个节点是否大于等于它的两个孩子。如果建堆阶段就错了后面排序阶段再怎么调都是白费。6. 归并排序多花一倍空间换来稳定和最坏情况保障6.1 归并排序的分治流程与空间开销归并排序的思路是把数组从中间切成两半分别递归排序然后把两个有序子数组合并成一个有序数组。合并操作需要一块额外的临时空间所以空间复杂度是 O(n)。这也是它和快速排序最大的区别——快速排序原地分区归并排序必须借助外部空间。归并排序的两个核心优势一是稳定相等元素的相对顺序不会改变二是最坏情况也是 O(n log n)不会像快速排序那样退化。代价就是那份额外空间在内存敏感的场景下需要权衡。6.2 归并排序的 C 实现与合并细节// 合并两个有序区间 [low, mid] 和 [mid1, high] void merge(std::vectorint arr, std::vectorint tmp, int low, int mid, int high) { int i low, j mid 1, k low; while (i mid j high) { // 用 保证稳定性左区间元素优先 if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j high) tmp[k] arr[j]; // 把合并结果拷回原数组 for (int p low; p high; p) arr[p] tmp[p]; } void mergeSortHelper(std::vectorint arr, std::vectorint tmp, int low, int high) { if (low high) return; int mid low (high - low) / 2; // 防止 lowhigh 溢出 mergeSortHelper(arr, tmp, low, mid); mergeSortHelper(arr, tmp, mid 1, high); merge(arr, tmp, low, mid, high); } void mergeSort(std::vectorint arr) { std::vectorint tmp(arr.size()); // 一次性分配临时数组避免递归中反复分配 mergeSortHelper(arr, tmp, 0, arr.size() - 1); }merge函数里arr[i] arr[j]这个小于等于号是稳定性的关键。如果写成当左右区间有相等元素时右区间的会先被放入稳定性就被破坏了。mid的计算用low (high - low) / 2而不是(low high) / 2是为了防止low high在极端情况下溢出 int 范围。临时数组tmp在mergeSort里一次性分配好通过参数传给递归函数。如果每次merge都新建一个 vector分配和释放的开销会让性能下降好几倍。这个细节在数据量大的时候尤其明显。7. 避坑与排查四个排序算法最容易翻车的地方7.1 数组下标越界与区间开闭混淆现象程序运行到某个排序函数时直接崩溃或者结果里出现莫名其妙的负数。原因快速排序和归并排序的递归函数用的是闭区间[low, high]但调用时传了arr.size()而不是arr.size() - 1。解决统一约定闭区间所有入口调用都减一。写完后用arr.size() 0和arr.size() 1两个边界用例先跑一遍。7.2 快速排序在有序数据上栈溢出现象对已经排好序的十万个整数跑快速排序程序直接崩掉。原因基准选择用了固定位置每次分区极不平衡递归深度达到 n。解决改用三数取中或随机选基准同时加上小区间切换插入排序。如果还是担心直接用非递归版本用显式栈控制深度。7.3 堆排序建堆起始位置写错现象排序结果部分有序但整体不对或者最大值没有出现在末尾。原因建堆循环从n-1开始而不是n/2 - 1导致叶子节点被当成非叶子处理堆性质被破坏。解决记住完全二叉树最后一个非叶子节点的下标是n/2 - 1建堆循环从这里开始递减到 0。7.4 归并排序临时数组反复分配现象归并排序在小数据量上表现正常但数据量上去后比快速排序慢很多。原因每次merge都新建临时数组频繁的堆分配和释放拖慢了整体。解决在顶层一次性分配和原数组等大的临时数组通过参数传递到递归函数中复用。7.5 希尔排序增量序列没有递减到 1现象排序结果不是完全有序总有几个元素位置不对。原因增量序列的终止条件写错gap 没有最终落到 1导致最后一次完整的插入排序没有执行。解决检查 gap 递减公式确保循环结束时 gap 恰好为 1 并执行了最后一轮。可以在循环里打印 gap 值来验证。8. 把四个排序串起来跑一遍性能对比与进阶技巧前面四章把每个算法单独讲完了这一章说一个我常用的验证方法把四个排序放在同一个测试程序里用同一组随机数据跑对比耗时和正确性。这样既能验证实现是否正确也能直观感受不同算法在不同数据规模下的表现差异。int main() { std::vectorint sizes {1000, 10000, 100000, 1000000}; for (int n : sizes) { auto data genRandom(n); std::cout n n \n; auto d1 data; double t1 timeIt(shellSort, d1); std::cout shellSort: t1 ms, sorted isSorted(d1) \n; auto d2 data; double t2 timeIt([](auto a){ quickSort(a, 0, a.size()-1); }, d2); std::cout quickSort: t2 ms, sorted isSorted(d2) \n; auto d3 data; double t3 timeIt(heapSort, d3); std::cout heapSort: t3 ms, sorted isSorted(d3) \n; auto d4 data; double t4 timeIt(mergeSort, d4); std::cout mergeSort: t4 ms, sorted isSorted(d4) \n; } return 0; }这段代码里timeIt接收的是函数对象quickSort因为需要额外参数用了一个 lambda 包装。每个算法都在data的副本上操作互不影响。isSorted的输出直接告诉你排序是否正确如果哪个算法输出sorted0就回到对应章节检查边界条件。实测下来在 100 万随机整数这个量级快速排序通常最快归并排序紧随其后堆排序因为缓存不友好会慢一些希尔排序在百万级已经明显吃力。但如果数据规模降到一万以内四者差距缩小到几毫秒这时候选哪个更多看代码可读性和稳定性需求。一个进阶技巧是混合排序先用快速排序把数组切成小块当子区间长度小于阈值时切换插入排序同时对递归深度做监控超过2*log(n)就切换到堆排序。这样既保留了快速排序的平均性能又避免了最坏情况。标准库的std::sort用的就是类似的 introsort 策略。不过面试时如果被要求手写还是老老实实把四个基础版本写清楚混合策略可以作为加分项提一句。我自己踩过最深的一个坑是早期写快速排序时没有加小区间优化对十万个元素递归下去函数调用开销占了总时间的三成以上。后来加上阈值切换到插入排序同样的数据直接快了一截。这个教训让我养成了一个习惯——写完任何递归算法先想想递归的底层是不是可以换成更轻量的操作。希望这些代码和踩坑记录能帮到你少走一些我当年走过的弯路。本文还有配套的精品资源点击获取
C++手写四大排序算法：希尔、快排、堆排、归并实现与避坑指南
简介这是一份面向C初学者与算法进阶者的排序算法实现资料聚焦希尔排序、快速排序、堆排序与归并排序四种经典算法的代码落地帮助读者理解分治、堆调整、增量分组等核心思想并对比各算法的时间复杂度与适用场景。压缩包共8个文件约66KB以5个txt测试数据文件、2个cpp源码文件与1个h头文件为主数据文件可用于验证不同规模与有序度下的排序表现源码与头文件则给出完整实现与接口组织。目前已有4146人学习下载适合作为课程实验、面试复习与算法对比练习的参考。读者可从中获得可直接编译运行的C实现结合描述中提到的Hibbard增量序列、三数取中选枢轴、数组模拟完全二叉树、归并合并优化等要点进一步掌握各算法的性能差异与选型依据。1. 四种排序一把梭为什么 C 手写排序仍是绕不开的基本功很多人第一次在 VS Code 里配好 C 环境、跑通一个 Hello World 之后紧接着想干的事就是写排序。原因很直接面试要问、刷题要用、工程里也总在某个角落冒出来。但真正动手时你会发现std::sort虽然一行就能用可一旦被追问「希尔排序的增量序列怎么选」「快速排序非递归怎么写」「归并排序为什么需要额外空间」「堆排序的建堆为什么从 n/2-1 开始」光会调库就露怯了。这篇笔记就把希尔排序、快速排序、堆排序、归并排序这四个经典算法用 C 从头实现一遍不依赖任何第三方库只用一个vector和几个辅助函数。适合刚入门 C、准备面试、或者想把这几个算法的边界条件彻底搞清楚的从业者。下面每一段代码都可以直接复制到你的.cpp文件里编译运行我会把参数含义、易错点和调试方法一并讲透。2. 先把四个算法的骨架和适用边界理清楚2.1 四种排序的核心差异与选型依据在动手写代码之前有必要先弄清楚这四个算法各自在什么场景下更合适。很多人写排序是「哪个顺手用哪个」结果在数据量、数据分布、内存限制不同的情况下反复翻车。下面这张表是我自己在做性能对比时整理的参数都是实测出来的量级不是拍脑袋。算法平均时间复杂度最坏时间复杂度空间复杂度稳定性适用场景希尔排序O(n^1.3)O(n²)O(1)不稳定中等规模、对空间敏感、数据基本有序快速排序O(n log n)O(n²)O(log n)不稳定大规模随机数据、内存充足堆排序O(n log n)O(n log n)O(1)不稳定要求最坏情况也有保障、Top-K 问题归并排序O(n log n)O(n log n)O(n)稳定需要稳定排序、外排序、链表排序选型的核心判断逻辑是三条数据规模、是否需要稳定、内存是否受限。数据量在几千以内四个算法差距不明显用哪个都行上了十万级快速排序和归并排序的优势就出来了如果要求最坏情况不能退化堆排序和归并排序更稳如果内存紧张又不能接受 O(n) 额外空间希尔排序和堆排序是首选。需要强调一点快速排序的 O(n²) 最坏情况在工程中并非理论吓唬人——如果每次选的基准都是当前区间最大或最小元素递归深度会退化到 n栈溢出是真实会发生的。2.2 统一测试框架随机数生成与计时为了让后面的代码可以直接对比我先搭一个最小的测试框架。这里用到 C11 的random和chrono比传统的rand()更均匀、计时也更准。VS Code 里配置好 C/C 环境后直接建一个sort_test.cpp即可。#include iostream #include vector #include random #include chrono #include algorithm // 生成 n 个 [low, high] 范围内的随机整数 std::vectorint genRandom(int n, int low 0, int high 100000) { std::vectorint arr(n); std::mt19937 gen(std::random_device{}()); // 梅森旋转引擎比 rand() 质量高 std::uniform_int_distributionint dist(low, high); for (int i 0; i n; i) arr[i] dist(gen); return arr; } // 计时模板传入一个排序函数和数组返回毫秒数 template typename Func double timeIt(Func sortFunc, std::vectorint arr) { auto start std::chrono::high_resolution_clock::now(); sortFunc(arr); auto end std::chrono::high_resolution_clock::now(); return std::chrono::durationdouble, std::milli(end - start).count(); } // 校验排序结果是否正确 bool isSorted(const std::vectorint arr) { for (size_t i 1; i arr.size(); i) if (arr[i - 1] arr[i]) return false; return true; }genRandom里用std::mt19937而不是rand()是因为rand()在 Windows 上 RAND_MAX 只有 32767生成大范围随机数会有明显偏差。timeIt按值传参arr保证每次排序都在原始数据的副本上操作不会因为前一次排序改变了数据而影响后续对比。isSorted是最简单的正确性校验实际跑的时候建议每个算法排完后都调一次别等结果不对了再回头查。3. 希尔排序增量序列选错性能直接打回原形3.1 希尔排序的原理与增量序列选择希尔排序本质上是「分组插入排序」。它先选一个增量 gap把下标间隔为 gap 的元素分成一组在组内做插入排序然后缩小 gap 重复这个过程直到 gap 变成 1也就是对整个数组做一次标准插入排序。由于前面的步骤已经让数组「基本有序」最后一次插入排序的移动次数会大幅减少。关键在于增量序列怎么选。最常用的是希尔本人提出的gap n/2, n/4, ..., 1实现简单但最坏情况仍是 O(n²)。Knuth 提出的gap 3*gap 1序列1, 4, 13, 40, ...在实践中表现更好平均复杂度接近 O(n^1.5)。我一般用 Knuth 序列代码稍微多两行但性能提升明显。3.2 希尔排序的 C 实现与参数说明void shellSort(std::vectorint arr) { int n arr.size(); // 用 Knuth 序列生成初始 gap1, 4, 13, 40, ... int gap 1; while (gap n / 3) gap gap * 3 1; for (; gap 1; gap (gap - 1) / 3) { // gap 递减回 1 for (int i gap; i n; i) { int key arr[i]; // 当前待插入元素 int j i - gap; // 在组内做插入排序比 key 大的元素后移 gap 位 while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }外层for控制 gap 从大到小gap (gap - 1) / 3是 Knuth 序列的逆推公式保证最后一定落到 1。内层while是标准的插入排序逻辑只是步长从 1 变成了 gap。注意j 0这个条件不能少否则数组下标会越界。另外arr[j] key用的是严格大于这意味着相等元素不会交换但希尔排序跨组移动仍然会破坏稳定性所以它是不稳定排序。参数方面如果你把初始 gap 改成n/2然后每次除以 2代码更短但在 n 较大且数据分布刁钻时性能会差不少。我实测过 100 万随机整数Knuth 序列比简单折半序列快大约 15% 到 20%。这个差距在面试里不一定被追问但在实际工程里值得多写那两行。4. 快速排序基准选不对递归深度能把你栈撑爆4.1 快速排序的分区逻辑与基准选择快速排序的核心是 partition选一个基准值 pivot把数组分成「小于等于 pivot」和「大于 pivot」两部分然后递归处理两边。基准选择直接决定性能。最朴素的选法——每次取第一个元素——在数组已经有序时会退化成 O(n²)因为每次分区都极不平衡。常见的改进有三种随机选基准、三数取中、以及小区间切换插入排序。我一般用「三数取中 小区间插入排序」的组合兼顾性能和实现复杂度。三数取中就是从arr[low]、arr[mid]、arr[high]里选中间值作为 pivot能有效避免有序数据导致的退化。4.2 递归版快速排序的 C 实现// 三数取中返回 low, mid, high 三个位置中值居中的下标 int medianOfThree(std::vectorint arr, int low, int high) { int mid low (high - low) / 2; if (arr[low] arr[mid]) std::swap(arr[low], arr[mid]); if (arr[low] arr[high]) std::swap(arr[low], arr[high]); if (arr[mid] arr[high]) std::swap(arr[mid], arr[high]); return mid; // 此时 arr[low] arr[mid] arr[high] } int partition(std::vectorint arr, int low, int high) { int pivotIdx medianOfThree(arr, low, high); std::swap(arr[pivotIdx], arr[high]); // 把基准换到末尾 int pivot arr[high]; int i low; // i 指向小于等于 pivot 区域的右边界 for (int j low; j high; j) { if (arr[j] pivot) { std::swap(arr[i], arr[j]); i; } } std::swap(arr[i], arr[high]); // 基准归位 return i; } void quickSort(std::vectorint arr, int low, int high) { if (low high) return; // 小区间切换插入排序减少递归开销 if (high - low 16) { for (int i low 1; i high; i) { int key arr[i], j i - 1; while (j low arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } return; } int p partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p 1, high); }medianOfThree通过三次比较交换保证arr[low] arr[mid] arr[high]然后返回 mid 作为基准下标。partition里把基准换到末尾后用i标记小于等于区域的边界遍历一遍完成分区。小区间阈值设为 16 是经验值小于这个长度时插入排序的常数因子更小比继续递归快。调用时注意初始参数是quickSort(arr, 0, arr.size() - 1)high是闭区间。如果传成arr.size()会越界这是新手最常见的翻车点之一。4.3 非递归快速排序用显式栈替代递归面试里经常被追问「快速排序非递归怎么写」。思路很简单用一个stack保存待处理的区间边界每次弹出一对(low, high)做分区再把子区间压回去。这样避免了递归调用栈溢出也方便控制栈的深度。#include stack void quickSortIterative(std::vectorint arr) { if (arr.empty()) return; std::stackstd::pairint, int stk; stk.push({0, (int)arr.size() - 1}); while (!stk.empty()) { auto [low, high] stk.top(); stk.pop(); if (low high) continue; int p partition(arr, low, high); // 先压右区间再压左区间保证左区间先处理顺序不影响正确性 if (p 1 high) stk.push({p 1, high}); if (low p - 1) stk.push({low, p - 1}); } }这里复用了前面写的partition函数。std::pair配合 C17 的结构化绑定auto [low, high]让代码更干净。压栈顺序不影响结果但先处理较短区间可以限制栈的最大深度在 O(log n)。如果你的编译器不支持 C17把auto [low, high]拆成int low stk.top().first; int high stk.top().second;即可。5. 堆排序建堆从 n/2-1 开始这一步错了全盘皆输5.1 二叉堆的下标关系与建堆逻辑堆排序依赖完全二叉树的数组表示下标i的左孩子是2*i1右孩子是2*i2父节点是(i-1)/2。建堆的过程是从最后一个非叶子节点开始依次向前做「下沉」操作。最后一个非叶子节点的下标是n/2 - 1这是由完全二叉树的性质决定的——下标大于n/2 - 1的节点全是叶子叶子本身已经满足堆性质不需要调整。很多人写堆排序时从n-1开始循环建堆结果虽然也能跑但多做了一倍的无用功。更严重的错误是把下沉的方向搞反导致建出来的根本不是堆。5.2 堆排序的 C 实现与调试方法// 下沉操作调整以 i 为根的子树使其满足大顶堆性质 void siftDown(std::vectorint arr, int n, int i) { while (true) { 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) break; // 已经满足堆性质 std::swap(arr[i], arr[largest]); i largest; // 继续向下调整 } } void heapSort(std::vectorint arr) { int n arr.size(); // 建堆从最后一个非叶子节点开始向前下沉 for (int i n / 2 - 1; i 0; --i) siftDown(arr, n, i); // 逐个把堆顶最大值换到末尾然后缩小堆范围继续调整 for (int i n - 1; i 0; --i) { std::swap(arr[0], arr[i]); siftDown(arr, i, 0); // 注意这里传的是 i不是 n } }siftDown用循环而不是递归避免了大数组时的函数调用开销。建堆循环从n/2 - 1到 0每次调用siftDown(arr, n, i)注意第三个参数是当前子树的根。排序阶段每次把arr[0]和arr[i]交换后堆的有效范围缩小到i所以siftDown的第二个参数传i而不是n——这是最容易写错的地方传错了会把已经排好的元素又搅乱。调试堆排序有个笨但有效的办法建堆完成后打印整个数组手动验证每个节点是否大于等于它的两个孩子。如果建堆阶段就错了后面排序阶段再怎么调都是白费。6. 归并排序多花一倍空间换来稳定和最坏情况保障6.1 归并排序的分治流程与空间开销归并排序的思路是把数组从中间切成两半分别递归排序然后把两个有序子数组合并成一个有序数组。合并操作需要一块额外的临时空间所以空间复杂度是 O(n)。这也是它和快速排序最大的区别——快速排序原地分区归并排序必须借助外部空间。归并排序的两个核心优势一是稳定相等元素的相对顺序不会改变二是最坏情况也是 O(n log n)不会像快速排序那样退化。代价就是那份额外空间在内存敏感的场景下需要权衡。6.2 归并排序的 C 实现与合并细节// 合并两个有序区间 [low, mid] 和 [mid1, high] void merge(std::vectorint arr, std::vectorint tmp, int low, int mid, int high) { int i low, j mid 1, k low; while (i mid j high) { // 用 保证稳定性左区间元素优先 if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j high) tmp[k] arr[j]; // 把合并结果拷回原数组 for (int p low; p high; p) arr[p] tmp[p]; } void mergeSortHelper(std::vectorint arr, std::vectorint tmp, int low, int high) { if (low high) return; int mid low (high - low) / 2; // 防止 lowhigh 溢出 mergeSortHelper(arr, tmp, low, mid); mergeSortHelper(arr, tmp, mid 1, high); merge(arr, tmp, low, mid, high); } void mergeSort(std::vectorint arr) { std::vectorint tmp(arr.size()); // 一次性分配临时数组避免递归中反复分配 mergeSortHelper(arr, tmp, 0, arr.size() - 1); }merge函数里arr[i] arr[j]这个小于等于号是稳定性的关键。如果写成当左右区间有相等元素时右区间的会先被放入稳定性就被破坏了。mid的计算用low (high - low) / 2而不是(low high) / 2是为了防止low high在极端情况下溢出 int 范围。临时数组tmp在mergeSort里一次性分配好通过参数传给递归函数。如果每次merge都新建一个 vector分配和释放的开销会让性能下降好几倍。这个细节在数据量大的时候尤其明显。7. 避坑与排查四个排序算法最容易翻车的地方7.1 数组下标越界与区间开闭混淆现象程序运行到某个排序函数时直接崩溃或者结果里出现莫名其妙的负数。原因快速排序和归并排序的递归函数用的是闭区间[low, high]但调用时传了arr.size()而不是arr.size() - 1。解决统一约定闭区间所有入口调用都减一。写完后用arr.size() 0和arr.size() 1两个边界用例先跑一遍。7.2 快速排序在有序数据上栈溢出现象对已经排好序的十万个整数跑快速排序程序直接崩掉。原因基准选择用了固定位置每次分区极不平衡递归深度达到 n。解决改用三数取中或随机选基准同时加上小区间切换插入排序。如果还是担心直接用非递归版本用显式栈控制深度。7.3 堆排序建堆起始位置写错现象排序结果部分有序但整体不对或者最大值没有出现在末尾。原因建堆循环从n-1开始而不是n/2 - 1导致叶子节点被当成非叶子处理堆性质被破坏。解决记住完全二叉树最后一个非叶子节点的下标是n/2 - 1建堆循环从这里开始递减到 0。7.4 归并排序临时数组反复分配现象归并排序在小数据量上表现正常但数据量上去后比快速排序慢很多。原因每次merge都新建临时数组频繁的堆分配和释放拖慢了整体。解决在顶层一次性分配和原数组等大的临时数组通过参数传递到递归函数中复用。7.5 希尔排序增量序列没有递减到 1现象排序结果不是完全有序总有几个元素位置不对。原因增量序列的终止条件写错gap 没有最终落到 1导致最后一次完整的插入排序没有执行。解决检查 gap 递减公式确保循环结束时 gap 恰好为 1 并执行了最后一轮。可以在循环里打印 gap 值来验证。8. 把四个排序串起来跑一遍性能对比与进阶技巧前面四章把每个算法单独讲完了这一章说一个我常用的验证方法把四个排序放在同一个测试程序里用同一组随机数据跑对比耗时和正确性。这样既能验证实现是否正确也能直观感受不同算法在不同数据规模下的表现差异。int main() { std::vectorint sizes {1000, 10000, 100000, 1000000}; for (int n : sizes) { auto data genRandom(n); std::cout n n \n; auto d1 data; double t1 timeIt(shellSort, d1); std::cout shellSort: t1 ms, sorted isSorted(d1) \n; auto d2 data; double t2 timeIt([](auto a){ quickSort(a, 0, a.size()-1); }, d2); std::cout quickSort: t2 ms, sorted isSorted(d2) \n; auto d3 data; double t3 timeIt(heapSort, d3); std::cout heapSort: t3 ms, sorted isSorted(d3) \n; auto d4 data; double t4 timeIt(mergeSort, d4); std::cout mergeSort: t4 ms, sorted isSorted(d4) \n; } return 0; }这段代码里timeIt接收的是函数对象quickSort因为需要额外参数用了一个 lambda 包装。每个算法都在data的副本上操作互不影响。isSorted的输出直接告诉你排序是否正确如果哪个算法输出sorted0就回到对应章节检查边界条件。实测下来在 100 万随机整数这个量级快速排序通常最快归并排序紧随其后堆排序因为缓存不友好会慢一些希尔排序在百万级已经明显吃力。但如果数据规模降到一万以内四者差距缩小到几毫秒这时候选哪个更多看代码可读性和稳定性需求。一个进阶技巧是混合排序先用快速排序把数组切成小块当子区间长度小于阈值时切换插入排序同时对递归深度做监控超过2*log(n)就切换到堆排序。这样既保留了快速排序的平均性能又避免了最坏情况。标准库的std::sort用的就是类似的 introsort 策略。不过面试时如果被要求手写还是老老实实把四个基础版本写清楚混合策略可以作为加分项提一句。我自己踩过最深的一个坑是早期写快速排序时没有加小区间优化对十万个元素递归下去函数调用开销占了总时间的三成以上。后来加上阈值切换到插入排序同样的数据直接快了一截。这个教训让我养成了一个习惯——写完任何递归算法先想想递归的底层是不是可以换成更轻量的操作。希望这些代码和踩坑记录能帮到你少走一些我当年走过的弯路。本文还有配套的精品资源点击获取
