八大排序算法全解析：从特性拆解到C语言实战指南

排序算法这东西，很多人觉得"背会了八种就能应付面试"，但真到项目里选型、优化、排查问题时，才发现自己连"为什么快排默认用三数取中"、"归并排序在什么场景下反而更快"这种基本问题都答不上来。我写这一篇，就是想把这摊事彻底捋清楚：八大排序算法的特性怎么拆解、分治思想怎么真正用起来、C语言实现时有哪些坑、以及在实际场景里到底该怎么选。不管你是刚学数据结构的学生，还是被线上排序性能问题折磨的工程师，这篇都能给你一个可以直接抄的参考框架。

1. 排序算法全景与核心评价指标

1.1 为什么排序算法值得花时间吃透

先别急着跳过。排序算法表面上是"把一组数据排成有序序列"，但它的价值远超这个定义本身。你会发现几乎所有经典算法思想——分治、递归、堆、哈希、桶——都能在排序算法里找到最直观的载体。我见过不少工程师，业务写得飞起，一涉及到需要自己实现一个有序结构或者优化一段排序逻辑就抓瞎，原因就是早期没把排序算法的底层逻辑吃透。

更重要的是，排序算法的性能直接影响业务系统的响应时间。比如一个电商后台的商品列表，如果依赖数据库每次查询都做全量排序，数据量上来之后响应时间会成倍增长；而如果能在内存里用合适的排序算法预处理数据，效果立竿见影。换句话说，排序不是一个"会写就行"的基础题，它是你在面对真实数据时做出正确技术决策的分水岭。

1.2 时间复杂度、空间复杂度与稳定性，一个都不能少

评价排序算法有三个绕不开的维度：时间复杂度、空间复杂度和稳定性。

时间复杂度要区分最坏情况、最好情况和平均情况。比如快排在平均情况下是O(n log n)，但最坏情况下会退化到O(n²)，这点做系统设计时必须考虑，因为线上数据不会永远给你"平均情况"。

空间复杂度则是很多人容易忽视的点。原地排序（in-place）意味着额外空间是O(1)，而归并排序需要O(n)的辅助数组。在内存受限的嵌入式环境里，归并排序的O(n)额外空间可能是致命伤，这就是为什么嵌入式排序经常优先考虑堆排序而不是归并排序。

稳定性指的是：如果两个元素值相同，排序后它们的相对顺序是否保持不变。稳定排序在按多个关键字排序时特别有用——比如先按时间排，再按优先级排，如果你用的排序算法不稳定，第二次排序可能打乱第一次的顺序。

我把八个经典排序算法的核心指标先列个总表，后面逐节拆解：

这张表先放这，后面每一行我都会展开讲背后的原理和适用场景。

2. 八大经典排序算法特性逐个拆解

2.1 冒泡排序：入门的价值不在性能

冒泡排序的核心思想是相邻元素两两比较，如果顺序错误就交换，每一轮把当前未排序部分的最大值"冒泡"到末尾。实现非常简单，双循环就搞定了。

我实际的想法是：冒泡排序唯一的实战价值在于它极端简单、代码不可能写错。在一些对性能不敏感、数据量很小（比如几十个元素以内）的场景，你确实可以图省事用冒泡。但它有个隐藏优势——它是稳定排序，如果你只是在维护一个"局部有序"的小数组，冒泡的提前退出机制（某一轮没有发生任何交换就说明已经有序）能提供O(n)的最好情况。

不过说句得罪人的话：如果你还在生产代码里用冒泡排上万条数据，那真该反思了。它每一轮比较次数是固定的n-1、n-2...，总比较次数约n²/2，这个复杂度在数据量翻倍时是灾难性的。

2.2 选择排序：交换次数最少的朴素方案

选择排序的思路更直接：每一轮从未排序区间里找到最小值，放到已排序区间的末尾。它最突出的特点是交换次数很少——每轮最多交换一次，总共最多n-1次交换。

这在某些场景下是实打实的优势：如果被排序的元素是结构体，交换的成本很高（要整体拷贝内存），而比较的成本相对低，那么选择排序反而比那些"交换频繁但比较次数更少"的算法更划算。

但是要注意，选择排序是不稳定排序。为什么？因为它会把最小值直接"扔"到前面，可能跨越中间相同元素，导致相同元素的相对顺序改变。举个例子：[5, 3, 5, 2]，第一轮把2换到开头，原来两个5的相对位置没有变，但如果换成[5, 5, 2]，第一轮把2和第一个5交换，两个5的顺序就反了。这个细节笔试面试经常考。

