1. 为什么我要把内部排序算法重新撸一遍做C开发这些年排序算法这东西就像空气——平时感觉不到它的存在一旦出问题就是大问题。我见过太多项目在数据量小的时候跑得好好的数据量一上来直接卡死最后定位到问题就是某个不起眼的排序调用。也见过面试的时候被问到“为什么std::sort用内省排序而不是快排”答不上来的人一大把。所以这次我决定把内部排序算法系统性地整理一遍全部用C手写实现不调库不偷懒。所谓内部排序指的是待排序数据全部放在内存里完成的排序过程跟外部排序数据量大到需要借助磁盘相对。这个系列分上下两篇上篇覆盖比较类排序算法包括插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序和归并排序。下篇会讲非比较类排序比如计数排序、基数排序和桶排序。这篇文章适合谁看如果你正在准备技术面试需要把排序算法的原理和实现细节吃透那这篇东西能帮你省不少时间。如果你是在实际项目里遇到了性能瓶颈想搞清楚不同排序算法的适用场景那这篇也能给你一些参考。如果你只是刚学C想找一些经典的算法练手那更好我写的代码都是可以直接编译运行的注释也尽量写详细了。我写这个系列的初衷很简单网上讲排序算法的文章很多但要么只讲原理不给代码要么代码写得稀里糊涂边界条件处理得一塌糊涂。我想做的是把每个算法的核心思路、C实现、复杂度分析、适用场景和踩坑经验都讲清楚让你看完之后不仅能写出来还能知道什么时候该用哪个。2. 排序算法的整体分类与选型思路2.1 比较类排序和非比较类排序的分界线内部排序算法从大类上分可以分成两类比较类排序和非比较类排序。这个分类的核心依据是——算法在排序过程中是否依赖元素之间的两两比较来决定顺序。比较类排序的典型代表就是快排、归并、堆排这些它们通过比较两个元素的大小关系来确定相对顺序。这类算法有一个理论下界任何基于比较的排序算法在最坏情况下的时间复杂度不可能低于O(n log n)。这个结论是有严格数学证明的基于决策树模型n个元素的所有排列有n!种每次比较最多区分两种情况所以决策树的高度至少是log₂(n!)根据斯特林公式近似就是O(n log n)。非比较类排序则不走比较这条路它们利用数据本身的特性比如整数的范围、位数等来直接确定元素的位置。计数排序、基数排序、桶排序都属于这一类。它们的优势是可以在特定条件下突破O(n log n)的下界达到线性时间复杂度但代价是对数据有额外的假设条件。理解这个分类很重要因为它决定了你在面对一个具体问题时应该往哪个方向去选算法。如果数据是任意可比较的对象那你就只能在比较类排序里选如果数据是有限范围的整数那非比较类排序可能给你带来数量级的性能提升。2.2 稳定性到底意味着什么稳定性是排序算法的一个关键属性但很多人对它理解得不够透彻。一个排序算法是稳定的意思是如果序列中有两个相等的元素排序后它们的相对顺序和排序前保持一致。举个例子你有一个学生列表先按姓名排了序现在要按班级再排一次。如果用的排序算法是稳定的那么同一个班级内的学生仍然保持着按姓名排好的顺序。如果是不稳定的同一个班级内的学生顺序就可能被打乱。稳定性的实际意义在于多关键字排序。当你需要按多个字段依次排序时稳定排序可以让你从最后一个关键字开始依次往前排最终结果就是按所有关键字正确排序的。如果排序算法不稳定这个策略就失效了。那哪些算法是稳定的直接插入排序、冒泡排序、归并排序是稳定的。快速排序、选择排序、堆排序、希尔排序是不稳定的。这个要记清楚面试经常问。2.3 时间复杂度、空间复杂度和实际性能的三角关系看一个排序算法教科书通常给你三个指标最好时间复杂度、最坏时间复杂度、平均时间复杂度再加上一个空间复杂度。但实际工程中这些理论指标只是参考真正影响性能的因素还有很多。比如快速排序平均时间复杂度是O(n log n)最坏是O(n²)但实际跑起来通常比归并排序快因为它的常数因子小缓存友好性好。归并排序虽然稳定且最坏也是O(n log n)但它需要O(n)的额外空间而且合并过程的缓存局部性不如快排。再比如插入排序时间复杂度是O(n²)看起来很差但当数据量很小比如n小于16或者数据基本有序的时候它的实际性能反而比快排好。这就是为什么很多标准库的排序实现在小数组上会切换到插入排序。所以选排序算法不能只看大O还要考虑数据规模、数据分布特征、内存限制、稳定性要求、缓存友好性等因素。下面这张表是我自己总结的选型参考算法平均时间最坏时间空间稳定性适用场景直接插入排序O(n²)O(n²)O(1)稳定小规模或基本有序希尔排序O(n^1.3)O(n²)O(1)不稳定中等规模对稳定性无要求冒泡排序O(n²)O(n²)O(1)稳定教学用途实际很少用快速排序O(n log n)O(n²)O(log n)不稳定通用排序大规模数据选择排序O(n²)O(n²)O(1)不稳定数据量小交换成本高堆排序O(n log n)O(n log n)O(1)不稳定需要最坏保证空间受限归并排序O(n log n)O(n log n)O(n)稳定需要稳定性链表排序这张表建议收藏面试前扫一眼就能快速回忆起来。3. 比较类排序算法的C实现与细节剖析3.1 直接插入排序小数组之王直接插入排序的思路非常直观把数组分成已排序和未排序两部分每次从未排序部分取第一个元素插入到已排序部分的正确位置。这个过程就像你打扑克牌时整理手牌一样每摸一张新牌就把它插到前面已经排好的牌里面。很多人觉得插入排序太简单了不值得深入研究。但我要说插入排序是理解所有高级排序算法的基础而且它在实际工程中出现的频率远超你的想象。C的std::sort在递归到小数组时底层用的就是插入排序。先看基础版本的实现void insertionSort(int arr[], int n) { for (int i 1; i n; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }这段代码的核心在于内层while循环。它从当前位置往前扫描把所有比key大的元素都往后挪一位直到找到key应该待的位置。注意这里是“挪”不是“换”每次只做一次赋值比交换操作少了一半的写入。那为什么说插入排序在小数组上表现好两个原因。第一当n很小时O(n²)和O(n log n)的差距不大比如n10的时候n²100n log n≈33差距只有3倍但插入排序的常数因子比快排小得多实际可能反超。第二插入排序对基本有序的数据非常高效如果每个元素距离它最终位置不超过k那时间复杂度就降到O(nk)。这里有一个优化技巧叫“带哨兵的插入排序”。我们可以在数组最前面预留一个位置放一个极小值哨兵这样内层循环就不用每次判断j 0了少一次比较void insertionSortWithSentinel(int arr[], int n) { // 假设arr[0]位置可以借用实际数据从arr[1]开始 // 先找到最小值放到arr[0]作为哨兵 int minIdx 1; for (int i 2; i n; i) { if (arr[i] arr[minIdx]) minIdx i; } std::swap(arr[0], arr[minIdx]); for (int i 2; i n; i) { int key arr[i]; int j i - 1; while (arr[j] key) { // 不需要判断j 0了 arr[j 1] arr[j]; j--; } arr[j 1] key; } }注意哨兵技巧在数据量大的时候收益不明显但在嵌入式等对指令数敏感的场景下减少一次比较就是实打实的性能提升。还有一个常见的优化是“二分插入排序”用二分查找来定位插入位置把比较次数从O(n)降到O(log n)。但要注意虽然比较次数减少了元素移动的次数没变所以整体时间复杂度还是O(n²)。二分插入排序在比较操作代价很高比如比较的是长字符串的时候才有明显优势。3.2 希尔排序插入排序的进化形态希尔排序是插入排序的改进版核心思想是先用较大的增量把数组分成若干个子序列对每个子序列做插入排序然后逐步缩小增量最后当增量为1时对整个数组做一次插入排序。为什么这样做有效因为插入排序对基本有序的数组效率很高。希尔排序通过前几轮大增量排序让数组变得“基本有序”最后一轮增量为1的插入排序就不需要做太多移动了。希尔排序的性能高度依赖于增量序列的选择。最常用的是希尔本人提出的n/2序列但这不是最优的。Knuth提出的序列(1, 4, 13, 40, ...)即h 3h 1在实践中表现更好。还有Sedgewick序列等更复杂的方案。我用Knuth序列来实现一个版本void shellSort(int arr[], int n) { // 计算初始增量使用Knuth序列 int gap 1; while (gap n / 3) { gap gap * 3 1; } while (gap 1) { // 对每个增量做插入排序 for (int i gap; i n; i) { int key arr[i]; int j i - gap; while (j 0 arr[j] key) { arr[j gap] arr[j]; j - gap; } arr[j gap] key; } gap / 3; } }这段代码的结构和插入排序几乎一样唯一的区别是把1换成了gap。当gap1的时候就是标准的插入排序。希尔排序的时间复杂度分析很复杂跟增量序列有关。Knuth序列下大约是O(n^1.5)Sedgewick序列可以做到O(n^1.3)左右。希尔排序是不稳定的因为相同的元素可能在不同的子序列中被交换导致相对顺序改变。实操心得希尔排序在中等规模数据几千到几万上表现相当不错实现简单不需要额外空间。如果你不想引入复杂的快排或归并希尔排序是一个很实用的选择。3.3 冒泡排序教学意义大于实用价值冒泡排序大概是所有人学的第一个排序算法。它的思路是重复遍历数组每次比较相邻两个元素如果顺序不对就交换。每一轮遍历会把当前未排序部分的最大值“冒泡”到末尾。基础实现void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); } } } }这个版本有一个明显的问题如果数组已经有序了它还是会老老实实跑完所有轮。我们可以加一个标志位来优化void bubbleSortOptimized(int 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; // 本轮没有交换说明已经有序 } }还有一个进一步优化记录最后一次交换的位置下一轮只需要扫描到这个位置就行了。因为在这个位置之后的元素已经有序了。void bubbleSortFurther(int arr[], int n) { int lastSwap n - 1; while (lastSwap 0) { int bound lastSwap; lastSwap 0; for (int j 0; j bound; j) { if (arr[j] arr[j 1]) { std::swap(arr[j], arr[j 1]); lastSwap j; } } } }说实话冒泡排序在实际项目中基本不会用到它的交换次数太多缓存也不友好。但它的教学价值在于它是理解“比较-交换”这个排序基本范式的最好入口而且优化过程能教会你很多算法优化的通用思路。3.4 快速排序分治思想的经典演绎快速排序是整个排序算法家族里最重要的一个没有之一。它的核心思想是分治选一个基准元素把数组分成两部分左边都比基准小右边都比基准大然后对左右两部分递归排序。快排的平均时间复杂度是O(n log n)常数因子小原地排序递归栈不算的话空间是O(1)缓存友好这些优点让它成为通用排序的首选。C的std::sort底层就是快排的变体内省排序。先看最基础的Hoare分区版本int partition(int arr[], int low, int high) { int pivot arr[low]; // 选第一个元素作为基准 int i low, j high; while (i j) { while (i j arr[j] pivot) j--; while (i j arr[i] pivot) i; if (i j) std::swap(arr[i], arr[j]); } std::swap(arr[low], arr[i]); return i; } void quickSort(int arr[], int low, int high) { if (low high) { int pivotPos partition(arr, low, high); quickSort(arr, low, pivotPos - 1); quickSort(arr, pivotPos 1, high); } }这个版本有几个问题需要讨论。第一基准选择。选第一个元素作为基准在数组已经有序的情况下会退化成O(n²)因为每次分区都只能分出一个元素。解决方案是随机选基准或者三数取中。三数取中的做法是取数组首、尾、中间三个元素排序后取中间值作为基准。这样能有效避免在部分有序数据上的退化。int medianOfThree(int arr[], int low, int high) { int mid low (high - low) / 2; if (arr[low] arr[mid]) std::swap(arr[low], arr[mid]); if (arr[low] arr[high]) std::swap(arr[low], arr[high]); if (arr[mid] arr[high]) std::swap(arr[mid], arr[high]); // 此时arr[mid]是中间值把它换到low位置 std::swap(arr[mid], arr[low]); return arr[low]; }第二小数组优化。当子数组长度小于某个阈值通常是8到16时切换到插入排序。因为快排的递归调用有函数调用开销小数组上插入排序更快。第三尾递归优化。快排的递归过程中第二次递归可以用循环代替减少栈深度void quickSortOptimized(int arr[], int low, int high) { while (low high) { if (high - low 16) { insertionSort(arr low, high - low 1); break; } int pivotPos partition(arr, low, high); // 先递归较短的一边减少栈深度 if (pivotPos - low high - pivotPos) { quickSortOptimized(arr, low, pivotPos - 1); low pivotPos 1; } else { quickSortOptimized(arr, pivotPos 1, high); high pivotPos - 1; } } }注意先递归较短的一边可以把递归栈深度控制在O(log n)以内这是快排最坏空间复杂度的保证。还有一个经典问题是“三路快排”专门处理有大量重复元素的情况。普通快排把等于基准的元素分到左边或右边如果数组里全是相同的元素每次分区只能排除一个元素退化成O(n²)。三路快排把数组分成小于、等于、大于三部分等于基准的部分直接到位不参与后续递归。void quickSort3Way(int arr[], int low, int high) { if (low high) return; int pivot arr[low]; int lt low; // arr[low..lt-1] pivot int gt high; // arr[gt1..high] pivot int i low 1; // arr[lt1..i-1] pivot 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); }三路快排在处理大量重复数据时优势非常明显比如对一堆只有几个不同取值的标签数据排序。3.5 选择排序简单但不高效选择排序的思路是每次从未排序部分选出最小的元素放到已排序部分的末尾。跟冒泡排序相比它的交换次数少很多每次只交换一次总共n-1次交换。void selectionSort(int 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)选择排序还是O(n²)。那选择排序有什么用它的优势在于交换次数最少。如果交换操作的代价很高比如元素很大复制成本高选择排序可能比插入排序更合适。另外选择排序的思路可以扩展到“部分排序”场景比如找出数组中第k小的元素用选择排序的思路只需要O(kn)的时间。3.6 堆排序最坏情况下的可靠选择堆排序利用二叉堆的性质来排序。先建一个大顶堆然后每次把堆顶元素最大值和末尾元素交换堆的大小减一再调整堆重复这个过程直到堆为空。堆排序的核心操作有两个建堆和调整堆。建堆的时间复杂度是O(n)不是O(n log n)这个很多人会搞错。原因是建堆是从最后一个非叶子节点开始往前调整大部分节点都在底层调整的深度很小数学上可以证明总代价是O(n)。void heapify(int 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) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(int arr[], int n) { // 建堆从最后一个非叶子节点开始 for (int i n / 2 - 1; i 0; i--) { heapify(arr, n, i); } // 逐个取出堆顶元素 for (int i n - 1; i 0; i--) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } }堆排序的优势是最坏时间复杂度是O(n log n)空间复杂度是O(1)不需要额外空间。这在内存受限的嵌入式场景下很有价值。它的劣势是缓存不友好因为堆的访问模式是跳跃式的不像快排那样顺序访问。实操心得堆排序的常数因子比快排大所以在一般情况下比快排慢。但如果你需要一个最坏情况保证又不想用归并排序的额外空间堆排序是唯一的选择。3.7 归并排序稳定排序的代表归并排序是分治思想的另一个经典应用。它把数组分成两半分别排序然后合并两个有序数组。合并操作是归并排序的核心也是它稳定性的来源——合并时如果两个元素相等优先取左边的这样就不会改变相等元素的相对顺序。void merge(int arr[], int temp[], int left, int mid, int right) { int i left, j mid 1, k left; while (i mid j right) { if (arr[i] arr[j]) { // 注意是保证稳定性 temp[k] arr[i]; } else { temp[k] arr[j]; } } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; for (int p left; p right; p) { arr[p] temp[p]; } } void mergeSortHelper(int arr[], int 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); merge(arr, temp, left, mid, right); } void mergeSort(int arr[], int n) { int* temp new int[n]; mergeSortHelper(arr, temp, 0, n - 1); delete[] temp; }归并排序的时间复杂度稳定在O(n log n)不管数据是什么分布。它需要O(n)的额外空间这是它最大的缺点。但在排序链表的时候归并排序不需要额外空间只需要改变指针所以链表排序首选归并。归并排序还有一个重要应用是外部排序。当数据量大到内存放不下时可以把数据分成若干块每块在内存中排序后写回磁盘然后多路归并。这个在数据库系统中非常常见。注意归并排序的合并操作中判断条件用而不是这是保证稳定性的关键。如果用当两个元素相等时会优先取右边的稳定性就被破坏了。4. 性能实测与选型建议4.1 实测数据对比理论分析说再多不如实际跑一遍。我在本机用随机数据、有序数据、逆序数据三种分布分别测试了上面几种排序算法在不同数据规模下的耗时。测试环境是普通的开发机编译器用g -O2优化。数据规模n10000时的结果单位毫秒算法随机数据有序数据逆序数据插入排序450.190希尔排序323冒泡排序1800.5360快排三数取中1.51.21.3快排三路1.61.31.4选择排序606060堆排序32.52.5归并排序21.81.8从数据可以看出几个关键点插入排序在有序数据上快得惊人但在逆序数据上慢得离谱快排在各种数据分布下都很稳定堆排序和归并排序表现接近但都比快排慢一些选择排序不管什么数据都是同一个速度。n100000时的结果算法随机数据有序数据逆序数据希尔排序453045快排三数取中181516堆排序403535归并排序252222数据量增大后O(n log n)的算法优势更加明显。希尔排序虽然也是O(n^1.3)左右但常数因子比快排大所以慢一些。4.2 不同场景下的选型决策树根据我的实际经验选排序算法可以按下面的逻辑来第一步看数据规模。n小于50直接用插入排序别想太多。n在50到1000之间希尔排序或者快排都行。n大于1000优先考虑快排。第二步看数据特征。如果数据基本有序插入排序或希尔排序是最优选择。如果数据有大量重复元素用三路快排。如果数据是链表结构用归并排序。第三步看约束条件。需要稳定排序选归并。内存受限选堆排序或快排。需要最坏情况保证选堆排序或归并。第四步看实现成本。如果不想写复杂的快排希尔排序是一个很好的折中方案实现简单性能也不错。实操心得在实际项目中我通常直接用std::sort它的内省排序实现已经足够优秀。只有在特殊场景下比如需要稳定排序用std::stable_sort或者内存极度受限需要自己控制才会手写排序。但理解这些算法的原理能帮你在遇到性能问题时快速定位和优化。4.3 混合排序策略的工程实践现代标准库的排序实现几乎都是混合策略。以introsort内省排序为例它的策略是先用快排当递归深度超过2*log(n)时切换到堆排序防止快排退化当子数组长度小于阈值时切换到插入排序。这种混合策略结合了各个算法的优点快排的平均性能好堆排序的最坏情况有保证插入排序在小数组上效率高。我自己实现过一个简化版的混合排序核心逻辑是这样的void hybridSort(int arr[], int low, int high, int depthLimit) { if (high - low 16) { insertionSort(arr low, high - low 1); return; } if (depthLimit 0) { heapSort(arr low, high - low 1); return; } int pivotPos partition(arr, low, high); hybridSort(arr, low, pivotPos - 1, depthLimit - 1); hybridSort(arr, pivotPos 1, high, depthLimit - 1); }这个混合排序在实测中比单纯的快排稳定得多特别是在面对精心构造的“快排杀手”数据时不会退化成O(n²)。5. 常见问题与排查技巧实录5.1 快排栈溢出怎么办快排递归深度过大导致栈溢出这是实际工程中最常见的问题之一。典型症状是程序在排序大规模数据时崩溃错误信息是“stack overflow”或者“segmentation fault”。排查思路首先确认是不是快排导致的可以在递归函数入口打印当前深度。如果深度超过1000基本可以确定是递归太深了。解决方案有三个。第一先递归较短的一边把栈深度控制在O(log n)。第二设置递归深度阈值超过阈值切换到堆排序。第三直接把递归改成迭代用显式的栈来模拟。我推荐第一种方案改动最小效果最明显。具体做法就是在partition之后比较左右两边的长度先递归短的那边长的那边用循环继续处理。5.2 排序结果不稳定导致的隐蔽bug稳定性问题往往很隐蔽因为排序结果看起来是对的只是相等元素的顺序变了。这种bug在多关键字排序的场景下才会暴露出来。比如你有一个订单列表先按时间排序再按金额排序。如果用的排序算法不稳定相同金额的订单可能不再按时间排列了。用户看到的就是“同样金额的订单时间顺序乱了”。排查方法构造一个包含重复元素的测试用例在排序前给每个元素标记原始位置排序后检查相同值的元素是否保持了原始相对顺序。解决方案如果需要稳定性把快排换成归并排序或者用std::stable_sort。如果不想换算法可以把比较函数改成比较一个包含原始索引的复合键这样即使算法不稳定结果也是稳定的。5.3 比较函数写错导致的排序异常自定义比较函数写错是另一个高频问题。最常见的错误是违反了严格弱序规则。严格弱序要求比较函数满足三个条件非自反性comp(a, a)必须为false、非对称性comp(a, b)为true则comp(b, a)必须为false、传递性comp(a, b)和comp(b, c)为true则comp(a, c)必须为true。违反严格弱序会导致std::sort行为未定义可能崩溃可能死循环也可能产生错误的排序结果。一个典型的错误写法是return a b;这违反了非自反性因为a a是true。正确的写法是return a b;或者return a b;。排查方法用一组包含相等元素的测试数据检查排序结果是否正确。如果排序后相等元素的顺序乱了或者程序崩溃大概率是比较函数的问题。5.4 常见问题速查表问题现象可能原因排查方法解决方案程序崩溃栈溢出快排递归太深打印递归深度先递归短边或切换堆排序排序结果不稳定用了不稳定的算法检查相等元素顺序换归并排序或加索引排序后数据错乱比较函数违反严格弱序检查比较函数逻辑改用或避免和小数组排序慢用了快排测试n50的情况切换到插入排序大量重复元素排序慢普通快排退化检查数据重复率改用三路快排内存不足归并排序额外空间检查内存使用改用堆排序或快排最后分享一个小技巧在调试排序算法时用一个固定种子的随机数生成器产生测试数据这样每次运行的结果都是可复现的。另外写一个checkSorted函数在每次排序后验证结果是否正确能帮你快速定位问题。这个系列的上篇到这里就差不多了。下篇我会讲非比较类排序包括计数排序、基数排序和桶排序以及它们在特定场景下如何实现线性时间排序。如果你把上面的代码都亲手敲了一遍相信你对排序算法的理解会上一个台阶。