C++四大经典排序算法：希尔、快排、堆排、归并的手写实现与性能对比

简介排序算法是计算机科学的基础它通过比较和交换元素来组织数据其核心原理在于减少逆序对以提高访问效率。从时间复杂度、空间复杂度和稳定性等维度评估不同算法各有优劣这直接决定了它们在工程实践中的技术价值。例如快速排序的平均性能优异但存在退化风险而归并排序稳定可靠但需要额外空间。在实际应用场景中算法选择需综合考虑数据规模、内存限制和稳定性要求。本文以C为例深入探讨希尔排序、快速排序、堆排序和归并排序的实现细节并分析其性能表现其中快速排序的分治思想和堆排序的树形结构应用是理解更复杂算法的关键。1. 从排序算法的“鄙视链”谈起为什么还要手写它们如果你是一个C开发者尤其是经历过面试的看到“希尔、快速、堆、归并”这几个排序算法的名字大概率会心一笑或者眉头一皱。在STL的std::sort大行其道的今天为什么我们还要去手写这些“古老”的算法直接用#include algorithm然后std::sort(v.begin(), v.end())不香吗这个问题问得好。直接使用std::sort对于99%的日常场景不仅香而且是绝对的最佳实践。它经过千锤百炼针对不同数据规模和类型做了大量优化例如对于小数组使用插入排序对于大数组使用内省排序——一种混合了快速排序、堆排序和插入排序的算法其性能和稳定性远超绝大多数开发者自己手写的版本。那么手写的意义何在在我看来这绝非为了“炫技”或应付考试。其核心价值在于理解。理解这些经典算法就像理解汽车的发动机原理即使你一辈子都用自动驾驶懂原理也能让你在车出问题时不至于只能打电话叫拖车。具体来说构建算法思维骨架排序是算法世界的“ Hello World ”。快速排序的分治思想、堆排序的树形结构应用、归并排序的稳定合并这些是理解更复杂算法如动态规划、图算法的基石。亲手实现一遍是对这些抽象思想最扎实的具象化训练。洞察性能边界与取舍只有自己实现你才会真切感受到快速排序在近乎有序数据下的糟糕表现退化为O(n²)才会明白为什么std::sort要引入堆排序作为递归深度的“保险丝”也才会理解归并排序那额外的O(n)空间开销在内存敏感场景下的代价。这种对算法“脾气”的熟悉是进行系统级性能调优和选型的前提。应对特殊定制需求std::sort是通用的但业务是千奇百怪的。当你需要对一个自定义的复杂结构体按某个特定规则排序或者需要一种非标准的比较逻辑时理解底层算法能帮助你更好地设计比较函数甚至启发你修改算法本身来适应需求例如实现一个针对链表优化的归并排序。破解面试与 legacy code毋庸讳言手写排序是面试高频题。更重要的是在维护一些历史代码库时你可能会遇到没有使用STL或者为了极致的性能、特定的内存管理而自定义实现的排序算法。此时读懂它、调试它、优化它都需要这份基本功。所以今天我们就抛开std::sort这根“拐杖”回归本源用C重新实现这四种经典排序算法。我们的目标不是写出比STL更快的代码而是写出清晰、正确、并能体现算法精髓的代码。我会在实现中穿插大量“为什么这么做”的思考以及我在实际编码和调试中踩过的坑希望能给你带来比教科书更接地气的理解。2. 希尔排序插入排序的“超级赛亚人”形态让我们先从相对“冷门”但思想巧妙的希尔排序开始。很多人觉得它不如快排、归并出名但它的设计哲学非常值得玩味——如何让一个简单算法获得质的飞跃希尔排序的本质是分组插入排序。它是对直接插入排序的威力加强版。直接插入排序在处理小规模或基本有序的数据时效率很高因为它的内循环在数据有序时近乎是O(1)的。但当数据大规模且无序时它需要将元素一位一位地向前移动效率低下时间复杂度为O(n²)。希尔排序的聪明之处在于它不急于一下子完成排序而是先进行宏观调整。它引入了一个“增量序列”gap sequence的概念。算法会先以一个大步长比如数组长度的一半对数组进行分组并对每组进行插入排序。这样元素可以一次移动很远的位置快速消除那些距离其最终位置很远的“逆序对”。然后逐步缩小步长重复分组和排序。当步长缩小到1时整个数组已经“基本有序”了此时再做一次标准的插入排序就能以很小的代价完成最终排序。2.1 增量序列的选择算法的“发动机调校”希尔排序的性能高度依赖于增量序列的选择。糟糕的序列可能让性能退化到O(n²)好的序列则能逼近O(n log² n)甚至更好。这里我们实现最经典、也最容易理解的希尔增量序列Shell‘s original sequence初始步长为n/2之后每次减半直到1。void shellSort(vectorint arr) { int n arr.size(); // 使用希尔增量序列gap n/2, n/4, ..., 1 for (int gap n / 2; gap 0; gap / 2) { // 从第gap个元素开始对其所在组进行插入排序 for (int i gap; i n; i) { int temp arr[i]; // 待插入的元素 int j; // 对以gap为步长的子序列进行插入排序 for (j i; j gap arr[j - gap] temp; j - gap) { arr[j] arr[j - gap]; // 将较大的元素向后移动gap位 } arr[j] temp; // 插入正确位置 } } }为什么内层循环的条件是j gap这是边界保护。当j减去gap后必须确保索引仍然有效0。因为我们是按组进行插入排序组内的第一个元素索引是i % gap但用j gap来判断更简洁通用它保证了我们在比较和移动时不会越界访问arr[j-gap]。一个常见的“坑”错误理解分组。初学者常误以为希尔排序是先显式地把数组分成gap组然后分别对每组排序。实际上上面的代码展示的是更高效的做法对每个从gap到n-1的元素arr[i]它都属于以i % gap为起点的那个子序列。外层i循环遍历所有元素内层j循环沿着该元素所在的子序列步长为gap向前做插入排序。这种实现将分组逻辑隐含在了移动步长gap中代码更紧凑缓存局部性也更好。实操心得希尔排序的适用场景。希尔排序的代码不长但效率在中等规模数据上常常有惊喜。它是不稳定排序空间复杂度O(1)。虽然其理论时间复杂度不如O(n log n)的算法但由于它几乎不需要额外的内存访问除了一个临时变量temp在数据量不大比如几千到几万、且对内存占用非常敏感嵌入式环境的场景下它可能是一个朴实无华且高效的选择。它的性能很大程度上依赖于增量序列除了希尔增量还有Hibbard序列、Sedgewick序列等更优的选择有兴趣可以深入研究。3. 快速排序优雅与风险并存的“分治之王”快速排序是面试中的绝对明星也是std::sort的基石之一。它的思想极其优雅选择一个基准pivot将数组分成两部分左边都小于等于基准右边都大于等于基准然后递归地对左右两部分进行同样的操作。3.1 核心分区Partition的艺术快速排序的所有魔力都蕴藏在分区操作中。一个健壮、高效的分区实现是快排的灵魂。这里我们实现经典的Lomuto分区方案它逻辑清晰易于理解和实现。// Lomuto分区函数返回基准值的最终位置 int partition(vectorint arr, int low, int high) { int pivot arr[high]; // 选择最后一个元素作为基准 int i low - 1; // i指向小于pivot区域的最后一个位置 for (int j low; j high; j) { // 如果当前元素小于等于基准 if (arr[j] pivot) { i; // 扩大小于pivot的区域 swap(arr[i], arr[j]); // 将当前元素交换到该区域 } } // 将基准元素交换到正确位置i1 swap(arr[i 1], arr[high]); return i 1; // 返回基准的索引 } void quickSort(vectorint arr, int low, int high) { if (low high) { // pi是分区后基准元素的正确位置 int pi partition(arr, low, high); // 递归排序基准左右两边的子数组 quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } } // 对外提供的接口 void quickSort(vectorint arr) { if (!arr.empty()) { quickSort(arr, 0, arr.size() - 1); } }为什么选择arr[high]作为pivot简单但不是最优。选择第一个或最后一个元素作为基准在数组已经有序或逆序时会导致分区极度不平衡一边没有元素另一边有n-1个元素从而使递归树退化成链表时间复杂度恶化为O(n²)。这是快速排序最著名的“阿喀琉斯之踵”。如何规避最坏情况——“随机化”与“三数取中”。工业级的实现绝不会固定选择头或尾。常用策略有随机选择基准在[low, high]区间随机选一个索引与arr[high]交换再执行上述分区。这能将最坏情况的发生概率降到极低。三数取中法取arr[low]、arr[mid]、arr[high]的中位数作为基准。这能有效避免在已部分有序的数据上出现糟糕的分区。我们可以轻松修改partition函数来加入随机化int partitionRandom(vectorint arr, int low, int high) { // 生成一个[low, high]范围内的随机索引 int randomIndex low rand() % (high - low 1); swap(arr[randomIndex], arr[high]); // 将随机选中的元素交换到末尾 // 之后沿用原来的Lomuto分区逻辑 return partition(arr, low, high); // 调用上面标准的partition函数 }在quickSort递归函数中调用partitionRandom即可。记住在程序开始时用srand(time(nullptr))初始化随机种子。Lomuto分区的优缺点优点逻辑非常直白代码简洁容易写对。缺点当数组中存在大量与基准值相等的元素时Lomuto分区仍会进行不必要的交换且不能将相等的元素均匀分到两侧。对于这种情况Hoare分区使用两个指针从两端向中间扫描通常是更好的选择但它理解起来稍复杂边界条件也更容易出错。一个致命的细节递归深度与栈溢出。即使进行了随机化在极端情况下比如运气极差或者针对该算法的恶意数据递归深度仍可能达到O(n)。对于大型数组这可能导致栈溢出。std::sort采用的内省排序Introsort监控递归深度当深度超过2 * log(n)时会自动切换到堆排序从而将最坏时间复杂度保证在O(n log n)。在我们自己的实现中如果用于生产环境也必须考虑这个“安全阀”机制。4. 堆排序利用“树结构”的原地排序堆排序是一种非常聪明的原地、不稳定的比较排序算法时间复杂度稳定在O(n log n)。它不需要额外的存储空间除了几个临时变量也不存在快速排序那样的最坏情况退化问题。它的思想是将待排序数组构造成一个最大堆或最小堆然后反复将堆顶元素最大值与堆末尾元素交换并重建堆直到堆的大小为1。4.1 理解“堆”与数组的映射堆是一种特殊的完全二叉树。我们通常用数组来隐式地表示它。对于一个索引为i的节点从0开始它的父节点索引是(i - 1) / 2它的左孩子索引是2 * i 1它的右孩子索引是2 * i 2堆排序分为两个主要阶段建堆Heapify将无序数组调整成一个最大堆。排序将堆顶元素最大值与当前堆的最后一个元素交换堆的大小减1然后对新的堆顶元素执行“下沉Sift Down”操作以恢复最大堆性质。重复此过程。// 下沉操作确保以节点i为根的子树满足最大堆性质 void heapify(vectorint arr, int n, int i) { 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) { swap(arr[i], arr[largest]); // 交换 // 递归地调整被破坏的子堆 heapify(arr, n, largest); } } void heapSort(vectorint arr) { int n arr.size(); // 1. 构建最大堆从最后一个非叶子节点开始 // 最后一个非叶子节点的索引是 n/2 - 1 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 2. 一个个从堆顶取出元素 for (int i n - 1; i 0; i--) { // 将当前堆顶最大值移动到数组末尾 swap(arr[0], arr[i]); // 在缩小的堆大小为i上恢复最大堆性质 heapify(arr, i, 0); } }为什么建堆要从n/2 - 1开始因为叶子节点没有子节点的节点本身可以看作是一个合法的堆。最后一个非叶子节点是最后一个拥有至少一个孩子的节点索引为n/2 - 1整数除法。从它开始向前遍历对每个节点调用heapify可以确保当我们处理到某个节点时它的左右子树都已经是最大堆这样heapify操作才能正确工作。这是一种“自底向上”的建堆方式时间复杂度是O(n)比一个个插入O(n log n)要高效。heapify的递归与迭代。上面的heapify使用了递归清晰易懂。但在生产代码中为了极致性能和避免递归栈开销通常会写成迭代形式void heapifyIterative(vectorint arr, int n, int i) { int current i; while (true) { int largest current; int left 2 * current 1; int right 2 * current 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest current) break; // 当前节点已满足堆性质 swap(arr[current], arr[largest]); current largest; // 继续向下调整 } }堆排序的“尴尬”与优势。堆排序的O(n log n)很稳定且是原地排序这是它的优点。但它也有明显的缺点缓存不友好堆排序对数组的访问是跳跃式的访问父节点、左孩子、右孩子这破坏了程序的局部性原理导致缓存命中率低。在实际运行中它的常数因子往往比快速排序和归并排序大。不稳定在交换和下沉过程中相等元素的相对位置可能改变。因此堆排序很少作为通用排序的首选。但它有两个不可替代的用途一是作为快速排序的“安全网”如内省排序二是用于实现优先级队列。我们熟悉的Cstd::priority_queue底层就是用堆实现的。理解堆排序是理解优先级队列这一重要数据结构的基础。5. 归并排序稳定、可靠的分治典范归并排序是分治思想的另一个完美体现。它采用一种“先分后治”的策略将数组递归地分成两半分别排序然后将两个已排序的子数组合并成一个大的有序数组。它是稳定排序时间复杂度稳定为O(n log n)但需要O(n)的额外空间。5.1 核心合并两个有序数组归并排序的难点和精髓都在于“合并Merge”步骤。给定两个已经有序的子数组arr[left...mid]和arr[mid1...right]如何高效地将它们合并到一个临时数组中再拷贝回原数组// 合并两个有序子数组 arr[left..mid] 和 arr[mid1..right] void merge(vectorint arr, int left, int mid, int right) { int n1 mid - left 1; // 左子数组的大小 int n2 right - mid; // 右子数组的大小 // 创建临时数组 vectorint L(n1), R(n2); // 拷贝数据到临时数组 for (int i 0; i n1; i) L[i] arr[left i]; for (int j 0; j n2; j) R[j] arr[mid 1 j]; // 合并临时数组回 arr[left..right] int i 0; // 初始化左子数组的索引 int j 0; // 初始化右子数组的索引 int k left; // 初始化合并子数组的索引 while (i n1 j n2) { if (L[i] R[j]) { // 注意这里用 保证了稳定性 arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } // 拷贝左子数组剩余的元素如果有 while (i n1) { arr[k] L[i]; i; k; } // 拷贝右子数组剩余的元素如果有 while (j n2) { arr[k] R[j]; j; k; } // 临时数组 L 和 R 会在函数结束时被自动销毁 } void mergeSort(vectorint arr, int left, int right) { if (left right) { return; // 递归基子数组只有一个元素或为空 } int mid left (right - left) / 2; // 防止溢出等同于 (leftright)/2 mergeSort(arr, left, mid); // 排序左半部分 mergeSort(arr, mid 1, right); // 排序右半部分 merge(arr, left, mid, right); // 合并已排序的两部分 } void mergeSort(vectorint arr) { if (!arr.empty()) { mergeSort(arr, 0, arr.size() - 1); } }为什么mid left (right - left) / 2这是一个经典的防溢出技巧。在C/C中(left right) / 2在left和right都很大时left right可能会超过int类型的最大值导致溢出。而left (right - left) / 2在数学上等价但避免了先加后除的溢出风险。归并排序的稳定性秘密。注意merge函数中的比较if (L[i] R[j])。这里使用小于等于而非小于是关键所在。当L[i]等于R[j]时我们优先将L[i]来自左子数组放入原数组。由于左子数组的元素在原数组中本就位于右子数组元素之前这个操作保证了相等元素的原始相对顺序不变从而实现了稳定排序。这是归并排序一个非常重要的特性在需要稳定性的场景如先按成绩排序再按姓名排序下是首选。空间复杂度之殇与优化。O(n)的额外空间是归并排序的主要缺点。每次合并都需要临时数组。一个常见的优化是在排序开始时只分配一个与原数组等大的临时数组然后在整个递归过程中重复使用它而不是在每个merge调用中都创建新的临时数组。这可以将空间复杂度从每次递归调用的O(n log n)栈空间堆空间降低到确定的O(n)堆空间。void mergeSortOptimized(vectorint arr) { if (arr.empty()) return; vectorint temp(arr.size()); // 一次性分配临时空间 mergeSortHelper(arr, temp, 0, arr.size() - 1); } void mergeSortHelper(vectorint arr, vectorint temp, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSortHelper(arr, temp, left, mid); mergeSortHelper(arr, temp, mid 1, right); mergeWithTemp(arr, temp, left, mid, right); // 使用共用的temp数组 } void mergeWithTemp(vectorint arr, vectorint temp, int left, int mid, int right) { // ... 合并逻辑类似但将数据拷贝到temp的对应区间再合并回arr // 具体实现需小心处理temp数组的索引 }归并排序的用武之地。由于其稳定性和可靠的最坏O(n log n)复杂度归并排序是外部排序数据量太大无法全部装入内存的核心算法。它也常用于对链表进行排序因为链表不像数组那样需要连续空间归并排序的合并步骤在链表上可以只用O(1)的额外空间修改指针即可这使得它对链表排序非常高效。6. 实战对比与选型思考纸上得来终觉浅理论分析固然重要但“是骡子是马拉出来遛遛”。我们写一个简单的测试程序在相同的数据集上对比这四种算法的实际表现。这里我们测试两个场景大规模随机数据和小规模基本有序数据。#include iostream #include vector #include cstdlib #include ctime #include chrono #include algorithm using namespace std; using namespace std::chrono; // ... (这里插入上面四个排序算法的实现代码) vectorint generateRandomArray(int n) { vectorint arr(n); srand(time(nullptr)); for (int i 0; i n; i) { arr[i] rand() % 10000; // 生成0-9999的随机数 } return arr; } vectorint generateNearlySortedArray(int n) { vectorint arr(n); for (int i 0; i n; i) { arr[i] i; } // 随机交换少量元素制造基本有序 srand(time(nullptr)); for (int i 0; i n / 100; i) { // 交换约1%的元素 int a rand() % n; int b rand() % n; swap(arr[a], arr[b]); } return arr; } templatetypename Func void testSort(const string name, Func sortFunc, vectorint arr) { auto start high_resolution_clock::now(); sortFunc(arr); auto stop high_resolution_clock::now(); auto duration duration_castmicroseconds(stop - start); // 简单验证排序正确性可选对于大数组可能耗时 // for (size_t i 1; i arr.size(); i) { // if (arr[i-1] arr[i]) { cout Sort Error! endl; break;} // } cout name 用时: duration.count() 微秒 endl; } int main() { const int N 10000; // 测试数据量 cout 测试 N 个随机整数 endl; auto randomArr generateRandomArray(N); auto arr1 randomArr; auto arr2 randomArr; auto arr3 randomArr; auto arr4 randomArr; testSort(希尔排序, shellSort, arr1); testSort(快速排序, quickSort, arr2); testSort(堆排序 , heapSort, arr3); testSort(归并排序, mergeSort, arr4); cout \n 测试 N 个基本有序整数 endl; auto nearlySortedArr generateNearlySortedArray(N); arr1 nearlySortedArr; arr2 nearlySortedArr; arr3 nearlySortedArr; arr4 nearlySortedArr; testSort(希尔排序, shellSort, arr1); testSort(快速排序, quickSort, arr2); // 注意这里使用的是未随机化的快排性能会下降 testSort(堆排序 , heapSort, arr3); testSort(归并排序, mergeSort, arr4); return 0; }在我的环境Release模式编译下运行结果趋势大致如下具体时间因机器而异随机数据快速排序通常最快归并排序和堆排序次之且接近希尔排序最慢但差距可能不像O(n²) vs O(n log n)理论值那么大因为数据量不算巨大。基本有序数据未经优化的快速排序选择固定基准性能会急剧下降甚至可能比希尔排序还慢因为它每次都产生极度不平衡的分区。而归并排序和堆排序的时间保持稳定。希尔排序由于数据已基本有序其最后的插入排序阶段非常快表现可能不错。这个简单的测试印证了几个关键点快速排序在平均情况下很快但对输入数据敏感。务必使用随机化或三数取中来选择基准这是工程实现中的必须步骤。堆排序和归并排序性能稳定不受输入数据分布影响。希尔排序作为改进的插入排序在小规模或部分有序数据上可能有其优势且实现简单。那么到底该用哪个通用场景毫不犹豫地用std::sort。它是C标准库的精华集各家之长快速排序堆排序防退化插入排序优化小数组。需要稳定排序使用std::stable_sort它通常基于归并排序实现。内存极度受限考虑希尔排序或堆排序原地。对链表排序归并排序是天然的选择。自己实现作为学习理解它们的思想和实现细节比记住结论更重要。手写这些算法就像武术家练习基本功。std::sort是你的趁手兵器但深厚的“内功”对算法的理解能让你在面对任何复杂问题时都知道该挥舞哪件兵器甚至如何改造它。希望这篇长文能帮你把这四种经典排序的“筋骨”摸得更清楚一些。在实际编码中多思考边界条件空数组、单个元素、已排序数组多测试不同规模和数据分布你会对它们有更深刻的、属于自己的体会。本文还有配套的精品资源点击获取