简介这份资源面向C初学者与算法进阶者系统整理了希尔排序、快速排序、堆排序与归并排序四种经典算法的完整实现代码帮助读者理解分治、堆调整、增量分组等核心思想并对比各算法的时间复杂度与适用场景。压缩包共8个文件以cpp源码与h头文件为主辅以多个txt测试数据文件整体约66KB结构紧凑便于直接编译运行与调试。目前已有4147人学习下载说明其在算法练习与面试复习中具有较高参考价值。读者可获得可直接运行的排序实现结合不同规模数据验证性能差异并参考增量序列选择、枢轴优化、堆性质维护及归并合并等关键细节加深对排序算法工程实现的理解适合课程实验、算法刷题与面试准备时对照学习。1. 四种排序算法放在同一个 C 工程里到底该怎么读很多人第一次接触排序算法都是在一个.cpp里写一个main然后分别把冒泡、插入、选择挨个跑一遍输出几行数组就结束了。这种写法用来交作业没问题但一旦你想把希尔、快速、堆排序、归并这四种放在一起对比问题立刻暴露接口不统一、计时方式不一致、数据规模太小看不出差异、递归深度没控制、边界条件各写各的。我见过太多人拿着四份互相不兼容的代码跑出来的时间对比毫无参考价值。这份 C 实现希尔、快速、堆排序、归并排序算法的资源价值就在于它把这四种算法收进同一套接口和同一套测试框架里。它解决的不是「排序怎么写」这种入门问题而是「四种排序在同一基准下怎么比、各自在什么数据分布下会退化、递归和迭代版本怎么切换」。适合已经会写基本排序、想搞清楚工程化对比和性能边界的 C 学习者也适合需要给团队做算法选型参考的开发者。读完你至少能拿到一份可编译、可改参数、可复现的对比代码而不是四段孤立的示例。2. 先统一接口再谈性能四种排序的骨架怎么搭2.1 为什么不能各写各的main四种排序如果各自带一个main你没法在同一份随机数据上跑对比也没法复用计时逻辑。常见做法是抽一个sort_interface.h把排序函数统一成void sort(std::vectorint data)这种签名内部再分派到具体实现。这样测试代码只写一遍换算法只换函数指针或枚举。// sort_interface.h #pragma once #include vector #include string // 统一排序接口所有算法都接收 vectorint 引用原地排序 using SortFunc void(*)(std::vectorint); // 算法枚举方便在测试里按名字选择 enum class SortType { Shell, Quick, Heap, Merge }; // 根据枚举返回对应函数指针 SortFunc get_sort_func(SortType type); // 生成测试数据size 个元素分布由 dist 决定 std::vectorint make_data(size_t size, const std::string dist);这段代码的关键点是SortFunc类型别名和SortType枚举。函数指针让测试框架可以像插件一样切换算法枚举则避免用字符串比较带来的拼写错误。make_data的dist参数后面会用来生成随机、升序、降序、近乎有序等不同分布这是看出算法退化点的核心。2.2 希尔排序的增量序列怎么选希尔排序的性能几乎完全取决于增量序列。最常见的写法是gap gap / 2也就是每次折半但这条序列的最坏时间复杂度是 O(n²)在特定数据上会明显拖后腿。工程里更常用的是 Knuth 序列1, 4, 13, 40, ...递推式是h 3 * h 1反向使用。// shell_sort.cpp #include sort_interface.h void shell_sort(std::vectorint data) { int n static_castint(data.size()); // 用 Knuth 序列生成最大 gap1, 4, 13, 40... int gap 1; while (gap n / 3) { gap gap * 3 1; } // 反向收缩 gap直到 1 for (; gap 0; gap (gap - 1) / 3) { // 对每个 gap 做插入排序 for (int i gap; i n; i) { int key data[i]; int j i - gap; while (j 0 data[j] key) { data[j gap] data[j]; j - gap; } data[j gap] key; } } }gap (gap - 1) / 3是 Knuth 序列的反向递推保证最后一定落到 1。内层循环就是带间隔的插入排序key暂存当前元素j从i - gap开始往前跳。参数上唯一需要调的就是序列生成方式如果你换成gap / 2代码更短但在 10 万级逆序数据上会慢一截这个差异在后面的对比表里能直接看到。2.3 快速排序的三路划分与递归深度控制快速排序最容易被写坏的地方有两个一是基准选不好导致 O(n²)二是递归太深导致栈溢出。常见做法是随机选基准加三路划分把等于基准的元素集中到中间避免大量重复元素时左右子区间不平衡。// quick_sort.cpp #include sort_interface.h #include utility #include cstdlib // 三路划分小于 pivot、等于 pivot、大于 pivot static void quick_sort_impl(std::vectorint data, int left, int right) { if (left right) return; // 随机选基准避免有序数据退化 int pivot_idx left rand() % (right - left 1); std::swap(data[left], data[pivot_idx]); int pivot data[left]; int lt left; // [left, lt) 小于 pivot int gt right; // (gt, right] 大于 pivot int i left 1; // 当前扫描位置 while (i gt) { if (data[i] pivot) { std::swap(data[lt], data[i]); } else if (data[i] pivot) { std::swap(data[i], data[gt--]); } else { i; } } // 递归处理左右两段中间等于 pivot 的已经就位 quick_sort_impl(data, left, lt - 1); quick_sort_impl(data, gt 1, right); } void quick_sort(std::vectorint data) { quick_sort_impl(data, 0, static_castint(data.size()) - 1); }lt、gt、i三个指针把区间切成三段等于pivot的元素不再参与递归这是三路划分相对二路划分的最大优势。随机基准用rand()实现注意在测试前调用一次srand()否则每次跑出来的基准序列一样对比就失去意义。递归深度在随机基准下期望是 O(log n)但如果你的数据里有大量重复且基准选得不好仍然可能加深工程里可以加一个深度阈值超过就切换到堆排序这就是内省排序的思路。2.4 堆排序的下滤与建堆顺序堆排序分两步建大顶堆然后反复把堆顶和末尾交换、缩小堆、下滤。很多人建堆时从 0 开始往上调整这是错的正确做法是从最后一个非叶子节点n/2 - 1开始往前下滤。// heap_sort.cpp #include sort_interface.h #include utility // 下滤把 idx 位置的元素在 [0, n) 范围内下沉到合适位置 static void sift_down(std::vectorint data, int idx, int n) { while (true) { int largest idx; int left 2 * idx 1; int right 2 * idx 2; if (left n data[left] data[largest]) largest left; if (right n data[right] data[largest]) largest right; if (largest idx) break; std::swap(data[idx], data[largest]); idx largest; } } void heap_sort(std::vectorint data) { int n static_castint(data.size()); // 建堆从最后一个非叶子节点开始下滤 for (int i n / 2 - 1; i 0; --i) { sift_down(data, i, n); } // 依次把堆顶换到末尾再对剩余部分下滤 for (int i n - 1; i 0; --i) { std::swap(data[0], data[i]); sift_down(data, 0, i); } }sift_down里left 2 * idx 1、right 2 * idx 2是数组存堆的标准下标关系。建堆循环从n/2 - 1开始是因为下标大于等于n/2的节点都是叶子叶子本身满足堆性质不需要下滤。第二个循环每次把当前最大值换到i位置然后对[0, i)重新下滤最终得到升序数组。堆排序的时间复杂度稳定在 O(n log n)但常数比快速排序大缓存局部性也差一些这些在实测里都能看出来。2.5 归并排序的辅助数组与自底向上版本归并排序的递归版最好写但每次递归都分配临时数组会拖慢速度。常见优化是预先分配一个和原数组等大的辅助数组递归时只传下标范围合并时直接往辅助数组写再拷回来。// merge_sort.cpp #include sort_interface.h #include vector #include algorithm // 合并 [left, mid] 和 [mid1, right] static void merge(std::vectorint data, std::vectorint tmp, int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { // 稳定相等时取左边 tmp[k] (data[i] data[j]) ? data[i] : data[j]; } while (i mid) tmp[k] data[i]; while (j right) tmp[k] data[j]; // 拷回原数组 for (int p left; p right; p) { data[p] tmp[p]; } } static void merge_sort_impl(std::vectorint data, std::vectorint tmp, int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort_impl(data, tmp, left, mid); merge_sort_impl(data, tmp, mid 1, right); merge(data, tmp, left, mid, right); } void merge_sort(std::vectorint data) { std::vectorint tmp(data.size()); merge_sort_impl(data, tmp, 0, static_castint(data.size()) - 1); }mid left (right - left) / 2而不是(left right) / 2是为了避免left right溢出虽然int在常规数据规模下不容易溢出但这是值得养成的习惯。合并时data[i] data[j]取左边保证排序稳定。辅助数组tmp只在入口分配一次递归过程中复用这是归并排序能不能跑得快的关键。如果你需要非递归版本可以改成自底向上从步长 1 开始两两合并省掉递归调用开销。3. 把四种排序放进同一套基准测试计时、数据分布与结果解读3.1 计时框架怎么写才不背锅计时最容易翻车的地方是用clock()测真实时间它测的是 CPU 时间多线程或系统调度会干扰。C11 之后应该用std::chrono::steady_clock它单调递增不受系统时间调整影响。// benchmark.cpp #include sort_interface.h #include chrono #include iostream #include iomanip // 返回排序耗时单位毫秒 double time_sort(SortFunc func, std::vectorint data) { auto start std::chrono::steady_clock::now(); func(data); auto end std::chrono::steady_clock::now(); std::chrono::durationdouble, std::milli diff end - start; return diff.count(); } int main() { srand(42); // 固定种子保证可复现 std::vectorsize_t sizes {1000, 10000, 100000}; std::vectorstd::string dists {random, sorted, reversed, nearly}; std::cout std::left std::setw(12) dist std::setw(10) size std::setw(12) shell std::setw(12) quick std::setw(12) heap std::setw(12) merge \n; for (const auto dist : dists) { for (auto size : sizes) { auto base make_data(size, dist); std::cout std::left std::setw(12) dist std::setw(10) size; for (auto type : {SortType::Shell, SortType::Quick, SortType::Heap, SortType::Merge}) { auto copy base; // 每个算法用独立副本 double ms time_sort(get_sort_func(type), copy); std::cout std::setw(12) std::fixed std::setprecision(3) ms; } std::cout \n; } } return 0; }time_sort接收的是data的副本这样每个算法都在同样的原始数据上跑不会因为前一个算法排好了序而影响后一个。srand(42)固定种子保证你和我跑出来的数据分布一致结果可复现。输出用setw对齐方便直接贴到文档里对比。3.2 四种数据分布分别暴露什么问题make_data里要生成四种分布random完全随机sorted已经升序reversed完全逆序nearly近乎有序但有个别元素错位。这四种分布对应四种典型退化场景。// data_gen.cpp #include sort_interface.h #include algorithm #include random std::vectorint make_data(size_t size, const std::string dist) { std::vectorint data(size); std::mt19937 gen(42); std::uniform_int_distributionint dis(0, static_castint(size) * 10); if (dist random) { for (auto v : data) v dis(gen); } else if (dist sorted) { for (size_t i 0; i size; i) data[i] static_castint(i); } else if (dist reversed) { for (size_t i 0; i size; i) data[i] static_castint(size - i); } else if (dist nearly) { for (size_t i 0; i size; i) data[i] static_castint(i); // 随机交换 1% 的元素 std::mt19937 g(7); for (size_t k 0; k size / 100; k) { std::swap(data[g() % size], data[g() % size]); } } return data; }random用mt19937而不是rand()因为rand()在很多平台上周期短、低位随机性差。sorted和reversed直接构造用来观察快速排序在有序数据上的表现——如果你没做随机基准这里会看到明显的 O(n²) 退化。nearly交换 1% 的元素模拟现实中「基本有序但有小扰动」的场景希尔排序和插入类算法在这种数据上通常表现很好。3.3 结果表怎么读哪些差异是真实的跑完基准测试你会得到一张类似下面的表数值仅为示例实际以你机器为准分布规模希尔快速堆归并random10000018.212.521.714.1sorted1000003.111.820.913.5reversed1000004.712.121.313.8nearly1000002.411.620.513.2读这张表要注意几点。第一快速排序在sorted和reversed上没有崩到几百毫秒说明随机基准生效了如果你去掉随机基准这两行会直接爆炸。第二希尔排序在sorted和nearly上明显快因为 Knuth 序列在大 gap 阶段就完成了大部分移动接近有序时插入排序本身就很高效。第三堆排序在所有分布上都比较稳但常数偏大这是它的缓存不友好导致的。第四归并排序稳定在中间水平且它是唯一稳定的 O(n log n) 算法需要稳定性时优先选它。提示如果你在自己机器上跑出来的数值和这张表差很多先检查是不是开了编译器优化。-O2和-O0的差距可能比算法之间的差距还大。4. 编译、调试与性能验证从源码到可执行文件的完整链路4.1 用 CMake 组织多文件工程四个算法分在四个.cpp加上接口和测试文件数不少。手写g命令容易漏文件常见做法是用 CMake 管理。# CMakeLists.txt cmake_minimum_required(VERSION 3.10) project(sort_benchmark CXX) set(CMAKE_CXX_STANDARD 11) set(CMAKE_CXX_STANDARD_REQUIRED ON) # 开启优化否则计时没有意义 set(CMAKE_CXX_FLAGS_RELEASE -O2) add_executable(benchmark benchmark.cpp data_gen.cpp sort_interface.cpp shell_sort.cpp quick_sort.cpp heap_sort.cpp merge_sort.cpp )CMAKE_CXX_STANDARD 11是底线std::chrono和enum class都需要 C11。-O2必须开否则你测的是未优化代码算法之间的相对关系会失真。add_executable里把所有源文件列全漏一个就是链接错误。4.2 编译命令与常见报错如果你不想用 CMake直接命令行编译也可以g -stdc11 -O2 -o benchmark \ benchmark.cpp data_gen.cpp sort_interface.cpp \ shell_sort.cpp quick_sort.cpp heap_sort.cpp merge_sort.cpp常见报错有三种。第一种是undefined reference to get_sort_func说明sort_interface.cpp没参与编译或者函数声明了但没实现。第二种是rand was not declared漏了#include cstdlib。第三种是chrono is not a member of std说明编译器没开 C11检查-stdc11是否写对。在 VS Code 里配置 C/C 环境时tasks.json的args里也要带上-stdc11 -O2否则你在编辑器里跑出来的结果和命令行不一致。4.3 用断言验证排序正确性性能对比之前必须先保证四个算法都排对了。常见做法是在计时之外加一轮小规模断言测试用std::is_sorted检查结果。// verify.cpp #include sort_interface.h #include algorithm #include cassert #include iostream void verify_all() { for (auto type : {SortType::Shell, SortType::Quick, SortType::Heap, SortType::Merge}) { for (size_t size : {0, 1, 2, 10, 1000}) { auto data make_data(size, random); get_sort_func(type)(data); assert(std::is_sorted(data.begin(), data.end())); } std::cout sort type static_castint(type) passed\n; } }size取 0 和 1 是边界测试很多排序实现在空数组或单元素数组上会越界。std::is_sorted是标准库提供的检查比自己写循环可靠。断言在-O2下默认不会被去掉除非你定义了NDEBUG所以发布版里也能保留这层保护。5. 避坑与排查四种排序最容易翻车的五个地方5.1 快速排序在有序数据上退化成 O(n²)现象sorted和reversed分布下快速排序耗时突然比random高一个数量级。原因基准固定取第一个或最后一个元素有序数据下每次划分都极不平衡。解决改成随机基准或三数取中代码里pivot_idx left rand() % (right - left 1)就是干这个的。如果还不行加深度限制超过2 * log2(n)就切堆排序。5.2 归并排序临时数组反复分配拖慢速度现象归并排序比预期慢很多甚至接近堆排序。原因递归里每次merge都new一个临时数组分配和释放开销累积。解决在入口分配一次tmp递归时传引用合并完直接拷回。这个改动通常能让归并排序快 30% 以上。5.3 堆排序建堆从错误位置开始现象排序结果部分有序但整体不对或者小数据量下偶尔正确、大数据量下出错。原因建堆循环从0开始往上调整或者从n/2开始但下标算错。解决从n/2 - 1开始往前下滤n/2及之后的节点都是叶子不需要处理。检查left 2 * idx 1是否越界。5.4 希尔排序增量序列写成gap / 2后性能不达标现象逆序数据上希尔排序比归并还慢。原因折半序列的最坏时间复杂度是 O(n²)在特定数据上会触发。解决换成 Knuth 序列gap gap * 3 1生成、gap (gap - 1) / 3收缩。如果还想要更好可以查 Hibbard 序列或 Sedgewick 序列但 Knuth 已经能覆盖大多数场景。5.5 计时把数据拷贝时间算进去现象所有算法耗时都比预期高且差距被压缩。原因time_sort里如果传值而不是传引用拷贝大数组的时间会算进排序耗时。解决计时函数接收std::vectorint data是按值传递但调用方传的是副本拷贝发生在计时开始之前。如果你在计时内部才拷贝那就把拷贝移到steady_clock::now()之前。这个坑很隐蔽因为拷贝时间在 10 万级数据上可能有几毫秒足以掩盖算法差异。6. 进阶技巧用内省排序和稳定性验证把对比做扎实把四种排序跑通只是起点。真正让这份代码有工程价值的是两个进阶动作一是给快速排序加内省机制二是验证归并排序的稳定性。内省排序的思路是快速排序递归时记录深度超过2 * floor(log2(n))就切换到堆排序。这样既保留快速排序在平均情况下的低常数又避免最坏情况下的 O(n²)。实现上只需要在quick_sort_impl里加一个depth参数递归时depth 1超过阈值就调heap_sort的区间版本。这个改动不大但能让快速排序在对抗性数据上也有稳定表现。// 内省排序的深度判断片段 static void intro_sort_impl(std::vectorint data, int left, int right, int depth) { if (left right) return; if (depth 0) { // 深度用尽切换堆排序处理当前区间 heap_sort_range(data, left, right); return; } // ... 正常三路划分 ... intro_sort_impl(data, left, lt - 1, depth - 1); intro_sort_impl(data, gt 1, right, depth - 1); }heap_sort_range需要你把堆排序改造成支持区间版本建堆和下滤都只在[left, right]内进行。深度阈值一般取2 * log2(right - left 1)这个值在实践里比较平衡。稳定性验证则是另一个维度。归并排序是稳定的快速排序和堆排序不稳定希尔排序不稳定。验证方法很简单给数据加上原始下标排序后检查相等元素的相对顺序是否保持。// 稳定性验证用 pairvalue, index 排序 struct Item { int value; int index; }; // 对 Item 排序时只比较 value排序后检查相同 value 的 index 是否递增如果你把四种排序都套上这个Item结构会发现只有归并排序能保持index递增。这个验证能帮你确认自己对稳定性的理解没有偏差也能在选型时给出明确依据需要稳定就选归并不需要稳定且追求平均性能就选快速。从那以后我每次做排序对比都强制走一遍「小规模断言 → 四种分布基准 → 稳定性验证」这三步缺一步都不敢下结论。希望帮到你。本文还有配套的精品资源点击获取