2.3 插入排序：小数据集的隐形冠军

插入排序就像整理扑克牌：从第二个元素开始，每次把当前元素插入到前面已经有序的序列中的正确位置。平均情况下是O(n²)，但它有两个其他算法难以匹敌的优势。

第一个优势是最好情况O(n)。如果数据本身基本有序，插入排序的内层循环几乎不会执行，实际效率极高。这个特性让它在工程中成为"几乎有序数据"的首选。

第二个优势是它天然稳定，而且实现极其紧凑。很多标准库的排序算法都会在递归到小区间时切换到插入排序——比如Java的Arrays.sort在快排递归到元素个数小于47时就会改用插入排序。这不是闲得没事，而是实测表明：在小规模数据上，插入排序的常数因子远小于快排和归并，函数调用开销反而成了主导。

我个人的经验是：任何排序算法，在数据量小于50时，都不要用O(n log n)的复杂算法，直接用插入排序反而更快。这不是理论推导，是跑过benchmark之后得出的结论。

2.4 希尔排序：第一个突破O(n²)的实践派

希尔排序是插入排序的改进版，它引入"增量"的概念：先让相隔较远的元素进行比较和交换，让数据快速接近有序，最后再以增量为1做一次完整插入排序。这个"预排序"的过程大幅减少了最终插入排序的工作量。

希尔排序的时间复杂度随增量序列的选择而变化。最原始的希尔增量（n/2, n/4...）最坏是O(n²)；而使用Hibbard增量（1, 3, 7, 15... 即2^k -1）或Sedgewick增量时，平均复杂度可以到O(n^1.3)左右。

希尔排序不稳定，因为间隔交换会破坏相对顺序。它的空间复杂度是O(1)，属于原地排序，在内存受限的场景是个不错的折中。不过说实话，现在生产环境里单独使用希尔排序的场景不多，它更多是作为算法学习"人如何一步步改进一个朴素算法"的经典案例。

2.5 归并排序：稳定与确定性的代名词

归并排序基于分治思想：先把数组不断对半切分，直到每个子序列只剩一个元素，然后两两合并成有序序列。它的时间复杂度无论最好、最坏还是平均都是O(n log n)，这是它最大的底气——不存在快排那种"最坏退化"的隐患。

归并排序需要O(n)的额外空间来存放合并结果，这是它唯一的硬伤。但它的稳定性和确定性让它在很多场景下不可替代：比如链表排序（归并排序不需要随机访问，天然适合链式存储）、多路归并外部排序（处理海量数据放不进内存的场景）。

我在工程里用归并排序最多的场景就是"对稳定性有硬指标的大规模数据排序"。比如银行交易流水、订单日志这种需要保留原始顺序的多级排序，归并排序是正解。

2.6 快速排序：平均性能之王

快排也是分治思想的应用，但它的分法比归并更聪明：选一个基准值（pivot），把数组分成"小于基准"和"大于基准"两部分，然后递归处理左右两部分。关键在于，这个划分是原地完成的，不需要额外的大块辅助空间。

快排平均情况O(n log n)，而且常数因子很小，实际运行速度通常比堆排序和归并排序都快——因为内层循环最简单，CPU缓存利用率高。这就是为什么绝大多数语言标准库的排序默认实现都是快排的变种。

但快排有两个必须正视的问题。第一个是基准值选择不当会导致最坏O(n²)：如果数据已经有序，而你又每次选第一个元素做基准，那划分极端不平衡，递归深度变成n，性能直接崩盘。解决方式是三数取中或者随机选基准。第二个是它不是稳定排序。某些业务场景要求稳定排序，快排就不适用。

我之前有个项目就是这么踩坑的：对一批结构体按时间戳排序，因为快排不稳定，导致相同时间戳的记录顺序被打乱，后续的增量计算逻辑全乱了。后来换成归并排序才解决。

2.7 堆排序：无需额外空间的最坏情况保证

堆排序利用堆这种数据结构：先构建一个最大堆，然后反复把堆顶元素（最大值）与末尾元素交换，再调整堆结构，最终得到一个升序数组。

堆排序最吸引人的地方在于：最坏情况时间复杂度仍然是O(n log n)，同时额外空间是O(1)。这两个条件同时满足的算法很少。所以如果你面临"数据量很大、最坏情况不能接受退化、内存又紧张"的场景，堆排序几乎是最优解。

