排序算法这东西面试要问、项目要用、考试要考但真正能把常见几种排序用C干净利落地写出来、并且说清楚每种适用场景的人其实没想象中多。我见过太多人背得出快排的平均复杂度是O(n log n)但一让他手写一个不会退化的快排或者解释清楚归并排序为什么能稳定、堆排序的建堆为什么是O(n)就开始含糊了。这篇内容就是冲着这个来的——把冒泡、插入、选择、希尔、归并、快速、堆排序这七种常用排序算法的C实现从头到尾捋一遍每种都给出可编译运行的代码同时把实现里的关键决策、容易踩的坑、以及实际工程里怎么选讲透。不管你是正在准备技术面试还是写业务代码时需要手写一个排序或者纯粹想把算法基础打扎实这篇都能直接拿来参考。1. 先把排序算法的评价维度定清楚在动手写代码之前有几个评价维度必须先明确否则你写完也不知道自己写得好不好面试官问你为什么选这个你也答不上来。1.1 时间复杂度不只是看平均情况大多数人评价一个排序算法第一反应就是平均时间复杂度是多少。这个当然重要但远远不够。你需要同时关注三个维度最好情况、最坏情况、平均情况。为什么最坏情况这么关键因为工程里你没法保证输入数据永远随机。比如快速排序如果每次选的基准值都是当前区间的最小值或最大值那它就会退化成O(n²)这在处理已经有序的数据时特别容易发生。而插入排序恰恰相反它在数据接近有序时能跑到O(n)这就是为什么很多标准库的排序实现会在小数组上切换到插入排序。1.2 空间复杂度和稳定性同样不能忽略空间复杂度决定了你的算法能不能原地跑。冒泡、插入、选择、希尔、堆排序都是原地排序额外空间O(1)归并排序需要O(n)的辅助数组快速排序虽然是原地分区但递归调用栈需要O(log n)到O(n)的空间。稳定性指的是相等元素的相对顺序在排序后是否保持不变。这一点在实际业务里经常被忽视直到你发现按年龄排序后同年龄的人原来的录入顺序被打乱了才追悔莫及。稳定的排序有冒泡、插入、归并不稳定的有选择、希尔、快速、堆排序。下面这张表把七种算法的核心指标一次性列清楚建议收藏算法最好平均最坏空间稳定性冒泡排序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 log n)取决于增量O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定注意希尔排序的时间复杂度跟增量序列的选择强相关表中给的是常见增量下的参考值不是严格数学结论。1.3 为什么还要学这些过时的算法有人会问C标准库的std::sort已经足够好了为什么还要自己实现这些原因有三第一面试和考试确实会考这是硬门槛第二理解这些算法的思想能帮你写出更好的业务代码比如归并排序的分治思想在统计逆序对、外部排序里都有直接应用第三某些特殊场景下你需要定制排序逻辑比如对链表排序时归并排序是最优选择对海量数据做外部排序时也离不开归并的思路。所以这些算法不是过时而是基础基础不牢上层的东西都是空中楼阁。2. 三种O(n²)排序的实现与取舍冒泡、插入、选择这三种排序时间复杂度都是O(n²)看起来很菜但它们的实现细节里藏着不少值得琢磨的东西而且插入排序在实际工程中出场率极高。2.1 冒泡排序加一个提前退出标志冒泡排序的核心思路是相邻元素两两比较大的往后挪每一轮把当前未排序部分的最大值冒到末尾。最基础的写法是双重循环但这样即使数组已经有序也要跑满O(n²)。加一个swapped标志如果某一轮没有发生任何交换说明数组已经有序直接退出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; } }这个优化让冒泡排序在最好情况下达到O(n)。内层循环的边界是n - 1 - i因为每轮结束后末尾的i1个元素已经有序不需要再比较。这个细节很多人写的时候会写成n - 1虽然结果正确但多做了无用功。2.2 插入排序小数组上的王者插入排序的思路是维护一个有序的前缀每次把当前元素插入到前面有序部分的正确位置。它的实现有一个很优雅的写法用挪位代替交换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; } }为什么说插入排序是小数组上的王者因为当n比较小比如小于16或32时插入排序的常数因子极小实际跑起来比快速排序还快。这就是为什么很多标准库的排序实现在递归到小数组时会切换到插入排序。另外插入排序对近乎有序的数据极其高效接近O(n)。我在实际项目里处理日志按时间戳排序时因为日志本身基本有序用插入排序比快排还快。2.3 选择排序交换次数最少但永远不稳定选择排序每轮从未排序部分选出最小值放到已排序部分的末尾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次交换这在交换成本很高的场景下有意义。但它无论数据是否有序都要跑满O(n²)而且不稳定。举个例子序列[5a, 5b, 2]第一轮把2和5a交换变成[2, 5b, 5a]两个5的相对顺序就变了。所以如果你需要稳定性选择排序直接排除。3. 希尔排序插入排序的进化版希尔排序是插入排序的改进核心思想是先用较大的增量对相隔较远的元素进行插入排序让数组变得基本有序再逐步缩小增量最后增量为1时做一次标准插入排序。因为此时数组已经基本有序最后这趟插入排序接近O(n)。3.1 增量序列的选择直接决定性能希尔排序的性能高度依赖增量序列。最常用的是希尔本人提出的n/2, n/4, ..., 1实现简单但最坏情况仍是O(n²)。更好的是Knuth序列1, 4, 13, 40, ...即h 3*h 1最坏情况能到O(n^(3/2))。下面用Knuth序列实现void shellSort(int arr[], int n) { int h 1; while (h n / 3) h 3 * h 1; while (h 1) { for (int i h; i n; i) { int key arr[i]; int j i - h; while (j 0 arr[j] key) { arr[j h] arr[j]; j - h; } arr[j h] key; } h / 3; } }3.2 为什么希尔排序不稳定希尔排序在跨增量比较时相等元素可能被交换到不同位置破坏了相对顺序。比如[3a, 3b, 1]增量为2时3a和1比较交换变成[1, 3b, 3a]两个3的顺序就反了。所以希尔排序虽然性能比插入排序好但牺牲了稳定性。实际工程里如果你既想要比O(n²)快、又想要原地排序、还不太在乎稳定性希尔排序是个不错的折中选择代码量比归并和快排都少。4. 归并排序稳定排序的最优解归并排序是分治思想的经典应用把数组一分为二分别排序再合并两个有序数组。它的时间复杂度稳定在O(n log n)而且是稳定的代价是需要O(n)的额外空间。4.1 递归实现与合并逻辑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; }合并逻辑里有个关键细节if (arr[i] arr[j])用的是小于等于这保证了稳定性。如果写成小于相等时就会优先取右边的元素稳定性就没了。另外mid left (right - left) / 2而不是(left right) / 2是为了防止left和right都很大时整数溢出这个习惯要养成。4.2 归并排序在链表和外部排序中的独特价值归并排序对数组需要O(n)额外空间但对链表排序时它可以做到O(1)额外空间用快慢指针找中点然后合并两个有序链表。这是链表排序的最优方案因为链表不支持随机访问快排和堆排都不好使。另外处理海量数据的外部排序核心也是归并——把大文件切成小块分别排序后写回磁盘再做多路归并。所以归并排序绝不是只会考试的算法它的思想在工程里无处不在。5. 快速排序工程中最常用的排序快速排序是实践中最常用的排序算法平均O(n log n)常数因子小原地排序。但它的实现细节最多坑也最多。5.1 分区逻辑Hoare分区与Lomuto分区最常见的Lomuto分区以最后一个元素为基准int partitionLomuto(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; }Lomuto分区好理解但在数组已经有序时会退化成O(n²)因为每次基准都是最大值。Hoare分区用双指针从两端向中间扫描交换逆序对效率更高交换次数更少int partitionHoare(int arr[], int low, int high) { int pivot arr[low (high - low) / 2]; int i low - 1, j high 1; while (true) { do { i; } while (arr[i] pivot); do { --j; } while (arr[j] pivot); if (i j) return j; std::swap(arr[i], arr[j]); } }5.2 三数取中与随机化防止退化的关键要防止快排退化核心是让基准值尽量接近中位数。两种常用策略三数取中取首、中、尾三个元素的中位数作为基准和随机化随机选一个元素与首元素交换。三数取中在处理部分有序数据时效果很好随机化则能有效对抗恶意构造的数据。实际工程里std::sort用的是Introspective Sort内省排序结合了快排、堆排和插入排序递归深度超过2*log n时切换到堆排防止退化小数组切换到插入排序减少递归开销。5.3 快排的递归深度与尾递归优化快排的递归深度在最坏情况下是O(n)可能导致栈溢出。一个优化是每次先递归处理较短的一边较长的一边用循环处理尾递归优化这样递归深度能控制在O(log n)void quickSort(int arr[], int low, int high) { while (low high) { int p partitionHoare(arr, low, high); if (p - low high - p) { quickSort(arr, low, p); low p 1; } else { quickSort(arr, p 1, high); high p; } } }这个技巧在处理百万级数据时特别重要我踩过一次坑对一个接近有序的百万数组用朴素快排直接栈溢出崩溃后来加上尾递归优化才稳定。6. 堆排序原地且最坏也是O(n log n)堆排序利用二叉堆的性质先建大顶堆然后不断把堆顶最大值与末尾交换再调整堆。它的最大优势是最坏情况也是O(n log n)且原地排序空间O(1)。6.1 建堆为什么是O(n)而不是O(n log n)很多人以为建堆是O(n log n)其实自底向上的建堆是O(n)。原因在于从最后一个非叶子节点开始向下调整大部分节点都在底层调整高度很小。严格证明是高度为h的节点有n/2^(h1)个每个调整代价O(h)求和得到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); } }6.2 堆排序为什么实际比快排慢虽然堆排序最坏是O(n log n)但实际跑起来通常比快排慢。原因是堆排序的访问模式对CPU缓存不友好——它跳跃式访问数组元素缓存命中率低。而快排是顺序访问缓存友好。所以工程里std::sort默认用快排内省排序只有在递归过深时才切换到堆排。这个理论最优不等于实践最优的例子很值得记住。7. 实际工程里到底该怎么选把七种算法都实现一遍之后真正的问题来了实际写代码时怎么选我的经验是分场景小数组n 32直接用插入排序常数小实际最快。需要稳定性用归并排序或者std::stable_sort。一般情况用std::sort它是内省排序兼顾了性能和抗退化。链表排序用归并排序O(1)额外空间。内存极度受限用堆排序原地且最坏O(n log n)。数据近乎有序用插入排序接近O(n)。还有一个容易被忽视的点不要自己手写排序去替代std::sort除非你有明确的特殊需求。标准库的实现经过大量优化和测试比你自己写的快排更稳、更快、更安全。手写排序的价值在于理解原理和应对面试而不是在生产代码里炫技。最后分享一个我调试排序代码的实用技巧写一个checkSorted函数每次排序后验证结果再配合随机数据生成器做压力测试。很多边界bug比如数组长度为0或1、有大量重复元素都是这样测出来的。特别是快排用全相同元素的数组测一下如果分区逻辑写错很容易死循环或栈溢出。 
长河君 · 2026/10/20 23:46:21 · 阅读 1.2k C++七种排序算法详解：从原理到工程实践
排序算法这东西面试要问、项目要用、考试要考但真正能把常见几种排序用C干净利落地写出来、并且说清楚每种适用场景的人其实没想象中多。我见过太多人背得出快排的平均复杂度是O(n log n)但一让他手写一个不会退化的快排或者解释清楚归并排序为什么能稳定、堆排序的建堆为什么是O(n)就开始含糊了。这篇内容就是冲着这个来的——把冒泡、插入、选择、希尔、归并、快速、堆排序这七种常用排序算法的C实现从头到尾捋一遍每种都给出可编译运行的代码同时把实现里的关键决策、容易踩的坑、以及实际工程里怎么选讲透。不管你是正在准备技术面试还是写业务代码时需要手写一个排序或者纯粹想把算法基础打扎实这篇都能直接拿来参考。1. 先把排序算法的评价维度定清楚在动手写代码之前有几个评价维度必须先明确否则你写完也不知道自己写得好不好面试官问你为什么选这个你也答不上来。1.1 时间复杂度不只是看平均情况大多数人评价一个排序算法第一反应就是平均时间复杂度是多少。这个当然重要但远远不够。你需要同时关注三个维度最好情况、最坏情况、平均情况。为什么最坏情况这么关键因为工程里你没法保证输入数据永远随机。比如快速排序如果每次选的基准值都是当前区间的最小值或最大值那它就会退化成O(n²)这在处理已经有序的数据时特别容易发生。而插入排序恰恰相反它在数据接近有序时能跑到O(n)这就是为什么很多标准库的排序实现会在小数组上切换到插入排序。1.2 空间复杂度和稳定性同样不能忽略空间复杂度决定了你的算法能不能原地跑。冒泡、插入、选择、希尔、堆排序都是原地排序额外空间O(1)归并排序需要O(n)的辅助数组快速排序虽然是原地分区但递归调用栈需要O(log n)到O(n)的空间。稳定性指的是相等元素的相对顺序在排序后是否保持不变。这一点在实际业务里经常被忽视直到你发现按年龄排序后同年龄的人原来的录入顺序被打乱了才追悔莫及。稳定的排序有冒泡、插入、归并不稳定的有选择、希尔、快速、堆排序。下面这张表把七种算法的核心指标一次性列清楚建议收藏算法最好平均最坏空间稳定性冒泡排序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 log n)取决于增量O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定注意希尔排序的时间复杂度跟增量序列的选择强相关表中给的是常见增量下的参考值不是严格数学结论。1.3 为什么还要学这些过时的算法有人会问C标准库的std::sort已经足够好了为什么还要自己实现这些原因有三第一面试和考试确实会考这是硬门槛第二理解这些算法的思想能帮你写出更好的业务代码比如归并排序的分治思想在统计逆序对、外部排序里都有直接应用第三某些特殊场景下你需要定制排序逻辑比如对链表排序时归并排序是最优选择对海量数据做外部排序时也离不开归并的思路。所以这些算法不是过时而是基础基础不牢上层的东西都是空中楼阁。2. 三种O(n²)排序的实现与取舍冒泡、插入、选择这三种排序时间复杂度都是O(n²)看起来很菜但它们的实现细节里藏着不少值得琢磨的东西而且插入排序在实际工程中出场率极高。2.1 冒泡排序加一个提前退出标志冒泡排序的核心思路是相邻元素两两比较大的往后挪每一轮把当前未排序部分的最大值冒到末尾。最基础的写法是双重循环但这样即使数组已经有序也要跑满O(n²)。加一个swapped标志如果某一轮没有发生任何交换说明数组已经有序直接退出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; } }这个优化让冒泡排序在最好情况下达到O(n)。内层循环的边界是n - 1 - i因为每轮结束后末尾的i1个元素已经有序不需要再比较。这个细节很多人写的时候会写成n - 1虽然结果正确但多做了无用功。2.2 插入排序小数组上的王者插入排序的思路是维护一个有序的前缀每次把当前元素插入到前面有序部分的正确位置。它的实现有一个很优雅的写法用挪位代替交换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; } }为什么说插入排序是小数组上的王者因为当n比较小比如小于16或32时插入排序的常数因子极小实际跑起来比快速排序还快。这就是为什么很多标准库的排序实现在递归到小数组时会切换到插入排序。另外插入排序对近乎有序的数据极其高效接近O(n)。我在实际项目里处理日志按时间戳排序时因为日志本身基本有序用插入排序比快排还快。2.3 选择排序交换次数最少但永远不稳定选择排序每轮从未排序部分选出最小值放到已排序部分的末尾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次交换这在交换成本很高的场景下有意义。但它无论数据是否有序都要跑满O(n²)而且不稳定。举个例子序列[5a, 5b, 2]第一轮把2和5a交换变成[2, 5b, 5a]两个5的相对顺序就变了。所以如果你需要稳定性选择排序直接排除。3. 希尔排序插入排序的进化版希尔排序是插入排序的改进核心思想是先用较大的增量对相隔较远的元素进行插入排序让数组变得基本有序再逐步缩小增量最后增量为1时做一次标准插入排序。因为此时数组已经基本有序最后这趟插入排序接近O(n)。3.1 增量序列的选择直接决定性能希尔排序的性能高度依赖增量序列。最常用的是希尔本人提出的n/2, n/4, ..., 1实现简单但最坏情况仍是O(n²)。更好的是Knuth序列1, 4, 13, 40, ...即h 3*h 1最坏情况能到O(n^(3/2))。下面用Knuth序列实现void shellSort(int arr[], int n) { int h 1; while (h n / 3) h 3 * h 1; while (h 1) { for (int i h; i n; i) { int key arr[i]; int j i - h; while (j 0 arr[j] key) { arr[j h] arr[j]; j - h; } arr[j h] key; } h / 3; } }3.2 为什么希尔排序不稳定希尔排序在跨增量比较时相等元素可能被交换到不同位置破坏了相对顺序。比如[3a, 3b, 1]增量为2时3a和1比较交换变成[1, 3b, 3a]两个3的顺序就反了。所以希尔排序虽然性能比插入排序好但牺牲了稳定性。实际工程里如果你既想要比O(n²)快、又想要原地排序、还不太在乎稳定性希尔排序是个不错的折中选择代码量比归并和快排都少。4. 归并排序稳定排序的最优解归并排序是分治思想的经典应用把数组一分为二分别排序再合并两个有序数组。它的时间复杂度稳定在O(n log n)而且是稳定的代价是需要O(n)的额外空间。4.1 递归实现与合并逻辑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; }合并逻辑里有个关键细节if (arr[i] arr[j])用的是小于等于这保证了稳定性。如果写成小于相等时就会优先取右边的元素稳定性就没了。另外mid left (right - left) / 2而不是(left right) / 2是为了防止left和right都很大时整数溢出这个习惯要养成。4.2 归并排序在链表和外部排序中的独特价值归并排序对数组需要O(n)额外空间但对链表排序时它可以做到O(1)额外空间用快慢指针找中点然后合并两个有序链表。这是链表排序的最优方案因为链表不支持随机访问快排和堆排都不好使。另外处理海量数据的外部排序核心也是归并——把大文件切成小块分别排序后写回磁盘再做多路归并。所以归并排序绝不是只会考试的算法它的思想在工程里无处不在。5. 快速排序工程中最常用的排序快速排序是实践中最常用的排序算法平均O(n log n)常数因子小原地排序。但它的实现细节最多坑也最多。5.1 分区逻辑Hoare分区与Lomuto分区最常见的Lomuto分区以最后一个元素为基准int partitionLomuto(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; }Lomuto分区好理解但在数组已经有序时会退化成O(n²)因为每次基准都是最大值。Hoare分区用双指针从两端向中间扫描交换逆序对效率更高交换次数更少int partitionHoare(int arr[], int low, int high) { int pivot arr[low (high - low) / 2]; int i low - 1, j high 1; while (true) { do { i; } while (arr[i] pivot); do { --j; } while (arr[j] pivot); if (i j) return j; std::swap(arr[i], arr[j]); } }5.2 三数取中与随机化防止退化的关键要防止快排退化核心是让基准值尽量接近中位数。两种常用策略三数取中取首、中、尾三个元素的中位数作为基准和随机化随机选一个元素与首元素交换。三数取中在处理部分有序数据时效果很好随机化则能有效对抗恶意构造的数据。实际工程里std::sort用的是Introspective Sort内省排序结合了快排、堆排和插入排序递归深度超过2*log n时切换到堆排防止退化小数组切换到插入排序减少递归开销。5.3 快排的递归深度与尾递归优化快排的递归深度在最坏情况下是O(n)可能导致栈溢出。一个优化是每次先递归处理较短的一边较长的一边用循环处理尾递归优化这样递归深度能控制在O(log n)void quickSort(int arr[], int low, int high) { while (low high) { int p partitionHoare(arr, low, high); if (p - low high - p) { quickSort(arr, low, p); low p 1; } else { quickSort(arr, p 1, high); high p; } } }这个技巧在处理百万级数据时特别重要我踩过一次坑对一个接近有序的百万数组用朴素快排直接栈溢出崩溃后来加上尾递归优化才稳定。6. 堆排序原地且最坏也是O(n log n)堆排序利用二叉堆的性质先建大顶堆然后不断把堆顶最大值与末尾交换再调整堆。它的最大优势是最坏情况也是O(n log n)且原地排序空间O(1)。6.1 建堆为什么是O(n)而不是O(n log n)很多人以为建堆是O(n log n)其实自底向上的建堆是O(n)。原因在于从最后一个非叶子节点开始向下调整大部分节点都在底层调整高度很小。严格证明是高度为h的节点有n/2^(h1)个每个调整代价O(h)求和得到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); } }6.2 堆排序为什么实际比快排慢虽然堆排序最坏是O(n log n)但实际跑起来通常比快排慢。原因是堆排序的访问模式对CPU缓存不友好——它跳跃式访问数组元素缓存命中率低。而快排是顺序访问缓存友好。所以工程里std::sort默认用快排内省排序只有在递归过深时才切换到堆排。这个理论最优不等于实践最优的例子很值得记住。7. 实际工程里到底该怎么选把七种算法都实现一遍之后真正的问题来了实际写代码时怎么选我的经验是分场景小数组n 32直接用插入排序常数小实际最快。需要稳定性用归并排序或者std::stable_sort。一般情况用std::sort它是内省排序兼顾了性能和抗退化。链表排序用归并排序O(1)额外空间。内存极度受限用堆排序原地且最坏O(n log n)。数据近乎有序用插入排序接近O(n)。还有一个容易被忽视的点不要自己手写排序去替代std::sort除非你有明确的特殊需求。标准库的实现经过大量优化和测试比你自己写的快排更稳、更快、更安全。手写排序的价值在于理解原理和应对面试而不是在生产代码里炫技。最后分享一个我调试排序代码的实用技巧写一个checkSorted函数每次排序后验证结果再配合随机数据生成器做压力测试。很多边界bug比如数组长度为0或1、有大量重复元素都是这样测出来的。特别是快排用全相同元素的数组测一下如果分区逻辑写错很容易死循环或栈溢出。