八大内部排序算法详解：源码、复杂度与工程选型

前阵子帮朋友重构一个数据统计模块，两万多条记录做个排序，他随手写了个冒泡，接口响应直接从 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 和 b，a 在 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] 和 [mid+1, 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 随机整数的大致实测结果：

从这个结果里能提炼出几条很实在的选型经验：

• 数据量小于几十条时，不用纠结，直接插入排序，代码短而且实际速度很快。
• 普通业务数据排序，优先用语言内置的排序函数，它们内部基本都做了快排 + 堆排序 + 插入排序的多策略混合。
• 有稳定性要求或者数据不是基本类型（比如按对象的多个字段排序）时，归并排序是最稳妥的选择。
• 内存紧张又有大量数据要排序，堆排序是兜底方案。
• 数据是非负整数且分布范围有限，基数排序可以秒杀所有比较排序。

快速排序在随机数据上的速度优势很明显，但它就像一把锋利的刀，用好了效率极高，用不好（比如固定取第一个元素当枢轴却遇到有序数据）就会切到自己的手。

7. 我自己在实际选型中的几个习惯

最后分享几个我踩坑之后沉淀下来的习惯，不一定适合所有场景，但至少能帮你避开那些常见的雷。

第一，能用系统自带的排序接口就不要手写。C 的 qsort、C++ 的 std::sort、Java 的 Arrays.sort，这些库函数经历过大量的工程优化，适配了各种边界情况，绝大多数场景直接调就对了。手写排序算法最容易出问题的不是算法本身，而是边界条件：数组长度为零、只有一个元素、元素重复、数据量极大导致递归栈溢出，这些坑库函数早就帮你填平了。

第二，遇到性能问题不要先甩锅给排序算法。先确认瓶颈到底是不是排序，很多时候是数据读取方式、内存拷贝或者循环里不必要的打印拖慢了整体时间。我那位朋友的接口从 7 秒降到几十毫秒，不只是换了排序算法，还顺手把日志打印和重复分配内存的问题一起解决了。

第三，学习排序算法时要抓主线。我的建议是把插入排序、归并排序、快速排序这三个的源码吃透，它们分别代表了增量、分治和分区交换三种基础思想。剩下五种都是在这三个思想上做的变形或优化。面试中让你手写排序，十有八九也是这三者之一。

第四，如果你要在真实项目里手写快排，务必加上三数取中和小数区间切换插入排序两个优化，否则所谓的"快速排序"在有序数据面前会很难堪。这些都是我在实际开发中实实在在踩过的坑，写出来给你当个参考。