★ FEATURED ARTICLE 简介这份资源面向C初学者与算法进阶者系统整理了希尔排序、快速排序、堆排序与归并排序四种经典排序算法的完整实现代码帮助读者理解分治、堆调整、增量分组等核心思想并对比各算法的时间复杂度与适用场景。压缩包共8个文件以cpp源码与h头文件为主辅以多个txt测试数据文件整体约66KB结构紧凑便于直接编译运行与调试。目前已有4146人学习下载说明其在算法入门与面试复习中具有较高参考价值。读者可获得可直接运行的排序实现结合不同规模的数据文件验证性能差异并参考描述中关于增量序列选择、枢轴选取、堆性质维护及归并空间优化的要点加深对算法细节的掌握适合课程实验、面试准备与算法效率分析等场景。1. 四种排序一把梭为什么 C 手写排序仍是绕不开的基本功很多人第一次在 VS Code 里配好 C 环境、跑通一个Hello World之后紧接着写的第二段代码就是排序。看着std::sort一行搞定难免会想都 2025 年了为什么面试、算法课、甚至一些底层模块还在要求手写希尔排序、快速排序、堆排序、归并排序答案很直接——std::sort是黑匣子它内部混合了内省排序快排 堆排 插入排序你调它永远不知道数据在什么分布下会退化、什么时候会触发 O(n log n) 之外的行为。而把这四种排序用 C 亲手实现一遍你拿到的是对时间复杂度、空间复杂度、稳定性、缓存友好度这四个维度的肌肉记忆。这篇笔记就按一线落地的路子把四份能直接编译运行的 C 代码、每份的关键参数、以及我踩过的坑讲清楚适合刚入门想夯实基础的人也适合准备面试想系统梳理的人。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)稳定链表排序、外部排序、要求稳定选型的判断顺序我一般是先看是否要求稳定要稳定直接归并再看是否对最坏时间有硬约束有就堆排再看内存是否紧张紧张就快排或堆排最后看数据规模小规模希尔反而常数更小。2.2 统一接口与测试骨架四份实现我都用同一套接口方便对比和跑测试。先搭好骨架后面每个算法只替换核心函数// sort_common.h #pragma once #include vector #include cstddef // 统一升序排序接口所有算法签名一致便于替换对比 void shellSort(std::vectorint a); void quickSort(std::vectorint a); void heapSort(std::vectorint a); void mergeSort(std::vectorint a); // 校验工具确认结果升序且元素集合未变 bool isSorted(const std::vectorint a);// sort_common.cpp #include sort_common.h #include algorithm bool isSorted(const std::vectorint a) { for (size_t i 1; i a.size(); i) { if (a[i - 1] a[i]) return false; // 发现逆序立即返回 } return true; }参数说明接口统一用std::vectorint引用传参避免拷贝isSorted只做升序校验配合std::is_permutation可以进一步确认元素集合没被改动。测试时我习惯用std::mt19937生成随机数规模从 10 到 100000 各跑一遍边界用全等、逆序、已排序三种极端输入。提示不要一上来就写 10 万规模的压力测试先用 10 个元素手算验证逻辑再放大规模否则出错时根本定位不到是哪一步划分错了。3. 希尔排序增量序列选错性能直接打回插入排序3.1 增量序列为什么是希尔排序的命门希尔排序的本质是「分组插入排序」先用较大的增量把元素大致归位再逐步缩小增量做精细调整。增量序列的选择直接决定复杂度用n/2, n/4, ...这种折半序列最坏仍是 O(n²)用 Hibbard 序列1, 3, 7, 15, ...即 2^k - 1可以做到 O(n^1.5)用 Sedgewick 序列能到 O(n^1.3)。我一般教学和面试用折半序列因为好写生产代码里如果真要用希尔会换成 Knuth 序列1, 4, 13, 40, ...即 3h1。3.2 折半增量版本的完整实现// shell_sort.cpp #include sort_common.h void shellSort(std::vectorint a) { int n static_castint(a.size()); // gap 从 n/2 开始折半直到 1最后一轮就是标准插入排序 for (int gap n / 2; gap 0; gap / 2) { // 对每个分组做插入排序i 从 gap 开始保证同组元素可比 for (int i gap; i n; i) { int key a[i]; // 当前待插入元素 int j i - gap; // 同组前一个元素下标 // 同组内向前找位置比 key 大的整体后移 gap while (j 0 a[j] key) { a[j gap] a[j]; j - gap; } a[j gap] key; // 落位 } } }逻辑说明外层gap控制增量内层i遍历每个分组的第一个待插入元素while循环在组内做「移位腾位」。注意j - gap而不是j--这是分组插入和普通插入的唯一区别。参数上gap的初始值取n/2是折半序列改成gap gap * 3 1的逆序生成就是 Knuth 序列性能会明显不同。3.3 增量序列对性能的实测影响我在 10 万随机整数上跑过对比折半序列大约 18msKnuth 序列约 12msSedgewick 序列约 9ms。差距不算天翻地覆但在嵌入式或对延迟敏感的场景里选对序列是白捡的收益。另一个容易忽略的点是希尔排序在「近乎有序」的数据上表现极好因为插入排序本身对有序数据是 O(n)希尔的前几轮增量会快速把数据推向有序。注意希尔排序不稳定。如果你需要稳定排序别在希尔上做文章直接换归并。4. 快速排序基准选不好O(n²) 就在门口等你4.1 划分逻辑与基准选择策略快排的核心是 partition选一个基准把小于它的放左边、大于它的放右边然后递归两边。基准选择是快排的生死线——固定选第一个元素遇到已排序数组直接退化成 O(n²)随机选或三数取中能把这种概率降到极低。我一般用「三数取中 小区间插入排序」的组合这也是很多标准库快排的常见做法。4.2 三数取中 小区间优化的实现// quick_sort.cpp #include sort_common.h #include algorithm // 三数取中取左、中、右三个位置的中位数作为基准放到最左 static int medianOfThree(std::vectorint 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]); std::swap(a[mid], a[lo]); // 中位数换到 lo 位置作为基准 return a[lo]; } static void quickSortImpl(std::vectorint a, int lo, int hi) { // 小区间阈值 16改用插入排序减少递归开销 if (hi - lo 16) { for (int i lo 1; i hi; i) { int key a[i], j i - 1; while (j lo a[j] key) { a[j 1] a[j]; --j; } a[j 1] key; } return; } int pivot medianOfThree(a, lo, hi); int i lo, j hi; while (i j) { while (i j a[j] pivot) --j; // 从右找小于基准的 while (i j a[i] pivot) i; // 从左找大于基准的 if (i j) std::swap(a[i], a[j]); } std::swap(a[lo], a[i]); // 基准归位 quickSortImpl(a, lo, i - 1); quickSortImpl(a, i 1, hi); } void quickSort(std::vectorint a) { if (a.size() 1) quickSortImpl(a, 0, static_castint(a.size()) - 1); }逻辑说明medianOfThree把中位数换到lo位置主循环用双指针从两端向中间夹逼i和j相遇处就是基准的最终位置。小区间阈值 16 是经验值太小递归开销大太大插入排序的 O(n²) 会拖后腿。参数上阈值可以按数据规模调10 万以下 16 比较稳。4.3 递归深度与栈溢出的处理快排最坏递归深度是 O(n)10 万逆序数据可能直接把栈打爆。两个办法一是先递归较小的一边、用循环处理较大的一边尾递归优化二是显式用栈模拟。我一般用前者改动很小// 尾递归优化片段先处理短的一边长的一边用循环 while (lo hi) { int p partition(a, lo, hi); if (p - lo hi - p) { quickSortImpl(a, lo, p - 1); lo p 1; } else { quickSortImpl(a, p 1, hi); hi p - 1; } }这样递归深度稳定在 O(log n)栈溢出基本不会出现。5. 堆排序与归并排序一个拼最坏时间一个拼稳定性5.1 堆排序的下沉与建堆细节堆排序分两步建大顶堆、逐个把堆顶换到末尾再下沉。建堆从最后一个非叶节点n/2 - 1开始往前下沉这一步是 O(n)之后每次取堆顶是 O(log n)总共 O(n log n)。堆排最大的优势是最坏时间也是 O(n log n)且原地排序适合对最坏延迟有硬要求的场景。// heap_sort.cpp #include sort_common.h #include algorithm // 下沉把 i 位置的元素在 [0, n) 范围内向下调整 static void siftDown(std::vectorint a, int i, int n) { while (true) { int l 2 * i 1, r 2 * i 2, largest i; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest i) break; // 已满足堆性质 std::swap(a[i], a[largest]); i largest; // 继续向下 } } void heapSort(std::vectorint a) { int n static_castint(a.size()); // 建堆从最后一个非叶节点开始下沉 for (int i n / 2 - 1; i 0; --i) siftDown(a, i, n); // 逐个把堆顶最大值换到末尾堆规模减一 for (int i n - 1; i 0; --i) { std::swap(a[0], a[i]); siftDown(a, 0, i); } }参数说明siftDown的第三个参数n是当前堆的有效规模取堆顶后要减一。建堆循环从n/2 - 1开始因为下标大于它的都是叶子节点天然满足堆性质。5.2 归并排序的临时数组与稳定性归并排序是唯一稳定的 O(n log n) 排序代价是需要 O(n) 额外空间。实现上分递归版和迭代版递归版好写迭代版省栈。关键点是合并时「左边小于等于右边就取左边」这个等号保证了稳定性。// merge_sort.cpp #include sort_common.h #include vector static void merge(std::vectorint a, std::vectorint tmp, int lo, int mid, int hi) { int i lo, j mid 1, k lo; while (i mid j hi) { // 用 保证稳定性相等时优先取左半部分 if (a[i] a[j]) tmp[k] a[i]; else tmp[k] a[j]; } while (i mid) tmp[k] a[i]; // 左半剩余 while (j hi) tmp[k] a[j]; // 右半剩余 for (int t lo; t hi; t) a[t] tmp[t]; // 拷回原数组 } static void mergeSortImpl(std::vectorint a, std::vectorint tmp, int lo, int hi) { if (lo hi) return; int mid lo (hi - lo) / 2; mergeSortImpl(a, tmp, lo, mid); mergeSortImpl(a, tmp, mid 1, hi); merge(a, tmp, lo, mid, hi); } void mergeSort(std::vectorint a) { if (a.size() 2) return; std::vectorint tmp(a.size()); // 一次性分配避免递归中反复申请 mergeSortImpl(a, tmp, 0, static_castint(a.size()) - 1); }逻辑说明tmp数组在入口处一次性分配好传进去避免每层递归都new一次。合并时是稳定性的关键改成就不稳定了。参数上mid lo (hi - lo) / 2而不是(lo hi) / 2是为了防止lo hi溢出。5.3 四份实现放在一起跑一遍把四个.cpp和sort_common.cpp一起编译写个 main 跑随机数据对比g -stdc17 -O2 main.cpp sort_common.cpp shell_sort.cpp quick_sort.cpp heap_sort.cpp merge_sort.cpp -o sort_demo ./sort_demo// main.cpp 片段 #include sort_common.h #include random #include chrono #include iostream int main() { std::mt19937 rng(42); std::uniform_int_distributionint dist(0, 1000000); std::vectorint base(100000); for (auto x : base) x dist(rng); auto run [](const char* name, void(*fn)(std::vectorint)) { auto v base; auto t0 std::chrono::high_resolution_clock::now(); fn(v); auto t1 std::chrono::high_resolution_clock::now(); double ms std::chrono::durationdouble, std::milli(t1 - t0).count(); std::cout name : ms ms, sorted isSorted(v) \n; }; run(shell, shellSort); run(quick, quickSort); run(heap, heapSort); run(merge, mergeSort); }10 万随机数据下我这边实测快排约 8ms、归并约 11ms、堆排约 14ms、希尔约 18ms。数字会随机器和编译器变化但相对关系基本稳定快排最快堆排因为缓存不友好偏慢归并多了一次拷贝。6. 避坑与排查这四种排序最容易翻车的五个地方6.1 快排遇到大量重复元素退化成 O(n²)现象数组里全是相同元素时快排耗时暴涨。原因基础的双指针划分把等于基准的元素全分到一边两边极度不平衡。解决改用三路划分小于、等于、大于三段或者用 Hoare 划分而不是 Lomuto 划分。三路划分在重复元素多的场景下能直接降到 O(n)。6.2 归并排序临时数组反复分配导致性能骤降现象归并比预期慢很多甚至比堆排还慢。原因在merge函数里每次new一个临时数组10 万数据下分配次数上万。解决在入口处一次性分配tmp递归中复用就像上面代码那样。6.3 堆排序建堆起点写错导致结果不对现象排序结果部分有序但整体不对。原因建堆循环从n - 1开始而不是n/2 - 1对叶子节点做无意义的下沉逻辑上没错但效率低更常见的是写成n/2导致漏掉一个非叶节点。解决记住最后一个非叶节点下标是n/2 - 1从它开始往前。6.4 希尔排序增量序列写成gap--导致退化成插入排序现象希尔排序和插入排序耗时几乎一样。原因增量每次减一最后一轮之前的所有轮次几乎没起到分组作用。解决增量至少要用折半或 Knuth 序列保证每轮分组数快速收敛。6.5 递归快排在大数据上栈溢出现象程序在 10 万以上逆序数据上崩溃。原因最坏递归深度 O(n)每层栈帧几十字节累计超过默认栈大小。解决先递归短的一边、长的一边用循环把递归深度压到 O(log n)或者显式用栈模拟递归。7. 进阶技巧用模板把四份代码合成一个可切换的排序工具箱写到这一步四份代码各自独立但实际项目里我更愿意把它们做成模板支持任意可比较类型并且能通过策略在运行时切换。核心思路是把「比较」和「交换」抽出来用模板参数传入// sort_box.h #pragma once #include vector #include functional template typename T, typename Less std::lessT class SortBox { public: explicit SortBox(Less less Less{}) : less_(less) {} void shell(std::vectorT a) const { /* 同前比较用 less_ */ } void quick(std::vectorT a) const { /* ... */ } void heap(std::vectorT a) const { /* ... */ } void merge(std::vectorT a) const { /* ... */ } private: Less less_; };这样SortBoxint排整数SortBoxstd::string排字符串SortBoxMyStruct, MyCmp排自定义结构体一份代码通吃。参数上Less默认std::lessT传入自定义比较器就能实现降序或按多字段排序。验证方法我一般分三层第一层用isSorted确认升序第二层用std::is_permutation确认元素集合没变第三层用std::sort的结果做基准逐元素比对。三层都过基本可以放心。验证层检查内容工具第一层结果是否升序isSorted第二层元素集合是否一致std::is_permutation第三层与标准库结果是否逐元素相等std::sort 最后说个我自己的习惯每次写完一个排序先用 5 个元素手算一遍再用 100 个随机数跑最后才上 10 万压力测试。这个顺序帮我省了无数次调试时间——小数据出错是逻辑问题大数据出错才是性能问题两者排查思路完全不同。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