它的缺点是：实际运行速度通常比快排慢，因为它对数据的访问模式是跳跃式的，CPU缓存命中率低；同时它是不稳定的排序。还有一个细节是，堆排序最好情况也是O(n log n)，没有利用"数据已经有序"这种先验信息的能力。

2.8 计数排序与基数排序：跳出比较排序的思维定式

八种经典排序通常在基础教材里会加上计数排序、基数排序和桶排序。很多人称它们为"八大排序"的一部分，严格来说这三种是线性时间排序，它们的核心思路是：不通过元素之间的比较来排序，而是利用元素本身的取值特征。

计数排序要求数据是范围有限的整数。做法是统计每个值出现的次数，然后根据计数累加的结果把元素放回正确位置。时间复杂度O(n+k)，其中k是数据范围。但k如果远大于n，空间浪费会非常严重。

基数排序则是按位进行排序：从最低位到最高位，每一位都用稳定的计数排序处理。比如对非负整数排序，按个位、十位、百位逐次稳定排序，最终结果就是有序的。它适合位数有限、取值范围很大的整数排序。

我特别想强调一个点：线性排序算法不是银弹。它们在数据特征匹配时效率惊人，但一旦脱离适用条件（比如数据是浮点数、或者范围极其稀疏），就会退化成空间怪物。实际项目中普遍使用的还是基于比较的排序算法。

3. 分治思想深度解析：以归并排序的改写为例

3.1 分治三步骤的本质

分治思想的基本框架只有三步：分解、解决、合并。听起来简单，但真正理解它需要想清楚每一步到底在干什么。

分解是把一个规模为n的问题拆成若干个规模更小的子问题，子问题之间相互独立、形式与原问题相同。排序里的体现就是"把数组切成两半"。解决是递归地处理子问题——直到子问题规模小到可以直接求解（递归边界）。合并是把子问题的解组合成原问题的解，这一步往往是整个算法最容易出错的地方，归并排序的合并就是"两个有序数组合并成一个有序数组"。

用生活化的例子来类比：你要整理一屋子乱放的书。分治的思路是，先把书按类别分成几堆，每堆再分成更小的堆，直到一堆只有三五本，直接手工整理即可，最后再按顺序把所有小堆合成一整列。这个"分——治——合"的节奏，就是分治思想的精髓。

3.2 用分治思想改造归并排序的实战路径

"利用分治思想修改合并排序算法"这个话题，我展开说说。归并排序本身已经是分治的教科书实现，但实战中可以做很多改造，让它的性能与适用性更好。

第一个常规改造是引入"小区间插入排序"。在归并递归到子数组长度小于某个阈值（比如16或32）时，不再继续递归，而是直接用插入排序处理这个小数组。理由我在前面说过：小规模数据上，递归与合并的函数调用开销超过了插入排序的比较开销。实测效果通常有10%-20%的性能提升。

第二个改造是优化合并过程。传统归并就地合并需要辅助数组，但这里有一个经典技巧：可以在合并时使用"哨兵值"避免每次判断数组边界。即在每个待合并数组的末尾放一个极大值（比如INT_MAX），这样在合并循环里就不用每次都检查"是否越界"，直接比较两个数组当前元素即可。这样代码更简洁，性能也有微幅提升。

第三个改造更进阶——用非递归方式重写归并排序。递归版本虽然清晰，但递归深度O(log n)在极端情况下也可能出问题（比如栈空间受限的嵌入式环境），而且递归函数调用的开销不可忽略。非递归版本从底向上：首先把相邻的1个元素两两合并成长度2的有序段，再把相邻长度2的有序段合并成长度4的有序段，依次类推，直到整个数组有序。实现时需要小心处理"最后一次合并长度可能不是2的幂"的情况。

下面是归并排序核心合并过程的C语言实现，我把哨兵优化也加进去了：

#include <stdio.h> #include <stdlib.h> #include <limits.h> // 合并两个有序区间 [left, mid] 和 [mid+1, right] // 使用哨兵值简化边界判断：在临时数组末尾插入 INT_MAX void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int* L = (int*)malloc((n1 + 1) * sizeof(int)); int* R = (int*)malloc((n2 + 1) * sizeof(int)); 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]; L[n1] = INT_MAX; // 哨兵 R[n2] = INT_MAX; // 哨兵 int i = 0, j = 0; for (int k = left; k <= right; k++) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } } free(L); free(R); } // 自顶向下归并排序 void mergeSort(int arr[], int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); }

