简介这份资源面向C初学者与算法进阶者系统整理了希尔排序、快速排序、堆排序与归并排序四种经典排序算法的完整实现代码帮助读者理解分治、增量分组、堆调整等核心思想并对比各算法的时间复杂度与适用场景。压缩包共8个文件以5个txt测试数据文件、2个cpp源码文件与1个h头文件为主源码与数据分离便于直接编译运行并观察不同数据规模下的排序表现整体约66KB轻量易读。目前已有4147人学习下载适合作为数据结构课程实验、算法练习或面试复习的参考材料。读者可从中获得可直接运行的C实现、配套测试数据以及关于增量序列选择、枢轴选取、堆性质维护与归并合并优化等关键实现细节的对照思路便于快速验证与二次修改。1. 四种排序一起手写为什么 C 面试和工程代码都绕不开这一关很多人第一次被要求「手写排序」时脑子里只有冒泡和选择排序结果面试官一句「写个归并吧」就卡壳。C 实现希尔、快速、堆排序、归并排序算法本质是把四类不同思路的排序一次性吃透插入类改进希尔、分治交换快排、树形选择堆排、分治归并归并。它们覆盖了 O(n log n) 的主流路径也是理解 STLsort内部 introsort 的前置知识。这篇文章面向正在准备 C 岗位、刷算法题、或者要给自己的小工具写排序模块的人。我会把四份可编译的完整代码、每行关键参数、以及我实际踩过的坑都摊开讲你照着敲一遍就能跑改几个参数就能对比性能。不玩虚的直接上代码和实测。2. 先把四个算法的骨架搭对C 实现里的接口设计与数组边界2.1 统一函数签名与测试框架四个排序如果各写各的接口后面做性能对比会非常痛苦。我一般先定一个统一签名void sortName(std::vectorint arr)全部原地修改不返回新数组。这样测试代码只写一次换函数名就能跑。下面是我常用的测试骨架包含随机数据生成和计时。#include iostream #include vector #include chrono #include random #include algorithm using namespace std; using namespace std::chrono; // 统一签名原地排序 void shellSort(vectorint arr); void quickSort(vectorint arr); void heapSort(vectorint arr); void mergeSort(vectorint arr); // 生成随机数组 vectorint genRandom(int n, int maxVal 100000) { vectorint v(n); mt19937 rng(42); // 固定种子保证每次数据一致 uniform_int_distributionint dist(0, maxVal); for (int i 0; i n; i) v[i] dist(rng); return v; } // 计时模板 templatetypename Func long long timeIt(Func f, vectorint arr) { auto start high_resolution_clock::now(); f(arr); auto end high_resolution_clock::now(); return duration_castmicroseconds(end - start).count(); } int main() { vectorint base genRandom(100000); cout shell: timeIt(shellSort, base) us\n; cout quick: timeIt(quickSort, base) us\n; cout heap: timeIt(heapSort, base) us\n; cout merge: timeIt(mergeSort, base) us\n; return 0; }这段代码的关键点有三个。第一mt19937是 C11 起的标准梅森旋转随机数引擎比rand()质量高得多固定种子 42 保证每次跑的数据完全一样否则你没法对比算法差异。第二timeIt接收的是vectorint arr值传递内部会拷贝一份这样原数组不会被排序破坏四个算法跑的是同一份原始数据。第三计时单位用微秒10 万数据量下快排大概几千微秒用毫秒会丢精度。提示如果你在 VS Code 里配 C 环境编译命令记得加-O2否则 Debug 模式下四个算法都慢得看不出差距。我一般用g -stdc17 -O2 main.cpp -o main。2.2 希尔排序增量序列选错性能直接退化成插入排序希尔排序是插入排序的改进版核心思想是先用较大增量把数组变得「基本有序」再逐步缩小增量做插入排序。增量序列的选择直接决定复杂度用n/2, n/4, ...最坏是 O(n²)用 Knuth 序列1, 4, 13, 40, ...可以到 O(n^1.5)。我一般用 Knuth 序列代码稍微多两行但值得。void shellSort(vectorint arr) { int n arr.size(); // 生成 Knuth 增量序列1, 4, 13, 40, 121... int gap 1; while (gap n / 3) gap gap * 3 1; for (; gap 1; gap (gap - 1) / 3) { // 对每个 gap 做插入排序 for (int i gap; i n; i) { int key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }逻辑说明外层gap从大到小内层就是标准的插入排序只不过步长从 1 变成gap。while (gap n / 3) gap gap * 3 1是在找不超过 n/3 的最大 Knuth 数这样第一轮 gap 不会太大导致无效比较。参数方面如果你把增量改成gap gap / 210 万随机数据下耗时会从约 8000 微秒涨到 15000 微秒左右差距肉眼可见。注意内层while的条件是arr[j] key不是用虽然结果正确但会多做无谓交换。2.3 快速排序基准值选不对递归深度能把栈撑爆快排的坑几乎全在基准值pivot选择上。固定选第一个元素遇到已排序数组会退化成 O(n²)递归深度到 n10 万数据直接栈溢出。我一般用「三数取中」取左、中、右三个位置的中位数作为 pivot放到最左边然后走经典的 Hoare 分区。int medianOfThree(vectorint arr, int lo, int hi) { int mid lo (hi - lo) / 2; if (arr[mid] arr[lo]) swap(arr[mid], arr[lo]); if (arr[hi] arr[lo]) swap(arr[hi], arr[lo]); if (arr[hi] arr[mid]) swap(arr[hi], arr[mid]); // 此时 arr[mid] 是中位数换到 lo 位置 swap(arr[mid], arr[lo]); return arr[lo]; } int partition(vectorint arr, int lo, int hi) { int pivot medianOfThree(arr, lo, hi); int i lo, j hi 1; while (true) { while (arr[i] pivot) if (i hi) break; while (arr[--j] pivot) if (j lo) break; if (i j) break; swap(arr[i], arr[j]); } swap(arr[lo], arr[j]); // pivot 归位 return j; } void quickSortHelper(vectorint arr, int lo, int hi) { if (lo hi) return; int p partition(arr, lo, hi); quickSortHelper(arr, lo, p - 1); quickSortHelper(arr, p 1, hi); } void quickSort(vectorint arr) { quickSortHelper(arr, 0, arr.size() - 1); }medianOfThree里三次比较把中位数换到arr[mid]再换到arr[lo]这样partition里可以直接用arr[lo]当 pivot。partition用的是 Hoare 分区方案i从 lo 开始、j从 hi1 开始先加再比避免边界死循环。注意while (arr[i] pivot) if (i hi) break;这行如果数组里全是相同元素没有i hi的保护会越界。参数上如果你把三数取中改成随机取 pivot性能差不多但随机数生成有开销10 万数据下反而慢 5% 左右。递归深度方面三数取中后 10 万随机数据深度约 20 层完全安全。2.4 堆排序下标从 0 开始子节点公式别写错堆排序分两步建大顶堆然后不断把堆顶和末尾交换、缩小堆范围、下沉调整。很多人翻车在下标公式上如果数组从 0 开始节点 i 的左子是2*i1右子是2*i2父节点是(i-1)/2。从 1 开始的公式是另一套混用必错。void siftDown(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; swap(arr[i], arr[largest]); i largest; } } void heapSort(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) { swap(arr[0], arr[i]); siftDown(arr, i, 0); } }siftDown里largest先假设是当前节点然后和左右子比较谁大记谁。如果largest变了就交换并继续下沉。建堆从n/2 - 1开始这是最后一个非叶子节点因为叶子节点本身已经满足堆性质。排序阶段每次把arr[0]当前最大值换到arr[i]然后对前 i 个元素重新下沉。参数注意siftDown的第二个参数是当前堆的有效大小排序阶段传的是i而不是n写错的话已排好的部分会被重新打乱。堆排序是不稳定排序但原地、最坏 O(n log n)适合对内存敏感的场景。2.5 归并排序临时数组开在递归里内存直接爆炸归并排序的经典写法是递归分治合并时需要额外空间。新手最容易犯的错是在merge函数里每次new一个临时数组10 万数据递归 17 层每层都分配释放不仅慢还可能内存碎片。正确做法是在外层开一个和原数组等大的临时数组全程复用。void merge(vectorint arr, vectorint tmp, int lo, int mid, int hi) { int i lo, j mid 1, k lo; while (i mid j hi) tmp[k] (arr[i] arr[j]) ? arr[i] : arr[j]; while (i mid) tmp[k] arr[i]; while (j hi) tmp[k] arr[j]; for (int p lo; p hi; p) arr[p] tmp[p]; } void mergeSortHelper(vectorint arr, vectorint tmp, int lo, int hi) { if (lo hi) return; int mid lo (hi - lo) / 2; mergeSortHelper(arr, tmp, lo, mid); mergeSortHelper(arr, tmp, mid 1, hi); merge(arr, tmp, lo, mid, hi); } void mergeSort(vectorint arr) { vectorint tmp(arr.size()); mergeSortHelper(arr, tmp, 0, arr.size() - 1); }merge里tmp[k] (arr[i] arr[j]) ? arr[i] : arr[j]这行用而不是是为了保证稳定性相等时先取左边的这样相同元素的相对顺序不变。mid lo (hi - lo) / 2而不是(lo hi) / 2防止 lo 和 hi 都很大时整数溢出。临时数组tmp在mergeSort里只分配一次通过参数传给递归函数。归并排序是稳定排序时间复杂度稳定 O(n log n)代价是 O(n) 额外空间。如果数据量特别大可以考虑用std::inplace_merge做原地归并但实现复杂且常数大一般不建议。3. 四份代码跑起来编译、计时与结果对比的完整流程3.1 编译命令与常见报错处理把上面所有代码放进一个main.cpp用下面命令编译。如果你在 Windows 上装了 Visual C 运行库但没装编译器需要先装 MinGW 或 MSVC 构建工具。g -stdc17 -O2 -Wall main.cpp -o sort_bench ./sort_bench-stdc17是因为用了mt19937和chronoC11 就够但 17 更稳。-O2必须加否则 Debug 模式下快排和归并的递归开销会被放大好几倍。-Wall打开所有警告能帮你发现未使用变量、符号比较这类问题。常见报错‘mt19937’ was not declared说明没加#include randomhigh_resolution_clock找不到说明没加#include chrono链接错误一般是函数声明了没定义检查四个排序函数是否都写了实现。3.2 10 万随机数据的实测结果与解读我在自己机器上跑出来的典型结果如下单位微秒不同 CPU 会有差异但相对关系稳定算法10 万随机数据耗时是否稳定额外空间最坏复杂度希尔排序约 8000否O(1)O(n^1.5)快速排序约 6000否O(log n) 栈O(n²)堆排序约 12000否O(1)O(n log n)归并排序约 9000是O(n)O(n log n)快排最快是因为它的内存访问模式对 CPU 缓存最友好常数最小。堆排序最慢是因为每次下沉都要跳着访问数组缓存命中率低。归并排序居中但它的优势是稳定和最坏情况有保证。希尔排序在随机数据上表现不错但如果数据已经基本有序它会退化得比较明显。注意这个表格是随机数据的结果。如果你把输入换成完全逆序快排的三数取中仍然能保持 O(n log n)但希尔排序的 Knuth 序列会慢一些。换成大量重复元素快排的 Hoare 分区性能会下降这时候可以考虑三路快排。3.3 用 std::sort 做基准对照自己写的排序到底行不行最直接的验证是和std::sort比。STL 的sort是 introsort快排堆排插入排序混合在 10 万随机数据上通常只要 4000 微秒左右比手写快排快 30% 到 50%。差距主要来自内联优化、迭代器抽象和更精细的小数组处理。你可以在main里加一行vectorint copy base; auto start high_resolution_clock::now(); sort(copy.begin(), copy.end()); auto end high_resolution_clock::now(); cout std::sort: duration_castmicroseconds(end - start).count() us\n;如果手写快排和std::sort差距在 2 倍以内说明你的实现已经合格了。差距过大就检查是不是递归里传了值、是不是每次都在分配内存、是不是没开-O2。4. 避坑与排查四个排序最容易翻车的五个地方4.1 快排递归栈溢出现象是程序直接崩溃原因是基准值选得太偏现象10 万数据跑快排程序报stack overflow或直接段错误。原因固定选第一个元素当 pivot输入恰好是升序或降序每次分区只减少一个元素递归深度到 n。解决改成三数取中或随机取 pivot递归深度降到 log n。如果还怕可以把递归改成显式栈的迭代版本但代码会复杂不少一般没必要。4.2 归并临时数组反复分配现象是越跑越慢原因是 merge 里 new 了数组现象归并排序在小数据上正常数据量一大就明显变慢甚至比堆排序还慢。原因merge函数里每次调用都vectorint tmp(hi - lo 1)递归 17 层就是 17 次分配释放。解决在外层mergeSort里分配一个和原数组等大的tmp通过参数传进递归全程复用。这个改动能让归并排序提速 30% 以上。4.3 堆排序下标公式混用现象是排序结果部分有序部分乱原因是 0 基和 1 基公式搞混现象堆排序跑完数组不是完全有序有些段对有些段错。原因建堆或下沉时用了 1 基公式2*i和2*i1但数组是 0 基。解决统一用 0 基公式左子2*i1右子2*i2父(i-1)/2。建议在纸上画一个 7 元素的小数组手动走一遍建堆过程确认公式无误再写代码。4.4 希尔增量序列选错现象是比插入排序还慢原因是 gap 每次只减 1现象希尔排序在 10 万数据上跑了 5 秒还没结束。原因增量写成gap gap - 1或者gap gap / 3但没生成 Knuth 序列导致 gap 序列退化成 O(n) 轮。解决用gap gap * 3 1生成序列然后gap (gap - 1) / 3递减。这样 gap 序列是 1, 4, 13, 40...轮数是 O(log n)。4.5 比较函数写反导致稳定性丢失现象是相同元素的相对顺序变了原因是用了严格大于现象归并排序对包含重复元素的数组排序后相同值的元素顺序和输入不一致。原因merge里用了arr[i] arr[j]而不是arr[i] arr[j]相等时先取了右边的。解决归并排序要稳定必须用。快排和堆排本身不稳定不用纠结这个但如果业务要求稳定就选归并或者std::stable_sort。5. 进阶技巧用模板和迭代器把四个排序变成通用工具上面四个排序都写死了vectorint实际工程里你可能要排vectordouble、vectorstring或者自定义结构体。最省事的改法是加模板参数和比较器。下面以快排为例其他三个同理。templatetypename T, typename Compare std::lessT void quickSortGeneric(std::vectorT arr, Compare comp Compare()) { std::functionvoid(int, int) helper [](int lo, int hi) { if (lo hi) return; T pivot arr[lo (hi - lo) / 2]; int i lo, j hi; while (i j) { while (comp(arr[i], pivot)) i; while (comp(pivot, arr[j])) --j; if (i j) { std::swap(arr[i], arr[j]); i; --j; } } helper(lo, j); helper(i, hi); }; helper(0, arr.size() - 1); }这个版本用了std::function递归 lambda代码更紧凑但std::function有类型擦除开销性能比裸函数指针慢 10% 到 20%。如果追求极致性能还是写独立的模板函数。比较器默认std::lessT传std::greaterT就能降序。注意pivot这里取的是中间位置的值而不是三数取中因为模板版本里三数取中需要comp配合写起来啰嗦中间值在大多数场景够用。验证方法很简单用vectorstring排一组单词或者用自定义结构体按某个字段排看结果是否符合预期。我一般还会加一个is_sorted检查templatetypename T bool isSorted(const std::vectorT arr) { for (size_t i 1; i arr.size(); i) if (arr[i] arr[i - 1]) return false; return true; }每次排序后调一下返回 false 就说明实现有问题。这个习惯帮我省了很多调试时间。最后说个我自己的教训早年写快排时为了「优化」把递归改成尾递归结果编译器没做尾调用优化性能反而降了。后来老老实实写普通递归开-O2什么问题都没有。排序算法这东西先把正确性和边界写对再谈优化顺序反了就是给自己挖坑。希望帮到你。本文还有配套的精品资源点击获取
