排序算法这东西，面试要问、项目要用、考试要考，但真正能把常见几种排序用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，因为每轮结束后末尾的i+1个元素已经有序，不需要再比较。这个细节很多人写的时候会写成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^(h+1)个，每个调整代价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、有大量重复元素）都是这样测出来的。特别是快排，用全相同元素的数组测一下，如果分区逻辑写错，很容易死循环或栈溢出。