注意一个关键细节：mid = left + (right - left) / 2，这里用差值除以2而不是(left + right) / 2，是为了防止两个大整数相加溢出。这是面试官特别喜欢考察的隐藏知识点。

再给一个非递归归并排序的实现，这个版本在工程中更有实用价值：

// 自底向上归并排序：迭代版 void mergeSortIterative(int arr[], int n) { for (int width = 1; width < n; width *= 2) { for (int left = 0; left < n - width; left += 2 * width) { int mid = left + width - 1; int right = (left + 2 * width - 1 < n - 1) ? (left + 2 * width - 1) : (n - 1); if (mid < right) { merge(arr, left, mid, right); } } } }

这个迭代版本的核心是外层循环控制"合并的宽度"，从1开始翻倍；内层循环按宽度分组并合并相邻两个有序段。最后一组的右边界可能超出数组，需要做right的越界判断。

3.3 优化后的归并排序性能对比

我实际跑过一组对比数据：对100万个随机整数排序，在同一台机器上重复测试取平均值。

从数据能看出，迭代版+小区间插入排序的组合效果最好，但提升幅度并没有想象中那么大，大概在18%左右。这说明：优化要针对瓶颈做，归并排序的主要开销一直在合并过程上，单纯减少递归调用收益有限；反过来，如果能在合并过程中利用数据已有顺序提前跳过一些合并操作（类似Timsort的探测逻辑），收益会大得多。

4. C语言实现核心排序算法

4.1 通用接口设计与比较/交换函数

C语言实现排序算法，第一个要考虑的是"怎么复用"。你不可能每次都把排序逻辑写死在一个具体类型上，所以要用函数指针做通用接口。

最经典的做法是模仿C标准库的qsort：

void sort_generic(void* base, size_t num, size_t size, int (*compare)(const void*, const void*));

参数含义依次是：数组起始指针、元素个数、单个元素字节大小、比较函数指针。有了这个接口，你就能对任意类型的数组进行排序：整数、浮点数、字符串、结构体都可以。

实际使用时还要注意两个C语言特有的细节。第一是交换函数不能直接用=赋值，因为你要交换的是size字节的原始内存，需要用临时缓冲区和memcpy完成。而且这里的memcpy必须用内存复制而非类型强转，因为你根本不知道调用方传进来的是什么类型。

第二是compare函数的规则：返回值小于0表示第一个参数应排在第二个参数前面，等于0表示相等，大于0表示第一个参数应排在第二个参数后面。这个约定容易搞反，C标准库的qsort就是按这个约定来的。

下面是一个基于冒泡排序实现的通用排序函数，大多数场景下是为了说明接口风格：

#include <string.h> void bubbleSortGeneric(void* base, size_t num, size_t size, int (*compare)(const void*, const void*)) { char* arr = (char*)base; char* temp = (char*)malloc(size); for (size_t i = 0; i < num - 1; i++) { for (size_t j = 0; j < num - 1 - i; j++) { if (compare(arr + j * size, arr + (j + 1) * size) > 0) { memcpy(temp, arr + j * size, size); memcpy(arr + j * size, arr + (j + 1) * size, size); memcpy(arr + (j + 1) * size, temp, size); } } } free(temp); }

这里用char*做指针运算的原因：C语言中void*不能直接做+运算，必须先转成char*，这样arr + j * size才能精确跳到第j个元素的首地址。

4.2 快排与归并的C代码实现细节

快排的C实现要重点关注划分函数。经典的Lomuto划分法和Hoare划分法都有各自的优劣势。Lomuto实现简单、逻辑直观，但交换次数略多；Hoare效率更高，但边界条件更易出错。

我用的是Lomuto加三数取中：

#include <stdio.h> // 三数取中：返回 left、mid、right 三个位置的中位值下标 int medianOfThree(int arr[], int left, int right) { int mid = left + (right - left) / 2; if (arr[left] > arr[mid]) { int t = arr[left]; arr[left] = arr[mid]; arr[mid] = t; } if (arr[mid] > arr[right]) { int t = arr[mid]; arr[mid] = arr[right]; arr[right] = t; } if (arr[left] > arr[mid]) { int t = arr[left]; arr[left] = arr[mid]; arr[mid] = t; } return mid; } // Lomuto 划分：以 pivotIndex 处的值为基准，原地划分 int partition(int arr[], int left, int right) { int pivotIndex = medianOfThree(arr, left, right); int pivot = arr[pivotIndex]; // 把基准值先交换到末尾 int t = arr[pivotIndex]; arr[pivotIndex] = arr[right]; arr[right] = t; int i = left; for (int j = left; j < right; j++) { if (arr[j] < pivot) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; } } arr[right] = arr[i]; arr[i] = pivot; return i; } void quickSort(int arr[], int left, int right) { if (left >= right) return; // 小区间使用插入排序，避免递归过深 if (right - left + 1 <= 16) { for (int i = left + 1; i <= right; i++) { int key = arr[i]; int j = i - 1; while (j >= left && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } return; } int p = partition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p + 1, right); }

