前阵子帮朋友重构一个数据统计模块两万多条记录做个排序他随手写了个冒泡接口响应直接从 200 毫秒飙到 7 秒。换成快速排序之后耗时瞬间降到几十毫秒。内部排序算法这个老话题平时没人提一到性能优化或者面试就绕不开。很多写业务代码的同学能背出八大排序的名字真到需要选型和落地时却连源码都写不完整。这篇文章把八种典型内部排序算法摆在一起源码、原理、复杂度、稳定性、适用场景全部拆开揉碎最后附上同一台机器上的实测对比。如果你正准备算法面试或者想搞清楚工程里到底该用哪种排序这篇应该能帮你省不少时间。1. 评价排序算法前先建立三把尺子排序算法不是孤立的一堆代码选型之前得先有一套评价体系。我见过太多人把快排最快挂在嘴边结果在特定数据分布下跑出 O(n²) 的灾难性性能。所以在贴源码之前先把三把尺子讲清楚。1.1 时间复杂度的三层含义最好、平均、最坏复杂度描述的是数据规模增长时的趋势不是某个具体耗时。初学者看快速排序平均 O(n log n)就以为它永远最快看冒泡排序 O(n²)就以为它一无是处这两种判断都太粗暴了。以直接插入排序为例它的最坏复杂度是 O(n²)但当输入数据基本有序时内层循环几乎不移动元素实际耗时接近 O(n)。反过来看快速排序平均情况确实优秀一旦每次选到的枢轴都是当前区间的最小值递归深度变成 n复杂度直接退化到 O(n²)这在有序或逆序数据上特别容易触发。所以评价一个排序算法必须同时看三个指标最好情况数据刚好对算法友好比如插入排序遇到接近有序的数据。平均情况随机数据下的期望表现这是工程选型最常用到的指标。最坏情况不管数据多刁钻算法都能保证的上限。1.2 空间复杂度原地排序与非原地排序的代价空间复杂度经常被忽略但它在嵌入式、移动端这类内存敏感场景里是硬指标。原地排序算法只使用 O(1) 的额外空间在原始数组上通过交换完成排序比如插入排序、冒泡排序、快速排序递归栈除外和堆排序。非原地排序需要额外的 O(n) 甚至更大空间归并排序需要一块和原数组等长的辅助数组基数排序需要桶数组。用生活里的例子类比原地排序就像在一张纸上用橡皮擦改数字非原地排序则是把内容重新抄写到另一张纸上再誊回来。前者省空间后者往往能换来稳定性或更可预测的性能。工程上如果内存很紧张堆排序是很好的兜底方案因为它既稳定地保持 O(n log n)又只消耗 O(1) 辅助空间。1.3 稳定性一个容易被忽略的工程属性稳定性的定义很简短排序前后相等元素的相对顺序保持不变。如果排序前数组里有两个值为 5 的元素 a 和 ba 在 b 前面排序后 a 仍然在 b 前面这个算法就是稳定的。为什么工程里要关心这个一个典型场景是表格的多列排序。用户先按时间列排序再按优先级列排序如果第二列排序是稳定的第一列的相对顺序就能保留。再比如商品列表先按销量排序再按价格排序稳定算法能让销量高的商品在价格相同的情况下排在前面。归并排序和插入排序是稳定的快速排序和堆排序不稳定这个属性直接决定了它们在真实业务中的适用范围。2. 插入类排序数据接近有序时的默认选项插入类排序的核心思想是逐步扩大有序区。这个思路朴素但非常有效尤其适合数据量小或者基本有序的场景。2.1 直接插入排序的源码与折半优化直接插入排序的思路可以理解为打扑克时理牌左手拿着的牌已经有序每摸一张新牌就从右往左找到合适位置插进去。用 C 语言实现非常简洁void InsertSort(int arr[], int n) { for (int i 1; i n; i) { int temp arr[i]; int j i - 1; // 从已有序区的末尾开始比较找到插入位置 while (j 0 arr[j] temp) { arr[j 1] arr[j]; // 元素后移 j--; } arr[j 1] temp; } }注意内层循环的终止条件 arr[j] temp 用的是严格大于等于的时候不移动这正是它稳定的原因。排序过程中已排序区永远在数组左端每轮把右侧第一个未排序元素插入到已排序区的正确位置。这个算法有两个明显特点。一是数据量很小时性能凶悍因为常量因子极小二是数据基本有序时接近线性时间。有一个常见的优化叫折半插入排序利用已排序区是有序数组这个条件用二分查找直接定位插入点把比较次数从 O(n) 降到 O(log n)。但移动次数没有变所以总复杂度依然是 O(n²)。2.2 希尔排序增量序列如何影响性能希尔排序是直接插入排序的改进版核心思想是跳跃式插入。先让元素以较大间隔分组排序再逐步缩小间隔间隔缩小到 1 时就是普通的插入排序。这个思路打破了插入排序只能比较相邻元素的限制让较小的元素能快速往前跳跃。void ShellSort(int arr[], int n) { // 常见的希尔增量每次折半 for (int gap n / 2; gap 0; gap / 2) { // 对每个分组做插入排序 for (int i gap; i n; i) { int temp arr[i]; int j i - gap; while (j 0 arr[j] temp) { arr[j gap] arr[j]; j - gap; } arr[j gap] temp; } } }增量序列的选择对性能影响很大。上面代码用的 gap n/2 逐步减半是 Shell 最早提出的方案最坏情况 O(n²)。Hibbard 增量2^k - 1和 Sedgewick 增量能把最坏复杂度优化到 O(n^1.3) 甚至更好。希尔排序有个值得注意的特性当间隔 gap 大于 1 时元素可能在分组间跳跃排序后相等元素的相对顺序可能被破坏所以希尔排序是不稳定的。这是它和直接插入排序之间最本质的区别之一。3. 交换类排序从最容易写错到工程首选交换类排序的核心动作是比较后交换。这一族里冒泡排序非常简单快速排序则是工程中最常用的排序之一两者对比着看很有意思。3.1 冒泡排序的提前终止优化冒泡排序的直观理解是每次把相邻元素中较大的那个往后推一轮下来最大元素像气泡一样浮到末尾。很多人觉得它简单其实它有一个特别实用的优化点引入 swapped 标记如果一整轮都没发生交换说明数组已经有序直接跳出。void BubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { Swap(arr[j], arr[j 1]); swapped 1; } } // 本趟未发生交换序列已经有序 if (!swapped) break; } }这个优化让冒泡排序在最好情况下变成 O(n)因为它能在检测到有序后立即终止。加上它只交换相邻元素相等元素不会越过彼此因此冒泡排序是稳定的。不过冒泡排序在随机数据上的平均表现依然是 O(n²)而且常数因子偏大。即使做了提前终止优化它也更适合教学演示和基本有序的小数据不适合大规模随机数据。3.2 快速排序的枢轴选择与退化防护快速排序是分治思想的典型代表。选一个元素当枢轴把比它小的放到左边、比它大的放到右边然后递归处理左右两部分。下面是我最常用的霍尔分区写法void QuickSort(int arr[], int low, int high) { if (low high) return; int pivot arr[low]; // 取区间第一个元素为枢轴 int i low, j high; while (i j) { // 从右往左找第一个小于枢轴的元素 while (i j arr[j] pivot) j--; // 把它放到枢轴左侧的空位 arr[i] arr[j]; // 从左往右找第一个大于枢轴的元素 while (i j arr[i] pivot) i; // 把它放到右侧的空位 arr[j] arr[i]; } arr[i] pivot; // 枢轴归位此时 i 即分割点 QuickSort(arr, low, i - 1); QuickSort(arr, i 1, high); }快排的性能要害在枢轴选择。上面的代码直接取第一个元素作为枢轴如果输入是已经有序的数组每轮划分都极不均匀递归深度变成 n复杂度退化到 O(n²)。这就是为什么实际工程里的快排几乎不会用取第一个元素这种朴素写法。常见的防护手段有三种三数取中从区间的首、尾、中间取三个元素用它们的中位数作为枢轴能有效避免有序数据导致的退化。随机枢轴随机选一个元素作为枢轴从概率上消除恶意数据的影响但随机数生成本身有开销。小区间切换插入排序当子区间长度小于某个阈值比如 16 或 32时不再递归调用快排而是改用它最擅长的插入排序减少递归开销。这也是 C 标准库中 std::sort 的设计思路它本质上是内省排序先走快排当递归深度过深时切换堆排序兜底小区间用插入排序收尾。理解了快排的退化机制就理解了为什么工程库的排序函数普遍不是裸快排。4. 选择类排序理解不稳定的最佳样本选择类排序的思路是每一轮从待排序区间选出最小元素放到已排序区末尾。选择排序的实现很直观堆排序则是在这个思路上的树形优化。4.1 简单选择排序的不稳定性来源简单选择排序的名字里虽然有简单二字但它有一个很有意思的性质不稳定。这里值得单独展开因为很多面试者在这个问题上栽过跟头。void SelectSort(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) { Swap(arr[i], arr[minIdx]); } } }举例解释为什么它会破坏稳定性。数组 [5a, 5b, 3]两个 5 分别记为 5a 和 5b。第一轮找到最小值 3下标是 2于是把 arr[0]5a和 arr[2]3交换数组变成 [3, 5b, 5a]。排序完成后5a 跑到了 5b 后面相等元素的相对顺序被破坏了所以它不稳定。这个例子很适合用来理解稳定性不是玄学而是由交换方式决定的。简单选择排序的比较次数固定为 O(n² / 2)移动次数较少。正因为比较次数不随数据分布变化它的最好、最坏、平均复杂度都是 O(n²)。4.2 堆排序的建堆与调整源码解析堆排序的思路是先把数组整理成一个大顶堆堆顶元素是全局最大值把它和末尾元素交换堆的长度减一再调整堆结构重新得到最大值。重复这个操作数组从后往前逐步有序。// 对以 root 为根的子树进行堆化n 表示堆的大小 void Heapify(int arr[], int n, int root) { int largest root; int l 2 * root 1; int r 2 * root 2; if (l n arr[l] arr[largest]) largest l; if (r n arr[r] arr[largest]) largest r; if (largest ! root) { Swap(arr[root], 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--) { Swap(arr[0], arr[i]); Heapify(arr, i, 0); } }建堆过程是理解堆排序的难点。为什么从 n/2 - 1 开始往前遍历因为数组作为完全二叉树时下标大于 n/2 - 1 的节点都是叶子节点叶子节点本身满足堆性质不需要调整。从最后一个非叶子节点开始从下往上处理才能保证子树的堆性质在树顶处理好之前已经建立。堆排序的时间复杂度恒为 O(n log n)这是它最大的工程优势不管数据有序还是无序性能上限都有保障。但它通常比快速排序慢一些原因在于缓存局部性差。堆排序比较和交换的数组下标是跳跃的不像插入排序和快排那样对缓存友好。堆排序同样不稳定因为堆顶元素和末尾元素交换时可能改变相等元素的相对位置。5. 归并与基数用空间换时间的代表这两类算法都不是原地排序但它们分别解决了不同维度的难题归并排序保证了最坏情况 O(n log n) 且稳定基数排序则能在特定数据条件下达到线性复杂度。5.1 归并排序的递归实现与稳定性原理归并排序采用经典的分治策略把数组从中间切成两半分别排序再把两个有序数组合并成一个有序数组。合并过程需要一块临时数组所以空间复杂度是 O(n)。// 合并两个有序子数组 [left, mid] 和 [mid1, right] void Merge(int arr[], int temp[], int left, int mid, int right) { int i left; int j mid 1; int 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 (i left; i right; i) { arr[i] temp[i]; } } void MergeSort(int arr[], int temp[], int left, int right) { if (left right) return; int mid left (right - left) / 2; MergeSort(arr, temp, left, mid); MergeSort(arr, temp, mid 1, right); Merge(arr, temp, left, mid, right); } // 统一的封装入口 void MergeSortWrapper(int arr[], int n) { int *temp (int *)malloc(n * sizeof(int)); if (temp) { MergeSort(arr, temp, 0, n - 1); free(temp); } }归并排序的稳定性体现在 Merge 函数里一行不起眼的代码当两个子数组当前元素相等时优先取左半部分的元素。因为左半部分的元素在原始数组中本来就排在右半部分之前所以相等元素的相对顺序被完整保留。对于大规模数据归并排序最稳定的特性是最坏情况也是 O(n log n)。而递归版的归并有函数调用开销也可以改成迭代版用 bottom-up 的方式逐层合并避免递归栈空间。工程上Java 的 Collections.sort 对对象数组使用归并排序一个重要原因就是对象排序场景通常要求稳定性。5.2 基数排序的桶分配过程基数排序和前面的比较排序完全不同它不直接比较两个元素的大小而是通过多次分配和收集完成排序。以整数排序为例最常用的是 LSD最低位优先先按个位分配再按十位分配依此类推。基数排序要求每次分配必须是稳定的。我用计数排序来实现桶分配这样能在一个线性扫描里完成所有桶的分发void RadixSort(int arr[], int n) { // 找到最大值决定需要处理多少位 int maxVal arr[0]; for (int i 1; i n; i) { if (arr[i] maxVal) maxVal arr[i]; } int *bucket (int *)malloc(n * sizeof(int)); // exp 表示当前处理的位权1、10、100... for (int exp 1; maxVal / exp 0; exp * 10) { int count[10] {0}; // 统计每个数字出现的次数 for (int i 0; i n; i) { count[(arr[i] / exp) % 10]; } // 累加次数转换为每个数字的起始位置 for (int i 1; i 10; i) { count[i] count[i - 1]; } // 从后往前遍历保证稳定性 for (int i n - 1; i 0; i--) { int idx (arr[i] / exp) % 10; bucket[--count[idx]] arr[i]; } // 收集回原数组 for (int i 0; i n; i) { arr[i] bucket[i]; } } free(bucket); }为什么从后往前遍历因为 count 数组累加后记录的是每个数字在当前位上的最后一个位置从后往前填充才能保证相同 digit 的元素保持它们在原数组中的相对顺序也就是稳定性。基数排序的时间复杂度是 O(d × (n r))d 是最大数字的位数r 是基数这里是十进制 10。当数字范围固定时d 是常数基数排序可以达到近似线性的效率。但它对数据类型有要求必须是可拆分为多个关键字的整数或字符串。处理负数时还需要额外处理符号位。6. 同一份数据八种排序实测对比讲了这么多理论最终还是得回到数据上来。我在一台老款 i5 台式机上做了简单测试这里分享一下测试方案和结论。注意具体数值跟机器和编译优化有关但相对趋势有很强的参考价值。6.1 测试框架设计为了让所有算法在同一个起跑线上对比我写了一个简单的 C 测试框架。核心思路是用同一份数据复制出多份副本对每个算法单独计时void CopyArray(int src[], int dst[], int n) { memcpy(dst, src, n * sizeof(int)); } // 统一接口排序函数接受原数组和长度 double TestTime(void (*sortFunc)(int[], int), int arr[], int n) { int *tmp (int *)malloc(n * sizeof(int)); CopyArray(arr, tmp, n); clock_t start clock(); sortFunc(tmp, n); clock_t end clock(); double ms (double)(end - start) * 1000 / CLOCKS_PER_SEC; free(tmp); return ms; } void QuickSortWrapper(int arr[], int n) { QuickSort(arr, 0, n - 1); } int main() { int n 100000; int *arr (int *)malloc(n * sizeof(int)); // 固定随机种子保证不同算法用同一份数据 srand(42); for (int i 0; i n; i) { arr[i] rand() % 100000; } // 依次测试 InsertSort、ShellSort、BubbleSort... printf(InsertSort: %.2f ms\n, TestTime(InsertSort, arr, n)); printf(QuickSort: %.2f ms\n, TestTime(QuickSortWrapper, arr, n)); free(arr); return 0; }我建议至少测三种数据分布完全随机数据、有序数据、逆序数据。实际测试中只测随机数据会严重误导选型因为有些算法比如插入排序在有序数据上的表现完全变样。6.2 实测结果与选型结论以下是我本机针对 100000 个 0~99999 随机整数的大致实测结果排序算法随机数据耗时相对量级基本有序数据逆序数据空间稳定性直接插入排序较慢约 2 秒级极快接近线性最慢O(1)稳定希尔排序中几十毫秒级快中O(1)不稳定冒泡排序很慢约 5 秒级快提前终止很慢O(1)稳定快速排序最快约 15~20 ms可能退化固定枢轴时可能退化O(log n) 栈不稳定简单选择排序慢约 3 秒级慢比较次数不变慢O(1)不稳定堆排序中约 25~35 ms中中O(1)不稳定归并排序中约 20~30 ms中中稳定 O(nlogn)O(n)稳定基数排序快个位数位宽时约 10 ms 内快快O(n r)稳定从这个结果里能提炼出几条很实在的选型经验数据量小于几十条时不用纠结直接插入排序代码短而且实际速度很快。普通业务数据排序优先用语言内置的排序函数它们内部基本都做了快排 堆排序 插入排序的多策略混合。有稳定性要求或者数据不是基本类型比如按对象的多个字段排序时归并排序是最稳妥的选择。内存紧张又有大量数据要排序堆排序是兜底方案。数据是非负整数且分布范围有限基数排序可以秒杀所有比较排序。快速排序在随机数据上的速度优势很明显但它就像一把锋利的刀用好了效率极高用不好比如固定取第一个元素当枢轴却遇到有序数据就会切到自己的手。7. 我自己在实际选型中的几个习惯最后分享几个我踩坑之后沉淀下来的习惯不一定适合所有场景但至少能帮你避开那些常见的雷。第一能用系统自带的排序接口就不要手写。C 的 qsort、C 的 std::sort、Java 的 Arrays.sort这些库函数经历过大量的工程优化适配了各种边界情况绝大多数场景直接调就对了。手写排序算法最容易出问题的不是算法本身而是边界条件数组长度为零、只有一个元素、元素重复、数据量极大导致递归栈溢出这些坑库函数早就帮你填平了。第二遇到性能问题不要先甩锅给排序算法。先确认瓶颈到底是不是排序很多时候是数据读取方式、内存拷贝或者循环里不必要的打印拖慢了整体时间。我那位朋友的接口从 7 秒降到几十毫秒不只是换了排序算法还顺手把日志打印和重复分配内存的问题一起解决了。第三学习排序算法时要抓主线。我的建议是把插入排序、归并排序、快速排序这三个的源码吃透它们分别代表了增量、分治和分区交换三种基础思想。剩下五种都是在这三个思想上做的变形或优化。面试中让你手写排序十有八九也是这三者之一。第四如果你要在真实项目里手写快排务必加上三数取中和小数区间切换插入排序两个优化否则所谓的快速排序在有序数据面前会很难堪。这些都是我在实际开发中实实在在踩过的坑写出来给你当个参考。