1. 为什么我要把内部排序重新梳理一遍做C开发这些年排序算法这东西就像空气——平时感觉不到它的存在一旦出问题就是大问题。我见过太多项目里有人随手写个std::sort就完事结果在特定数据规模下性能直接崩掉也见过面试时能把快排背得滚瓜烂熟但问他为什么小数组要切换插入排序就卡壳的候选人。所以这次我决定把内部排序算法从头到尾捋一遍用C实现把每个算法的脾气秉性都摸清楚。所谓内部排序指的是待排序数据全部放在内存中进行的排序过程。与之对应的是外部排序那是数据量大到内存装不下、需要借助磁盘的场景。内部排序是每个C程序员的基本功也是理解算法设计思想的绝佳入口。你可能会问STL里已经有std::sort了为什么还要自己实现我的回答是理解底层才能用好上层。当你知道了std::sort内部是内省排序Introsort——快排堆排插入排序的混合体你才能判断什么场景下它可能不是最优解。这篇文章适合两类人一是正在准备技术面试、需要系统梳理排序算法的同学二是在实际项目中遇到过排序性能问题、想搞清楚背后原理的开发者。我会用C逐一实现插入排序、希尔排序、冒泡排序、快速排序、选择排序和堆排序每个算法都会给出完整代码、复杂度分析以及我在实际测试中发现的那些文档里不会写的细节。文章分上下两篇上篇聚焦基础排序算法下篇会深入归并排序、计数排序、基数排序等更进阶的内容。先说清楚我的测试环境编译器用GCC 13.2标准是C20优化级别-O2测试机器是一台普通的x86笔记本。所有性能数据都是实测值不是从教科书上抄的。这一点很重要因为很多教材上的复杂度分析是理论值实际跑起来可能因为缓存命中率、分支预测等因素产生巨大差异。2. 插入排序小规模数据下的隐形冠军2.1 从打扑克牌说起插入排序的思想特别朴素就是你打扑克牌时整理手牌的方式。左手是已经排好序的牌右手每次摸一张新牌从右往左比较找到合适的位置插进去。这个类比虽然老套但它精准地抓住了插入排序的核心维护一个有序区间逐个将新元素插入到正确位置。用C实现的话最基础的版本长这样templatetypename T void insertionSort(T arr[], int n) { for (int i 1; i n; i) { T key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; --j; } arr[j 1] key; } }这段代码看起来简单但有几个细节值得注意。首先key变量保存了当前待插入的元素这是必须的因为后续的移动操作会覆盖arr[i]的位置。其次循环条件是arr[j] key而不是这保证了排序的稳定性——相等元素的相对顺序不会改变。稳定性在实际开发中很重要比如你先按姓名排序再按年龄排序如果年龄排序是稳定的那么同年龄的人仍然保持姓名的有序性。2.2 为什么插入排序在工程中如此重要很多人觉得插入排序是O(n²)的算法太慢了不值得关注。但我在实际测试中发现了一个反直觉的现象当数据规模小于32时插入排序比快速排序还快。这不是我瞎说你可以自己写个benchmark验证。原因有三第一插入排序的常数因子极小。它的内层循环只有一次比较和一次赋值没有递归调用开销没有函数栈帧的创建和销毁。而快速排序即使经过优化递归调用的开销在小数组上也不可忽略。第二插入排序对近乎有序的数据极其高效。如果数据已经基本有序插入排序的时间复杂度退化到O(n)。这个特性在实际场景中非常有用比如日志按时间戳排序新来的日志通常时间戳更大只需要插入到末尾附近。第三插入排序是原地排序空间复杂度O(1)不需要额外的内存分配。在嵌入式或内存受限的环境中这个优势很关键。我在一个数据处理项目中就吃过亏。当时需要对一个包含约50个元素的配置项数组排序我图省事直接调了std::sort。后来profile发现这个排序调用居然占了整个初始化流程15%的时间。换成手写的插入排序后耗时直接降了一个数量级。从那以后我就养成了一个习惯小数组排序优先考虑插入排序。2.3 二分插入排序优化比较次数普通插入排序在寻找插入位置时是线性扫描比较次数是O(n)。既然有序区间已经排好了为什么不用二分查找呢这就是二分插入排序的思路templatetypename T void binaryInsertionSort(T arr[], int n) { for (int i 1; i n; i) { T key arr[i]; int left 0, right i; while (left right) { int mid left (right - left) / 2; if (arr[mid] key) left mid 1; else right mid; } for (int j i; j left; --j) arr[j] arr[j - 1]; arr[left] key; } }二分插入排序把比较次数从O(n²)降到了O(n log n)但移动次数仍然是O(n²)。所以它的整体时间复杂度还是O(n²)只是在比较操作特别昂贵的场景下比如比较的是长字符串才有明显优势。这里有个坑二分查找的边界条件很容易写错。我建议用left right作为循环条件最后left就是插入位置。注意arr[mid] key中的是为了保持稳定性。注意二分插入排序虽然减少了比较但增加了代码复杂度。除非比较操作确实很耗时否则普通插入排序的简洁性更值得推荐。3. 希尔排序插入排序的进化形态3.1 增量序列的选择决定成败希尔排序是插入排序的改进版核心思想是先让数组变得基本有序最后再做一次插入排序。它通过一个递减的增量序列对相隔某个增量的元素进行插入排序。当增量为1时就是普通的插入排序但此时数组已经基本有序插入排序的效率极高。templatetypename T void shellSort(T arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { T key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } } }上面用的是最简单的希尔增量n/2, n/4, ..., 1但它的最坏时间复杂度是O(n²)。更好的选择是Knuth增量1, 4, 13, 40, ...即gap 3*gap 1最坏时间复杂度O(n^1.5)。还有Sedgewick增量能进一步优化到O(n^(4/3))。我在实测中对比过这几种增量序列在10万随机整数上希尔增量平均耗时约18msKnuth增量约12msSedgewick增量约9ms。差距还是很明显的。但要注意增量序列的选择和具体数据分布有关没有绝对的最优解。3.2 希尔排序的稳定性问题希尔排序是不稳定的排序算法。原因很简单相同的元素可能被分到不同的增量组里跨组移动时相对顺序可能改变。举个例子数组[2a, 2b, 1]gap2时2a和1比较交换变成[1, 2b, 2a]2a和2b的相对顺序就反了。如果你需要稳定性希尔排序就不合适。但如果你只关心速度希尔排序在中等规模数据几千到几万上表现相当不错代码也比快速排序简单得多。我个人的经验是数据量在1万以内、对稳定性没要求时希尔排序是性价比很高的选择。3.3 实测中的意外发现有个现象让我挺意外的在近乎有序的数据上希尔排序反而不如普通插入排序快。原因是希尔排序的前几轮增量排序会打乱原有的有序性虽然后续会恢复但额外的移动操作带来了开销。所以如果你的数据已经基本有序直接用插入排序就好别画蛇添足上希尔排序。另外希尔排序的性能对增量序列非常敏感。我曾经在一个项目里用了错误的增量序列gap每次减1而不是除以2结果在5万条数据上跑了整整3秒换成Knuth增量后降到15ms。这个教训告诉我用希尔排序一定要选经过验证的增量序列别自己拍脑袋发明。4. 冒泡排序被低估的教学工具4.1 基础实现与优化版本冒泡排序可能是所有人学编程时接触的第一个排序算法。它的原理是重复遍历数组比较相邻元素如果顺序错误就交换。每一轮遍历后最大的元素会冒泡到末尾。templatetypename T void bubbleSort(T arr[], int n) { for (int i 0; i n - 1; i) { bool swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); swapped true; } } if (!swapped) break; } }这个版本加了swapped标志如果某一轮没有发生任何交换说明数组已经有序可以提前退出。这个优化在近乎有序的数据上效果显著最好情况时间复杂度从O(n²)降到O(n)。还有一个优化思路是记录最后一次交换的位置因为该位置之后的元素已经有序下一轮只需要遍历到这个位置即可。这个优化在特定数据分布下能减少不少比较次数。4.2 冒泡排序真的没用吗网上很多文章把冒泡排序批得一文不值说它效率低、没人用。但我不完全同意。冒泡排序的价值在于教学和特定场景。从教学角度冒泡排序是理解交换排序思想的最佳入口。它的执行过程可视化程度高适合用来讲解算法复杂度和优化思路。我教新人时总是从冒泡排序开始然后一步步引导他们思考能不能减少比较次数能不能减少交换次数能不能一次移动多个位置这样自然就过渡到了快速排序。从实用角度冒泡排序在链表排序中有独特优势。因为链表不支持随机访问很多排序算法在链表上效率很低但冒泡排序只需要交换相邻节点实现起来很自然。当然链表排序有更好的选择比如归并排序但冒泡排序的链表版本确实是最容易写对的。提示如果你在面试中被要求手写冒泡排序记得加上swapped优化。这能体现你有优化意识而不是死记硬背。5. 快速排序分治思想的极致演绎5.1 霍尔分区与洛穆托分区快速排序是内部排序中平均性能最好的算法平均时间复杂度O(n log n)常数因子小原地排序。它的核心是分区操作选一个基准元素把数组分成两部分左边都不大于基准右边都不小于基准然后递归处理两部分。最经典的分区方案是霍尔分区Hoare Partition用两个指针从两端向中间扫描templatetypename T int hoarePartition(T arr[], int low, int high) { T pivot arr[low (high - low) / 2]; int i low - 1, j high 1; while (true) { do { i; } while (arr[i] pivot); do { --j; } while (arr[j] pivot); if (i j) return j; std::swap(arr[i], arr[j]); } } templatetypename T void quickSortHoare(T arr[], int low, int high) { if (low high) { int p hoarePartition(arr, low, high); quickSortHoare(arr, low, p); quickSortHoare(arr, p 1, high); } }霍尔分区的优点是交换次数少平均比洛穆托分区少三倍左右。但它的边界条件比较绕容易写错。注意pivot选的是中间元素而不是第一个元素这是为了避免在已排序数组上退化。洛穆托分区Lomuto Partition更直观用单指针维护小于基准的区域templatetypename T int lomutoPartition(T arr[], int low, int high) { T pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; std::swap(arr[i], arr[j]); } } std::swap(arr[i 1], arr[high]); return i 1; }洛穆托分区代码简单但交换次数多而且在有大量重复元素时性能很差。我一般推荐霍尔分区除非是教学场景。5.2 基准选择的艺术快速排序的性能极度依赖基准的选择。最坏情况是每次选到最大或最小元素递归深度变成n时间复杂度退化到O(n²)。为了避免这种情况有几种常见的基准选择策略随机选择每次随机选一个元素作为基准期望时间复杂度O(n log n)。实现简单效果稳定。三数取中取首、中、尾三个元素的中位数作为基准。能有效避免在已排序数据上退化。九数取中取九个位置的中位数更稳健但开销稍大。我在实测中发现对于随机数据随机选择和三数取中差别不大但对于已排序或近乎有序的数据三数取中明显更优。对于包含大量重复元素的数据三路分区Dutch National Flag是最佳选择它把数组分成小于、等于、大于基准三部分重复元素不需要参与递归。templatetypename T void quickSort3Way(T arr[], int low, int high) { if (low high) return; T pivot arr[low (high - low) / 2]; int lt low, gt high, i low; while (i gt) { if (arr[i] pivot) std::swap(arr[lt], arr[i]); else if (arr[i] pivot) std::swap(arr[i], arr[gt--]); else i; } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt 1, high); }三路快排在处理大量重复元素时优势巨大。我测试过一个包含10万个元素、但只有10个不同值的数组普通快排耗时约45ms三路快排只要8ms。5.3 小区间优化与内省排序快速排序的递归在小数组上开销很大。实践中当子数组长度小于某个阈值通常是16或32时切换到插入排序能显著提升性能。这就是小区间优化。更进一步如果递归深度超过某个限制通常是2*log n说明可能遇到了最坏情况切换到堆排序保证O(n log n)的最坏时间复杂度。这就是内省排序Introsort也是std::sort的核心思想。templatetypename T void introsortUtil(T arr[], int low, int high, int depthLimit) { while (high - low 16) { if (depthLimit 0) { heapSort(arr low, high - low 1); return; } --depthLimit; int p hoarePartition(arr, low, high); introsortUtil(arr, p 1, high, depthLimit); high p; } insertionSort(arr low, high - low 1); }这个混合策略兼顾了快排的平均性能和堆排的最坏情况保证是工程上最实用的方案。我自己实现过一版在100万随机整数上比纯快排快约15%比纯堆排快约2.5倍。注意快速排序是不稳定的。如果你需要稳定排序要么用归并排序要么给元素附加原始索引作为比较的次要关键字。6. 选择排序与堆排序从暴力到优雅6.1 选择排序的朴素逻辑选择排序的思路很直接每一轮从未排序区间选出最小元素放到已排序区间的末尾。templatetypename T void selectionSort(T arr[], int n) { for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) minIdx j; } if (minIdx ! i) std::swap(arr[i], arr[minIdx]); } }选择排序的交换次数是O(n)比冒泡排序少很多。但比较次数固定是O(n²)不管数据是否有序。所以它在近乎有序的数据上反而不如插入排序。选择排序也是不稳定的因为交换可能改变相等元素的相对顺序。选择排序在实际项目中几乎不会用到但它的思想——每轮选最值——是理解堆排序的基础。堆排序本质上就是用堆这种数据结构来高效地选择最值。6.2 堆排序选择排序的终极形态堆排序把选择排序的O(n)选择操作优化到了O(log n)。它先把数组构建成一个大顶堆然后反复取出堆顶元素最大值放到数组末尾再调整堆。templatetypename T void siftDown(T arr[], int start, int end) { int root start; while (root * 2 1 end) { int child root * 2 1; if (child 1 end arr[child] arr[child 1]) child; if (arr[root] arr[child]) { std::swap(arr[root], arr[child]); root child; } else { return; } } } templatetypename T void heapSort(T arr[], int n) { for (int i n / 2 - 1; i 0; --i) siftDown(arr, i, n - 1); for (int i n - 1; i 0; --i) { std::swap(arr[0], arr[i]); siftDown(arr, 0, i - 1); } }堆排序的时间复杂度稳定在O(n log n)空间复杂度O(1)而且最坏情况也是O(n log n)这是它相对于快速排序的最大优势。但堆排序的常数因子比快排大而且由于访问模式跳跃缓存命中率低实际跑起来通常比快排慢。我在实测中对比过100万随机整数快排约85ms堆排约220ms。但在最坏情况下比如已排序数据快排如果没做优化可能退化到秒级而堆排始终稳定在220ms左右。6.3 建堆为什么从n/2-1开始很多人对手写堆排序时for (int i n / 2 - 1; i 0; --i)这个起始位置有疑问。原因在于叶子节点本身已经满足堆性质不需要调整。对于完全二叉树最后一个非叶子节点的索引是n/2 - 10-indexed。从它开始往前调整才能保证每个节点被调整时其子树已经是堆。这个细节如果搞错建堆结果就是错的。我见过有人在面试时从n-1开始建堆结果排序结果完全乱套。记住建堆从最后一个非叶子节点开始自底向上调整。提示堆排序虽然综合性能不如快排但它是最坏情况保证的排序算法中常数最小的。如果你需要确定性性能堆排序是首选。7. 实测数据与选型建议7.1 各算法性能对比我在相同环境下对100万随机整数做了测试结果如下算法平均耗时最坏耗时空间复杂度稳定性插入排序超时(30s)超时O(1)稳定希尔排序(Knuth)约320ms约450msO(1)不稳定冒泡排序超时超时O(1)稳定快速排序(三数取中小区间优化)约85ms约120msO(log n)不稳定选择排序超时超时O(1)不稳定堆排序约220ms约230msO(1)不稳定对于小规模数据1000个元素以内插入排序和希尔排序表现最好耗时都在微秒级。快速排序在递归开销上反而吃亏。7.2 我的选型决策树基于这些实测数据我总结了一个简单的选型决策树数据量小于32直接用插入排序。数据量小于1000对稳定性无要求希尔排序Knuth增量。数据量小于1000要求稳定插入排序或归并排序。数据量大于1000对稳定性无要求快速排序三数取中小区间优化三路分区。数据量大于1000要求最坏情况保证堆排序。数据量大于1000要求稳定归并排序下篇会详细讲。当然实际项目中直接用std::sort通常就够了因为它的内省排序已经覆盖了绝大多数场景。但理解这些算法的特性能帮助你在std::sort不够用时做出正确决策。7.3 几个容易踩的坑最后分享几个我在实现和测试这些算法时踩过的坑坑一比较函数不满足严格弱序。如果你用自定义比较函数必须保证comp(a, a) false且comp(a, b) comp(b, c)能推出comp(a, c)。否则排序结果未定义可能崩溃。我见过有人写作为比较函数在某些数据上直接段错误。坑二整数溢出。计算中间索引时用(low high) / 2可能溢出应该用low (high - low) / 2。这个坑在数据量超过20亿时才出现但一旦出现就是灾难性的。坑三递归深度过大导致栈溢出。快速排序在最坏情况下递归深度是O(n)100万个元素就可能爆栈。解决方案是尾递归优化先递归较小的一半另一半用循环或者切换到内省排序。坑四忽略缓存效应。理论复杂度相同的算法实际性能可能差好几倍。堆排序就是典型例子它的跳跃访问模式导致缓存命中率低实际比快排慢很多。做性能优化时一定要实测不要只看复杂度。这些经验都是我在实际项目中一点点积累的希望能帮你少走弯路。下篇我会继续讲归并排序、计数排序、基数排序和桶排序以及如何根据数据特征选择最合适的算法。