简介这份资源面向正在学习数据结构与算法、准备课程设计或面试复习的C开发者系统整理了希尔排序、快速排序、堆排序与归并排序四种经典算法的实现代码。压缩包共8个文件约66KB包含2个cpp源文件、1个头文件以及5个txt测试数据文件源码与数据分离便于直接编译运行并对比不同算法在同一数据集上的表现。内容覆盖各算法的核心思路希尔排序的增量序列选择、快速排序的枢轴选取策略、堆排序的完全二叉树调整以及归并排序的合并优化并配有对应测试数据辅助验证。目前已有4146人学习下载适合希望理解分治与堆结构、掌握O(n log n)排序实现细节的读者参考也可作为算法课程实验的对照素材。1. 四路排序算法 C 落地从递归深度到堆调整的工程取舍排序算法是 C 面试和工程里绕不开的基本功但真正把希尔、快速、堆、归并四种排序写进同一个可编译、可对比、可复现的工程里很多人第一次动手就会翻车。这份资源给的是四套算法的 C 实现覆盖了从插入类到交换类、选择类、归并类的完整谱系适合正在准备 C 面试、需要交算法课设、或者想拿真实数据跑一遍性能对比的从业者。它解决的不是知道快排怎么写而是四种排序放在一起边界条件、递归深度、内存分配、稳定性差异到底怎么处理。下面按能编译、能跑通、能对比、能排错的顺序拆开讲每一步都落到可抄的代码和参数上。2. 环境准备与四份源码的工程结构别让编译错误挡在第一步2.1 编译器与 IDE 选型g 和 MSVC 的差异点四种排序都是纯标准库实现不依赖任何第三方库理论上 g、clang、MSVC 都能编。但实际动手时最容易卡住的是两件事一是std::vector传参时的引用写法二是递归函数在 MSVC 下的栈深度警告。我一般用 g 做主力验证命令是g -stdc17 -O2 -Wall sort_demo.cpp -o sort_demo-Wall一定要开快排的边界写错时编译器能帮你抓一部分。如果你在 VS Code 里配 C/C 环境tasks.json里把-stdc17和-O2加上别用默认的 C98否则auto和范围 for 都会报错。MSVC 用户注意/W4下递归函数可能触发 C4717 警告那是编译器对无限递归的误报确认递归出口写对了就可以忽略。2.2 统一接口设计一个函数签名管四种排序四份源码如果各写各的main对比起来会很乱。常见做法是抽一个统一入口签名固定成void sort(std::vectorint arr)四种算法各自实现主函数里用函数指针数组调度。这样跑性能对比时只改一行调用不用复制粘贴四遍计时逻辑。#include vector #include functional #include chrono #include iostream // 四种排序统一签名方便用函数指针调度 using SortFunc std::functionvoid(std::vectorint); void shellSort(std::vectorint arr); void quickSort(std::vectorint arr); void heapSort(std::vectorint arr); void mergeSort(std::vectorint arr); // 计时包装返回毫秒数传入的 arr 会被原地排序 double bench(SortFunc fn, std::vectorint data) { auto start std::chrono::high_resolution_clock::now(); fn(data); // 传值避免影响原始数据 auto end std::chrono::high_resolution_clock::now(); return std::chrono::durationdouble, std::milli(end - start).count(); }这段代码的关键点是bench用传值接收data每次调用都复制一份保证四种算法跑的是同一组原始数据不会因为前一个算法排好了序导致后一个算法作弊。std::function有轻微调用开销但在这个量级下可以忽略换来的是调度代码极简。如果你要跑百万级数据可以把std::function换成裸函数指针void(*)(std::vectorint)省掉类型擦除的开销。2.3 测试数据生成随机数种子必须固定对比排序性能时最容易被忽略的坑是每次跑的数据不一样导致结论不可复现。用std::mt19937配固定种子保证每次生成同一组数据。#include random std::vectorint genData(size_t n, int seed 42) { std::mt19937 rng(seed); // 固定种子保证可复现 std::uniform_int_distributionint dist(0, 1000000); std::vectorint data(n); for (auto x : data) x dist(rng); return data; }seed默认 42想换数据就改这个值。uniform_int_distribution的范围设成 0 到 100 万是为了让数据有足够的分散度避免大量重复值影响快排的分区效果。如果你要测重复值场景把范围改成 0 到 100重复率上来了快排的三路分区优势才体现得出来。3. 希尔排序与归并排序实现增量序列和临时数组的两个关键决策3.1 希尔排序增量序列选错性能差一个量级希尔排序的核心是增量序列。教科书上最常见的是gap gap / 2但这个序列的最坏时间复杂度是 O(n²)实际跑起来比想象中慢。常见做法是用 Knuth 序列gap 3 * gap 1它的平均复杂度接近 O(n^1.3)在中等规模数据上明显更稳。void shellSort(std::vectorint arr) { int n arr.size(); // Knuth 增量序列1, 4, 13, 40, 121... int gap 1; while (gap n / 3) gap 3 * gap 1; for (; gap 1; gap / 3) { // 对每个 gap 做插入排序 for (int i gap; i n; i) { int tmp arr[i]; int j i - gap; while (j 0 arr[j] tmp) { arr[j gap] arr[j]; j - gap; } arr[j gap] tmp; } } }gap从不超过n/3的最大 Knuth 值开始每次除以 3 递减到 1。内层循环就是标准的插入排序只是步长从 1 变成了gap。这里有个容易写错的地方j 0的判断必须在arr[j] tmp之前否则j变成负数时会越界访问。希尔排序是不稳定排序相同值的元素相对顺序可能改变如果你的场景要求稳定性直接跳到归并排序。3.2 归并排序临时数组开在递归里还是外面归并排序最经典的翻车点是每次递归都new一个临时数组导致大量内存分配性能直接掉一半。正确做法是在外层开一个和原数组等大的临时数组递归时只传索引范围。void mergeRange(std::vectorint arr, std::vectorint tmp, int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { // 保证稳定性左边相等时优先取左边 tmp[k] (arr[i] arr[j]) ? arr[i] : arr[j]; } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; for (int p left; p right; p) arr[p] tmp[p]; } void mergeSortImpl(std::vectorint arr, std::vectorint tmp, int left, int right) { if (left right) return; int mid left (right - left) / 2; // 防溢出写法 mergeSortImpl(arr, tmp, left, mid); mergeSortImpl(arr, tmp, mid 1, right); mergeRange(arr, tmp, left, mid, right); } void mergeSort(std::vectorint arr) { std::vectorint tmp(arr.size()); // 只分配一次 mergeSortImpl(arr, tmp, 0, arr.size() - 1); }mid left (right - left) / 2这个写法是为了防止left right在超大数组时溢出 int 范围虽然实际工程里很少遇到但面试时写标准写法是加分项。tmp[k] (arr[i] arr[j]) ? arr[i] : arr[j]里的是稳定性的关键如果写成相等元素会优先取右边稳定性就丢了。归并排序的空间复杂度是 O(n)这个临时数组是省不掉的但只分配一次和每次递归分配性能差距在百万级数据上能到 30% 以上。4. 快速排序与堆排序实现分区策略和堆调整的边界处理4.1 快速排序基准值选取决定最坏情况快排最怕的是有序数据配固定基准值递归深度直接退化成 O(n)栈溢出。常见做法是三数取中取左端、中间、右端三个值的中位数作为基准。int medianOfThree(std::vectorint arr, int left, int right) { int mid left (right - left) / 2; if (arr[left] arr[mid]) std::swap(arr[left], arr[mid]); if (arr[left] arr[right]) std::swap(arr[left], arr[right]); if (arr[mid] arr[right]) std::swap(arr[mid], arr[right]); std::swap(arr[mid], arr[right - 1]); // 把基准藏到 right-1 return arr[right - 1]; } void quickSortImpl(std::vectorint arr, int left, int right) { if (left right) return; if (right - left 16) { // 小区间用插入排序减少递归 for (int i left 1; i right; i) { int tmp arr[i], j i - 1; while (j left arr[j] tmp) { arr[j 1] arr[j]; --j; } arr[j 1] tmp; } return; } int pivot medianOfThree(arr, left, right); int i left, j right - 1; while (true) { while (arr[i] pivot) {} while (arr[--j] pivot) {} if (i j) break; std::swap(arr[i], arr[j]); } std::swap(arr[i], arr[right - 1]); // 基准归位 quickSortImpl(arr, left, i - 1); quickSortImpl(arr, i 1, right); } void quickSort(std::vectorint arr) { if (!arr.empty()) quickSortImpl(arr, 0, arr.size() - 1); }right - left 16这个阈值是小区间切换插入排序的经典优化减少递归调用次数。medianOfThree把基准换到right - 1位置是为了让主循环的i和j有哨兵不用每次判断边界。while (arr[i] pivot)这里没有边界检查依赖的是基准值一定在i和j之间这是三数取中把基准藏到right - 1的原因。如果你把基准放在left这个写法就会越界。4.2 堆排序下沉调整的循环终止条件堆排序的核心是siftDown最容易写错的是循环终止条件。父节点和左子节点的索引关系是child 2 * parent 1循环条件是child n - 1。void siftDown(std::vectorint arr, int parent, int n) { int tmp arr[parent]; int child 2 * parent 1; while (child n) { // 选左右子节点中较大的 if (child 1 n arr[child 1] arr[child]) child; if (tmp arr[child]) break; // 父节点已经最大停止下沉 arr[parent] arr[child]; parent child; child 2 * parent 1; } arr[parent] tmp; } void heapSort(std::vectorint arr) { int n arr.size(); // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; --i) siftDown(arr, i, n); // 逐个把堆顶换到末尾再调整剩余部分 for (int i n - 1; i 0; --i) { std::swap(arr[0], arr[i]); siftDown(arr, 0, i); } }建堆从n / 2 - 1开始这是最后一个非叶子节点。siftDown里用tmp暂存父节点值最后再赋值比每次交换少一半写操作。if (tmp arr[child]) break这个判断是提前终止如果父节点已经比最大的子节点大就不用继续下沉了。堆排序是不稳定排序而且对缓存不友好实际跑起来通常比快排慢但它的最坏时间复杂度稳定在 O(n log n)这是快排给不了的保证。5. 避坑与排查四类排序最容易翻车的五个点5.1 快排递归深度过大导致栈溢出现象跑 10 万条有序数据时程序直接崩溃报 segmentation fault。原因固定基准值遇到有序数据每次分区只减少一个元素递归深度达到 n。解决用三数取中选基准或者加一个递归深度阈值超过2 * log2(n)时切换到堆排序。我一般会在quickSortImpl里加一个depth参数超过 64 层就调heapSort处理当前区间。5.2 归并排序临时数组越界现象归并结果里出现随机值或者程序在mergeRange里崩溃。原因tmp数组大小开成了right - left 1但索引用的是全局的left到right导致越界。解决tmp必须和原数组等大索引直接用left到right不要做偏移。如果你非要开小数组那tmp的索引要改成k - left但这样容易出错不推荐。5.3 希尔排序增量序列死循环现象程序卡在希尔排序里不出来。原因gap gap / 2当gap变成 1 后如果循环条件写成gap 0下一次gap / 2变成 0循环退出但如果写成gap 1且gap是整数1 / 2 0循环也会退出。真正会死循环的是gap gap / 3且初始gap没算对导致gap一直是 0。解决用 Knuth 序列时先while (gap n / 3) gap 3 * gap 1保证gap至少是 1然后for (; gap 1; gap / 3)gap最终会变成 0 退出。5.4 堆排序建堆起始索引写错现象排序结果基本有序但前几个元素位置不对。原因建堆从n / 2开始漏掉了最后一个非叶子节点。解决最后一个非叶子节点的索引是n / 2 - 1建堆循环必须从它开始。可以用n 7手动验证n / 2 - 1 2索引 2 是最后一个有子节点的节点索引 3 到 6 都是叶子。5.5 四种排序共用同一组数据导致结果不可比现象快排跑完 10ms归并跑完 50ms结论是快排快 5 倍。原因快排把数据排好了归并跑的是已经有序的数据归并的有序数据反而更快但如果你先跑归再跑快结论就反过来了。解决bench函数必须传值接收数据每次调用都复制一份原始数据。这个坑我在第一次做性能对比时踩过当时以为是归并实现有问题查了半天才发现是数据被前一个算法改了。6. 性能对比与进阶技巧用真实数据验证四种排序的边界跑完四份实现后最有价值的不是哪个最快而是在什么数据规模和数据特征下哪个最稳。我一般会跑三组数据随机、有序、大量重复每组跑 1 万、10 万、100 万三个量级记录耗时和递归深度。下面是一个可复用的对比框架。int main() { std::vectorsize_t sizes {10000, 100000, 1000000}; std::vectorstd::pairstd::string, SortFunc algos { {Shell, shellSort}, {Quick, quickSort}, {Heap, heapSort}, {Merge, mergeSort} }; for (auto n : sizes) { auto data genData(n); std::cout n n \n; for (auto [name, fn] : algos) { double ms bench(fn, data); std::cout name : ms ms\n; } } return 0; }这段代码跑出来的典型结果是1 万量级四种算法差距不大都在 1ms 以内10 万量级快排和归并领先希尔开始掉队100 万量级快排最快归并紧随其后堆排序因为缓存不友好慢 20% 到 30%希尔最慢。但如果你把数据换成完全有序快排如果不做三数取中会直接退化归并和堆排序反而稳定。这就是为什么工程里很少只用一种排序std::sort内部是快排加堆排加插入排序的混合体std::stable_sort用的是归并。进阶技巧有两个方向。一是把快排的递归改成显式栈避免深递归爆栈写法是把(left, right)压进std::vectorstd::pairint,int循环处理。二是归并排序改成迭代版从步长 1 开始两两合并省掉递归调用开销。这两个改动都不大但能把最坏情况下的稳定性提一个档次。我自己的习惯是每次写完排序都会用assert(std::is_sorted(arr.begin(), arr.end()))验证一遍再跑一组边界数据空数组、单元素、全相同、已有序、逆序。这五组过了基本就不会有玄学 bug。从那以后我每次交排序代码前都强制走一遍这五组边界希望帮到你。本文还有配套的精品资源点击获取