这个实现在实践中足够稳。需要注意：partition返回的基准位置p已经是最终位置，递归时需要跳过p本身，否则会造成无限递归。

4.3 C语言实现中的指针与内存陷阱

C语言排序实现最常见的坑，我总结成以下几类，几乎每个都是血泪换来的经验。

第一个坑是数组越界。归并排序的合并循环、快排的划分循环都特别容易出现越界。尤其是哨兵优化后，如果哨兵值选得不合适（比如你用INT_MAX做哨兵，但数据里恰巧有INT_MAX），哨兵就失效了。稳妥做法是把哨兵值设计成"数据中不可能出现的值"。

第二个坑是malloc返回值未检查。在嵌入式或内存紧张的环境里，malloc完全可能返回NULL。很多人的排序代码直接用了没有判空，一旦内存不足，整个程序直接段错误。所有临时数组分配后必须判空，并给出错误处理。

第三个坑是递归深度过大导致栈溢出。快排最坏情况下递归深度是O(n)，如果数据量是百万级别，栈空间耗尽就会崩溃。这在大数据处理中是真实风险。解决办法包括：用三数取中或随机基准把概率降到极低；或者把小数组优先用插入排序处理，让递归深度保持在O(log n)水平；或者干脆用非递归版本。

第四个坑是结构体数组排序时的交换代价。直接用memcpy交换两个大的结构体，如果结构体里有指针，你交换的只是指针拷贝，没有问题；但如果结构体里包含大数组，memcpy整块拷贝的代价就很高。这种情况可以考虑排序索引数组而不是原始数据。

5. 实战场景下的算法选择指南

5.1 按数据规模选择

选择排序算法的第一条经验是看数据规模。规模不同，最优解完全不同。

数据量在几十以内时，插入排序几乎总是最好的选择。它的常数因子极小，代码简单，而且完全不需要额外空间。很多标准库实现都遵循这个原则，比如Go的sort包在切片长度小于12时使用插入排序。

数据量在几千到几十万之间，且对最坏情况没有苛刻要求时，快排是首选。这个区间是快排的主场，它的平均性能最优，且内存占用合理。

数据量达到百万以上且要求稳定性时，归并排序最合适。虽然它需要O(n)的辅助空间，但稳定性和确定性的优势在大数据场景下足够重要。

如果数据量巨大，内存放不下，那就不是简单的内存排序问题了，需要用外部排序——归并排序的多路归并版本是外部排序的基础。

5.2 按数据特征选择

除了规模，数据的初始特征对排序算法选择的影响非常大。

数据几乎有序时，插入排序是最优解，时间复杂度可以接近O(n)。这在实际业务中经常遇到：比如日志文件本身按时间追加写入，大部分时间戳已经有序，只有少量乱序记录，插入排序处理这种场景效率极高。

数据取值范围有限（比如年龄、分数、枚举值）时，计数排序是最佳选择。O(n+k)的线性时间能让其他O(n log n)算法望尘莫及。

数据是浮点数或者字符串时，计数排序和基数排序都不适用，应该直接用基于比较的排序。浮点数排序要特别注意NaN和-0的问题，JavaScript的Array.prototype.sort就有过相关坑。

数据中存在大量重复值时，三路快排（将数组分为小于、等于、大于基准三个区）比普通快排更高效。它避免了递归处理大量等同值区间，荷兰国旗问题的解法就是这个思路。

5.3 工程中的混合策略

工程实践很少只用一种排序算法。最优方案通常是组合策略。

一个典型的混合策略是"快排+插入排序"：递归到小区间就用插入排序，这样既利用快排的高效划分，又避免小规模递归的开销。Java的Arrays.sort对基本类型就采用类似策略，还结合了双轴快排。

