1. 排序算法到底在排什么从一次性能翻车说起排序这件事很多刚接触 C 的朋友会觉得“不就是把数组从小到大排一遍吗”直到某次处理十万条数据时程序卡住不动才意识到不同排序算法之间的差距能有多大。我最早写业务代码时也踩过这个坑一个统计模块需要对一批记录按时间戳排序数据量小的时候用冒泡排序毫无感觉等数据涨到几十万条页面直接卡死。后来换成标准库的排序接口同样的数据量瞬间就跑完了。这件事让我明白排序算法的选择不是学术问题而是实打实的工程问题。这篇文章围绕 C 中常见的几种排序算法展开包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序和堆排序。我会把每种算法的核心思路、代码实现、时间空间复杂度、适用场景讲清楚同时补充大量实际编码中才会遇到的细节比如边界条件怎么处理、递归深度怎么控制、什么情况下该用稳定排序。内容适合正在学数据结构与算法的同学也适合工作几年但想回头把基础打扎实的开发者。读完之后你至少能做到两件事第一能手写这些排序算法并解释每一步在干什么第二能根据数据规模和特性快速判断该用哪种排序。需要先说明一点C 标准库已经提供了std::sort、std::stable_sort等成熟接口实际项目中优先用标准库。但理解底层排序算法的价值在于当标准库不满足需求时比如需要自定义比较逻辑、需要部分排序、需要处理特殊数据分布你能自己写出合适的实现。而且排序算法是理解分治、递归、堆结构等更复杂算法的基石跳过它直接调库后面学其他东西会越来越吃力。2. 排序算法的整体分类与选型思路2.1 按时间复杂度划分的三个梯队排序算法最直观的分类方式就是看时间复杂度。第一梯队是 O(n²) 级别的包括冒泡排序、选择排序和插入排序。这类算法的特点是实现简单、代码短但数据量一大就明显吃力。第二梯队是 O(n log n) 级别的包括希尔排序平均情况、归并排序、快速排序和堆排序这是实际工程中最常用的档次。第三梯队是理论上的 O(n) 级别比如计数排序、基数排序、桶排序但它们对数据有额外要求不是通用排序。我个人的经验是数据量在一千以内O(n²) 的算法和 O(n log n) 的算法差距还不明显甚至因为常数因子小插入排序有时还更快。但数据量超过一万差距就迅速拉开。到了十万级别O(n²) 的算法基本不能用。所以选型的第一判断依据就是数据规模。2.2 稳定性一个容易被忽略但很关键的属性稳定性指的是如果两个元素的值相等排序后它们的相对顺序是否保持不变。举个例子你有一批订单记录先按金额排序再按时间排序。如果第二次排序是稳定的那么金额相同的订单会保持第一次排序后的时间顺序如果不稳定这个顺序就可能被打乱。稳定的排序算法有冒泡排序、插入排序、归并排序、计数排序、基数排序。不稳定的有选择排序、快速排序、堆排序、希尔排序。实际业务中当你需要多关键字排序时稳定性就非常重要。我见过有同事用快速排序做多级排序结果第二级排序把第一级的结果打乱了排查了半天才发现是稳定性问题。2.3 原地排序与额外空间开销原地排序指的是不需要额外的大量辅助空间只用到常数级别的临时变量。冒泡、选择、插入、希尔、快速、堆排序都是原地排序。归并排序需要 O(n) 的额外空间来合并两个有序子数组这是它最大的“缺点”但换来了稳定性和稳定的 O(n log n) 性能。在内存紧张的场景下比如嵌入式设备或者处理超大规模数据额外空间开销就是一个必须考虑的因素。归并排序虽然好但如果内存不够就得考虑其他方案。2.4 一张表看清各算法核心指标算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性是否原地冒泡排序O(n²)O(n²)O(n)O(1)稳定是选择排序O(n²)O(n²)O(n²)O(1)不稳定是插入排序O(n²)O(n²)O(n)O(1)稳定是希尔排序O(n^1.3)O(n²)O(n log n)O(1)不稳定是归并排序O(n log n)O(n log n)O(n log n)O(n)稳定否快速排序O(n log n)O(n²)O(n log n)O(log n)不稳定是堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定是这张表建议存下来面试和实际选型都用得上。注意快速排序的空间复杂度是 O(log n)这是递归调用栈的开销不是额外数组。3. 三种基础排序冒泡、选择、插入的细节与坑3.1 冒泡排序为什么它是最慢的之一冒泡排序的思路很直观每一轮比较相邻的两个元素如果前一个比后一个大就交换这样每一轮结束最大的元素就像气泡一样“浮”到了末尾。代码实现如下void bubbleSort(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; } }这里有个优化点加一个swapped标志。如果某一轮没有发生任何交换说明数组已经有序可以直接退出。这个优化让冒泡排序在最好情况下数组已经有序达到 O(n)。但即便如此冒泡排序的平均和最坏情况仍然是 O(n²)而且交换操作频繁实际性能在 O(n²) 算法里通常是最差的。我实测过对一万个随机整数排序冒泡排序大概需要几百毫秒而插入排序只要几十毫秒。差距主要来自冒泡排序的交换次数太多每次交换涉及三次赋值。所以除非是教学演示实际项目中我不建议用冒泡排序。3.2 选择排序交换次数最少但比较次数固定选择排序的思路是每一轮从未排序区间里找到最小的元素放到已排序区间的末尾。代码如下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]); } } }选择排序的特点是交换次数最少最多 n-1 次交换。但比较次数固定是 n(n-1)/2不管数据是否已经有序。所以它的最好、最坏、平均时间复杂度都是 O(n²)。这个特性意味着如果数据本身接近有序选择排序不会因此变快反而不如插入排序。选择排序还有一个容易被忽略的问题它是不稳定的。举个例子序列[5a, 5b, 2]第一轮找到最小值 2和第一个 5a 交换得到[2, 5b, 5a]两个 5 的相对顺序变了。如果业务需要稳定性选择排序不能用。3.3 插入排序小规模数据的最优解插入排序的思路是把数组分成已排序和未排序两部分每次从未排序部分取第一个元素插入到已排序部分的正确位置。代码如下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; } }插入排序在数据接近有序时非常快最好情况是 O(n)。而且它的常数因子小对于小规模数据比如 n 50插入排序往往比快速排序还快。这也是为什么很多标准库的排序实现会在递归到小数组时切换到插入排序。实操心得插入排序的while循环里arr[j] key这个比较决定了稳定性。如果写成相等元素会被交换稳定性就被破坏了。需要稳定排序时一定要注意这个细节。3.4 三种基础排序的实测对比我做过一组实测用随机生成的整数数组分别用三种算法排序记录耗时数据规模冒泡排序选择排序插入排序1000约 3ms约 2ms约 1ms5000约 80ms约 50ms约 25ms10000约 320ms约 200ms约 100ms50000约 8000ms约 5000ms约 2500ms可以看到插入排序在三种基础排序里始终最快选择排序次之冒泡排序最慢。数据量到五万时三种算法都已经明显吃力了。所以我的建议是小规模数据用插入排序中等以上规模直接上 O(n log n) 的算法。4. 进阶排序希尔、归并、快速、堆的实现与取舍4.1 希尔排序插入排序的增强版希尔排序是插入排序的改进版核心思想是先用较大的步长对数组进行分组插入排序让数组变得“基本有序”然后逐步缩小步长最后用步长为 1 的插入排序收尾。代码如下void shellSort(int arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { 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; } } }希尔排序的时间复杂度取决于步长序列的选择。上面用的是最简单的折半步长平均复杂度大约 O(n^1.3)。如果用更优的步长序列比如 Hibbard 序列可以做到 O(n^1.5) 甚至更好。希尔排序的优势是代码简单、原地排序、不需要递归适合中等规模数据。但希尔排序是不稳定的因为分组插入排序会打乱相等元素的相对顺序。而且它的性能对步长序列敏感实际项目中不如直接用快速排序或归并排序省心。4.2 归并排序稳定且性能可预测归并排序采用分治思想把数组分成两半分别排序然后合并两个有序子数组。代码如下void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; std::vectorint L(n1), R(n2); 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]; int i 0, j 0, k left; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; } else { arr[k] R[j]; } } while (i n1) arr[k] L[i]; while (j n2) arr[k] R[j]; } 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); }归并排序的最大优势是性能稳定不管数据怎么分布时间复杂度都是 O(n log n)。而且它是稳定的适合多关键字排序。缺点是额外空间 O(n)在内存受限的场景下不适用。注意事项merge函数里L[i] R[j]这个判断决定了稳定性。如果写成相等元素会优先取右边的稳定性就被破坏了。另外mid left (right - left) / 2这种写法比(left right) / 2更安全可以避免整数溢出。4.3 快速排序平均最快但有最坏情况快速排序也是分治思想选一个基准元素把数组分成小于基准和大于基准两部分然后递归排序。代码如下int partition(int arr[], int low, int high) { int 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; } void quickSort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } }快速排序的平均时间复杂度是 O(n log n)而且常数因子小实际运行速度通常比归并排序和堆排序快。但它有两个问题第一最坏情况是 O(n²)当数组已经有序且每次选最后一个元素作为基准时就会触发第二递归深度在最坏情况下是 O(n)可能导致栈溢出。解决最坏情况的办法是随机选基准或者三数取中。随机选基准就是把pivot的选取改成随机位置然后和最后一个元素交换。三数取中就是取首、中、尾三个元素的中位数作为基准。这两种方法都能有效避免有序数据导致的性能退化。4.4 堆排序原地且最坏也是 O(n log 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(1)而且最坏情况也是 O(n log n)不会像快速排序那样退化。缺点是常数因子较大实际运行速度通常比快速排序慢而且不稳定。另外堆排序对缓存不友好因为访问模式是跳跃的而快速排序和归并排序都是顺序访问。4.5 四种进阶排序的选型建议场景推荐算法理由需要稳定排序归并排序唯一稳定的 O(n log n) 算法内存充足、追求稳定性能归并排序最坏也是 O(n log n)内存紧张、追求速度快速排序原地排序平均最快内存极紧张、要求最坏可控堆排序原地且最坏 O(n log n)中等规模、代码简单希尔排序实现简单不需要递归实际项目中std::sort通常采用内省排序结合了快速排序、堆排序和插入排序的优点先用快速排序递归深度超过阈值时切换到堆排序小数组用插入排序。这种混合策略兼顾了速度和最坏情况的可控性。5. 实操中踩过的坑与排查技巧5.1 边界条件数组为空或只有一个元素所有排序算法都要处理n 1的情况。冒泡、选择、插入的循环条件天然处理了这种情况但递归算法需要显式判断。比如归并排序的if (left right) return;和快速排序的if (low high)。我见过有同事写快速排序时忘了这个判断导致空数组时递归无限进行程序直接崩溃。5.2 递归深度快速排序的栈溢出风险快速排序在最坏情况下递归深度是 O(n)。对十万个有序数据排序递归深度可能达到十万层远超默认栈大小直接导致栈溢出。解决办法有两个一是随机选基准或三数取中把最坏情况概率降到极低二是用尾递归优化把递归改成循环。下面是尾递归优化的写法void quickSortTail(int arr[], int low, int high) { while (low high) { int pi partition(arr, low, high); if (pi - low high - pi) { quickSortTail(arr, low, pi - 1); low pi 1; } else { quickSortTail(arr, pi 1, high); high pi - 1; } } }这种写法每次都先递归较小的那一边较大的一边用循环处理递归深度最多 O(log n)。5.3 比较函数的严格弱序如果用自定义比较函数必须满足严格弱序即comp(a, a)必须为 false且comp(a, b)和comp(b, a)不能同时为 true。我见过有人写比较函数时用了导致std::sort行为未定义程序随机崩溃。正确的写法是用相等时返回 false。5.4 常见问题速查表问题现象可能原因解决方法程序崩溃在递归函数递归深度过大导致栈溢出改用尾递归或随机选基准排序结果不稳定使用了不稳定算法换用归并排序或插入排序有序数据排序特别慢快速排序选了固定基准随机选基准或三数取中排序后相等元素顺序乱了比较函数用了改用大数据量内存不足归并排序额外空间 O(n)换用快速排序或堆排序小数组排序反而慢递归开销大于排序本身小数组切换插入排序5.5 一个容易被忽略的优化小数组切换插入排序快速排序和归并排序在递归到小数组时递归调用的开销可能比排序本身还大。常见的优化是当子数组长度小于某个阈值比如 16 或 32时直接调用插入排序。这个优化能显著提升整体性能。标准库的std::sort就是这么做的。void quickSortOptimized(int arr[], int low, int high) { if (high - low 16) { insertionSort(arr low, high - low 1); return; } int pi partition(arr, low, high); quickSortOptimized(arr, low, pi - 1); quickSortOptimized(arr, pi 1, high); }这个阈值不是固定的需要根据实际数据测试。一般来说 8 到 32 之间效果都不错。6. 标准库排序接口的正确用法6.1 std::sort 的基本用法与自定义比较std::sort是最常用的排序接口默认升序排列#include algorithm #include vector std::vectorint nums {5, 2, 8, 1, 9}; std::sort(nums.begin(), nums.end()); // 降序排列 std::sort(nums.begin(), nums.end(), std::greaterint()); // 自定义比较按绝对值排序 std::sort(nums.begin(), nums.end(), [](int a, int b) { return std::abs(a) std::abs(b); });std::sort不保证稳定性。如果需要稳定排序用std::stable_sort它底层是归并排序时间复杂度 O(n log n)空间复杂度 O(n)。6.2 部分排序std::partial_sort 和 std::nth_element有时候不需要完全排序只需要找出前 K 个最小的元素。这时候用std::partial_sort比完全排序更高效std::vectorint nums {5, 2, 8, 1, 9, 3, 7}; std::partial_sort(nums.begin(), nums.begin() 3, nums.end()); // 前三个元素是 1, 2, 3后面的顺序不保证如果只需要找出第 K 小的元素不需要前 K 个有序用std::nth_element更快平均复杂度 O(n)std::nth_element(nums.begin(), nums.begin() 3, nums.end()); // nums[3] 是第 4 小的元素左边的都比它小右边的都比它大6.3 排序结构体时的注意事项对结构体排序时比较函数必须严格弱序。比如按年龄排序年龄相同时按姓名排序struct Person { std::string name; int age; }; std::vectorPerson people {{A, 25}, {B, 20}, {C, 25}}; std::sort(people.begin(), people.end(), [](const Person a, const Person b) { if (a.age ! b.age) return a.age b.age; return a.name b.name; });这种写法是稳定的因为年龄相同时用姓名做了二次比较。但如果只写return a.age b.age;年龄相同的元素顺序就不确定了。实操心得对结构体排序时如果比较逻辑复杂建议单独写一个比较函数或函数对象不要用匿名 lambda 写太长否则调试时很难定位问题。另外比较函数里不要做耗时操作因为排序过程中比较函数会被调用 O(n log n) 次。7. 排序算法的实际应用场景7.1 数据去重与合并排序是去重的前置步骤。对数组排序后相同的元素会相邻只需要遍历一遍就能去重。合并两个有序数组也是常见操作归并排序的merge函数可以直接复用。7.2 查找中位数与 Top K 问题找中位数可以用std::nth_element平均 O(n)。找 Top K 大的元素可以用小顶堆维护一个大小为 K 的堆遍历数组比堆顶大的就替换堆顶并调整堆。时间复杂度 O(n log K)比完全排序的 O(n log n) 更高效。7.3 任务调度与优先级队列堆排序背后的堆结构就是优先级队列的基础。std::priority_queue底层用堆实现插入和删除都是 O(log n)。任务调度、事件处理等场景都依赖这个结构。7.4 数据库索引与外部排序数据库的索引通常用 B 树但构建索引时需要对数据进行排序。当数据量超过内存时需要外部排序把数据分成若干块每块在内存中排序后写入临时文件然后多路归并。归并排序的思想在这里发挥得淋漓尽致。8. 我个人的一些经验体会写了这么多年代码排序算法给我的最大启发不是某个具体算法的实现而是“没有银弹”这个道理。快速排序平均最快但最坏情况会退化归并排序稳定且性能可预测但需要额外空间堆排序原地且最坏可控但常数因子大。每种算法都有自己的适用场景关键是根据数据规模、内存限制、稳定性要求来选。另一个体会是不要过早优化。我见过有同事在数据量只有几百条的场景下纠结用哪种排序花了大半天做性能测试结果对整体性能毫无影响。真正需要关注排序性能的场景数据量至少是万级别以上。小数据量下代码可读性比性能更重要。最后分享一个调试技巧如果排序结果不对先检查比较函数是否满足严格弱序再检查边界条件空数组、单元素、全部相等最后检查递归的终止条件。我排查过的排序 bug 里九成以上都是这三类问题。把这三个检查点记住能省下大量调试时间。