另一个实用组合是"快排+堆排序"：当快排的递归深度超过某个阈值时，剩余部分改用堆排序。这是因为递归过深意味着划分极度不平衡，快排正在退化，此时堆排序的O(n log n)最坏保证能兜底。这个策略叫Introsort（内省排序），C++标准库的std::sort就是用它实现的。

Timsort是另一种值得了解的高级混合排序：它利用数据中天然存在的有序片段（run），用归并思想合并这些片段。它在处理"部分有序"的真实数据时表现极佳，Python和Java对象排序用的都是它。

6. 常见问题与排查技巧实录

6.1 边界条件导致的野指针问题

排序代码的崩溃绝大多数发生在边界条件上。我调试过很多次这类问题，总结出一个排查套路：用最小用例手动跑一遍。

比如排序三个元素[3, 1, 2]，在纸上画出每一步的数组状态、指针位置、递归调用顺序。这个办法看起来笨，但能快速定位是哪一步指针越界或者哪个递归分支错了。特别是快排，边界条件一旦写错，最后的结果是死循环或者栈溢出。

另一个实用技巧是开启AddressSanitizer编译选项。在GCC或Clang下加-fsanitize=address编译，运行时能自动捕获越界访问和非法内存操作，比瞎猜快得多。

6.2 稳定性误区

很多人对稳定性的理解停留在"相同元素顺序不变"这层，但实际工程里稳定性带来的问题往往很隐蔽。

我遇到过的一个典型案例是：先按用户名排序，再按注册时间排序，期望得到同一天注册的用户按用户名排列。如果第二次排序用的是快排，由于快排不稳定，相同注册时间的用户顺序可能被打乱，结果完全不符合预期。正确的做法是第二次排序用归并排序，或者把"注册时间"和"用户名"合并成一个复合排序键一次排完。

还有一个容易忽略的点：稳定性对"相邻关系"敏感。比如你正在处理事件流，相同时间戳的事件必须保持原始到达顺序，此时任何不稳定的排序都是错的。域名解析、共识算法、消息队列场景都有类似的要求。

6.3 性能测试的正确姿势

做排序性能测试时，最容易犯的错误是数据样本单一。我见过有人只测试了随机分布的数据就下结论"快排比归并快30%"，这非常不严谨。

正确做法是三组数据都测：随机分布、几乎有序、大量重复值。几乎有序时插入排序和Timsort会表现出碾压性优势；大量重复值时三路快排优势明显；随机分布时快排和堆排序的对比才接近真实。

测试时还要注意：同一组数据不能让多个排序算法共享，因为第一次排序已经把数据排好了，后续算法测的都是"几乎有序"的输入。正确做法是每个算法都用自己的独立副本，或者每次测试前重新洗牌。这个坑很基础，但真有人犯。

另外，性能测试要排除编译优化和热缓存的影响。C语言代码编译时加-O2是基本操作，否则你测的是调试版性能，没有任何参考意义。建议每个算法测多次取中位数，避免一次运行的偶然抖动。

6.4 几个容易被忽视的实战技巧

最后分享几个我从实际项目中攒下来的小技巧。

第一个技巧是：排序前尽量先检查数据是否需要排序。如果数据已经有序（比如数据库查出来默认就是按主键排的），直接跑O(n log n)算法是浪费。一个O(n)的检查可以避免大量无谓排序。

第二个技巧是：优先使用标准库提供的排序，而不是自己造轮子。C标准库的qsort、C++的std::sort、Java的Arrays.sort，这些实现都经过了极其充分的测试和优化，通常比你手写的版本更可靠、更快。你的排序代码只在业务排序逻辑特殊时才需要手写。

第三个技巧是：排序如果发生在内存数据上，要警惕"排序导致缓存失效"。大数据结构体数组在排序时，每次交换都会触发缓存行失效。可以考虑先建立一个索引数组，只对索引排序，最后再按索引重排原始数据。这样前期交换的是小整数，缓存友好度大幅提升。

第四个技巧是给排序算法加上日志钩子。在写递归排序时，打印每次递归的left和right值，以及划分后的基准位置。这能帮你快速发现递归是否无限、边界是否收敛。当然生产环境一定要去掉这些日志，它们的开销是致命的。

这些技巧看起来零碎，但真到排查线上问题时会发现，节省的时间不是一个量级的。排序算法要学透，理论是骨架，实践才是血肉。希望这篇能把你的排序算法知识体系补完整，下次遇到排序问题，不管是面试题还是线上故障，都能从容应对。