1. 排序算法到底在排什么：从一次性能翻车说起

排序算法这四个字，几乎是每个写C++的人绕不过去的一道坎。不管你是刚学完数组和循环的新手，还是已经写了几年业务代码的老手，只要碰到数据处理，排序就一定会出现。但很多人对排序的理解停留在“考试要考”“面试要问”的层面，真正到了项目里，往往就是一个std::sort丢过去，至于底层发生了什么、为什么快、什么时候会慢，一概不知。直到某一天数据量上来了，或者遇到一个特殊场景，程序直接卡死或者结果出错，才开始回头补课。

我自己就踩过这样的坑。早些年做一个日志分析的小工具，需要把几百万条记录按时间戳排序。当时想都没想就用了冒泡排序的思路去写，觉得逻辑简单不容易出错。结果跑起来之后，进度条几乎不动，等了十几分钟才处理完一小部分。后来换成快速排序，同样的数据量几秒钟就出来了。那次经历让我意识到，排序算法的选择不是学术问题，而是直接影响程序能不能用的工程问题。

这篇文章就是想把C++里常见的几种排序算法掰开揉碎讲清楚。我会从最基础的冒泡、选择、插入讲起，再到归并、快速、堆排序这些进阶内容，最后聊一聊实际项目中怎么选、怎么优化、怎么避坑。每一段代码都会给出完整的可运行版本，每一个参数都会解释为什么这么设。目标很简单：让你看完之后，不仅能写出这些排序，还能在合适的场景用合适的算法，遇到问题知道怎么排查。

适合谁看？如果你正在学C++基础，想搞明白排序到底怎么回事，这篇适合你。如果你已经工作，但每次排序都靠标准库，想深入理解底层原理，这篇也适合你。如果你正在准备技术面试，需要把常见排序的手写代码和复杂度分析吃透，那这篇更要对着一行一行看。我不打算用教科书那种定义加公式的方式来讲，而是用从业者之间交流的口吻，把每个算法的脾气秉性说清楚。

2. 基础三件套：冒泡、选择、插入的真实面目

2.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; } }

这段代码里有两个关键点经常被忽略。第一，内层循环的边界是n - 1 - i，不是n - 1。因为每一轮结束后，末尾的i个元素已经排好了，不需要再比较。第二，swapped标志位的作用是提前终止。如果某一轮没有任何交换发生，说明数组已经有序，后面的轮次全是浪费时间。我实测过，对于一个基本有序的数组，加上这个标志位之后，冒泡排序的速度能提升好几倍。

冒泡排序的时间复杂度是O(n²)，空间复杂度O(1)，稳定排序。所谓稳定，就是相等的元素在排序后相对位置不变。这个特性在某些场景下很重要，比如你先按姓名排序，再按年龄排序，如果年龄相同，希望保持姓名的顺序，那就需要稳定排序。冒泡排序满足这个条件，但它的效率实在太低了，实际项目中基本不会用。

注意：写冒泡排序的时候，千万不要把内层循环写成j < n - 1，这样虽然结果是对的，但会多出大量无意义的比较。数据量小的时候看不出来，数据量一大差距就明显了。

2.2 选择排序：交换次数最少但比较次数固定

选择排序的思路是：每一轮从未排序区间里找到最小的元素，放到已排序区间的末尾。和冒泡排序不同，选择排序的交换次数最多只有n-1次，因为每轮只交换一次。但它的比较次数是固定的，无论数组是否有序，都要比较n(n-1)/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]); } } }

选择排序有一个容易被忽视的细节：if (minIdx != i)这个判断。如果最小元素本来就在当前位置，就不需要交换。虽然多一次交换对性能影响不大，但在某些对写操作敏感的场景下（比如闪存存储），减少不必要的写入是有意义的。

选择排序是不稳定排序。举个例子，数组[5, 5, 3]，第一轮找到最小值3，和第一个5交换，变成[3, 5, 5]。原来第一个5在第二个5前面，交换后两个5的相对顺序变了。如果你需要稳定排序，选择排序就不合适。

选择排序的实际应用场景很少，但它的思想很重要。比如在数据量很小且交换成本很高的情况下，选择排序的交换次数优势就体现出来了。另外，选择排序的“找最小值”思路是堆排序的基础，理解了选择排序，后面学堆排序会轻松很多。

2.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; } }

插入排序的关键在于while循环的条件。arr[j] > key决定了排序的稳定性。如果写成arr[j] >= key，相等的元素会被移动到后面，排序就不稳定了。这一点在需要稳定排序的场景下必须注意。

插入排序的时间复杂度在最好情况下是O(n)，也就是数组已经有序的时候，每次只需要比较一次。最坏情况是O(n²)，数组完全逆序。平均情况也是O(n²)。但为什么很多标准库在数据量小的时候会用插入排序？因为它的常数因子很小，没有递归调用开销，对于n小于某个阈值（通常是16到32）的情况，插入排序比快速排序和归并排序都快。

我在实际项目里做过一个测试：对1000个随机整数排序，插入排序耗时约0.02毫秒，快速排序约0.01毫秒，差距不大。但对50个整数排序，插入排序约0.001毫秒，快速排序因为递归开销反而要0.003毫秒。所以很多高性能排序库会混合使用多种算法，小规模用插入排序，大规模用快速排序或归并排序。

实操心得：如果你需要自己实现一个排序函数，不要只写一种算法。可以设置一个阈值，比如当待排序区间长度小于16时，切换到插入排序。这个技巧在标准库的std::sort里也有体现，虽然具体实现因编译器而异，但思路是一致的。

3. 进阶算法：归并、快速、堆排序的工程细节

3.1 归并排序：稳定排序的性能担当

归并排序采用分治思想：把数组分成两半，分别排序，然后合并两个有序数组。它的时间复杂度稳定在O(n log n)，无论数据是否有序，都是这个复杂度。空间复杂度是O(n)，因为合并过程需要额外的数组空间。

void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; std::vector<int> 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); }

归并排序的稳定性由L[i] <= R[j]这个条件保证。当左右两边元素相等时，优先取左边的，这样左边元素在合并后仍然排在前面。如果写成<，稳定性就被破坏了。

归并排序最大的问题是空间开销。每次合并都要创建临时数组，递归深度是log n，总的空间复杂度是O(n)。对于内存敏感的场景，这个开销需要认真考虑。优化方法有两种：一种是在递归之前判断是否已经有序，如果arr[mid] <= arr[mid+1]，说明左右两半已经整体有序，不需要合并；另一种是使用原地归并，但实现复杂且常数因子大，实际项目中很少用。

归并排序还有一个天然优势：它非常适合外部排序。当数据量大到内存放不下时，可以把数据分成多个块，每块单独排序后写入磁盘，然后多路归并。这个思路在数据库和大数据处理中非常常见。

3.2 快速排序：平均最快但最坏情况要警惕

快速排序是实际应用中最广泛的排序算法，平均时间复杂度O(n log n)，常数因子小，原地排序不需要额外空间。但它的最坏情况是O(n²)，当每次选择的基准值都是最大或最小元素时就会触发。

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); } }

这段代码选择最后一个元素作为基准值。如果数组已经有序，每次分区都会把数组分成一个空区间和一个n-1长度的区间，递归深度变成n，时间复杂度退化为O(n²)。解决办法是随机选择基准值，或者使用三数取中法。

int medianOfThree(int arr[], int low, int high) { int mid = low + (high - low) / 2; if (arr[mid] < arr[low]) std::swap(arr[mid], arr[low]); if (arr[high] < arr[low]) std::swap(arr[high], arr[low]); if (arr[high] < arr[mid]) std::swap(arr[high], arr[mid]); std::swap(arr[mid], arr[high - 1]); return arr[high - 1]; }

三数取中法从low、mid、high三个位置取中间值作为基准，能有效避免有序数组导致的退化。实测下来，对于完全有序的数组，使用三数取中法的快速排序仍然保持O(n log n)的性能。

快速排序的另一个优化是小区间切换插入排序。当待排序区间长度小于某个阈值时，递归调用的开销超过了排序本身的开销，这时候用插入排序更划算。标准库的std::sort通常采用内省排序，结合了快速排序、堆排序和插入排序的优点。

注意：快速排序是不稳定排序。如果你需要稳定排序，要么用归并排序，要么在比较函数里加入额外的区分条件。比如对结构体排序时，如果主要字段相等，就比较次要字段，确保没有两个元素完全相等。

3.3 堆排序：原地排序的稳定选择

堆排序利用二叉堆的性质进行排序。先把数组构建成最大堆，然后依次把堆顶元素（最大值）和末尾元素交换，再调整堆。时间复杂度稳定在O(n log n)，空间复杂度O(1)，适合内存受限的场景。

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); } }

堆排序的构建堆过程从n/2 - 1开始，因为叶子节点本身已经满足堆性质，不需要调整。这个细节很多人会忽略，如果从n-1开始，虽然结果正确，但会多出大量无意义的调用。

堆排序的常数因子比快速排序大，因为每次调整堆都需要比较和交换，而且访问模式对缓存不友好。但在最坏情况下，堆排序保证O(n log n)，而快速排序可能退化到O(n²)。所以有些对稳定性要求极高的系统会选择堆排序，比如实时系统。

堆排序也是不稳定排序。另外，堆排序的交换次数比归并排序多，对于写操作敏感的场景需要权衡。

4. 实际项目怎么选：场景、数据与性能的三角平衡

4.1 数据规模决定算法选择

选排序算法，第一个要看的就是数据规模。数据量在几十个以内，插入排序是最优解，代码简单，没有递归开销。数据量在几百到几千，快速排序和归并排序都可以，快速排序的常数因子更小。数据量在几万到几百万，快速排序通常是首选，但要注意最坏情况的处理。数据量超过内存容量，归并排序的外部排序版本是唯一选择。

我做过一组实测数据，在同样的机器上对随机整数排序，结果如下：

从表格可以看出，冒泡排序在10000个数据时已经需要半秒，而快速排序只要1.2毫秒。这个差距在真实项目中是致命的。所以除非是教学演示，否则不要在生产代码里用冒泡排序。

4.2 数据特征影响算法表现

数据是否基本有序、是否有大量重复元素、元素类型是什么，这些特征都会影响排序算法的表现。

对于基本有序的数据，插入排序接近O(n)，快速排序如果基准值选得不好可能退化，归并排序不受影响。对于大量重复元素的数据，三路快速排序（把数组分成小于、等于、大于基准值三部分）比标准快速排序快很多。对于结构体或对象排序，比较操作的代价远高于交换操作，这时候归并排序的比较次数优势就体现出来了。

void threeWayQuickSort(int arr[], int low, int high) { if (low >= high) return; int lt = low, gt = high; int pivot = arr[low]; int i = low; while (i <= gt) { if (arr[i] < pivot) std::swap(arr[lt++], arr[i++]); else if (arr[i] > pivot) std::swap(arr[i], arr[gt--]); else i++; } threeWayQuickSort(arr, low, lt - 1); threeWayQuickSort(arr, gt + 1, high); }

三路快速排序在处理重复元素时，等于基准值的元素不需要参与后续递归，直接放在最终位置。对于所有元素都相同的数组，标准快速排序会退化成O(n²)，而三路快速排序只需要O(n)时间。

4.3 标准库排序的正确打开方式

C++标准库提供了std::sort和std::stable_sort两个排序函数。std::sort通常采用内省排序，平均O(n log n)，不稳定。std::stable_sort通常采用归并排序，稳定但需要额外空间。

#include <algorithm> #include <vector> std::vector<int> data = {5, 2, 8, 1, 9}; std::sort(data.begin(), data.end()); std::stable_sort(data.begin(), data.end());

使用std::sort时，比较函数必须满足严格弱序。所谓严格弱序，简单说就是比较函数不能返回true当两个元素相等时。比如return a <= b;就是错误的，应该写成return a < b;。这个错误在调试模式下可能不会暴露，但在发布模式下会导致未定义行为，甚至程序崩溃。

实操心得：如果你要排序的是自定义结构体，比较函数最好写成独立函数或者lambda，不要用成员函数。另外，比较函数里不要做复杂的计算，因为排序过程中比较函数会被调用O(n log n)次，每次多花一点时间，总时间就会显著增加。

对于需要稳定排序的场景，优先用std::stable_sort。如果内存紧张，可以考虑先给每个元素加一个原始索引，用std::sort排序，比较函数里当主要字段相等时比较索引。这样虽然多了一个字段，但避免了归并排序的额外空间开销。

5. 常见问题与排查技巧实录

5.1 排序结果不对的排查思路

排序结果不对，通常有以下几个原因。第一，比较函数的逻辑写反了。比如想升序排列，结果写成了arr[j] < arr[j+1]就交换，这样会把大的元素换到前面。第二，边界条件处理错误。比如快速排序的递归终止条件写成low <= high，会导致无限递归。第三，交换操作写错了。比如冒泡排序里写成swap(arr[j], arr[j+1])但循环变量用错。

排查的时候，先用小数据测试。比如用[3, 1, 2]这样的数组，手动模拟每一步，看看哪里和预期不符。如果小数据正确，大数据出错，那可能是递归深度或者内存问题。可以在关键位置加打印语句，输出每次分区或合并后的数组状态。

5.2 性能不达预期的优化方向

如果排序性能不达预期，可以从以下几个方向优化。第一，检查是否选择了合适的算法。小数据用插入排序，大数据用快速排序或归并排序。第二，检查比较函数是否过于复杂。把比较函数里能提前计算的值缓存起来。第三，检查是否有不必要的拷贝。比如归并排序里创建临时数组时，可以用std::vector的reserve预分配空间，避免多次扩容。

还有一个容易被忽视的点：数据的局部性。快速排序的分区操作访问内存是跳跃式的，对缓存不友好。如果数据量很大，可以考虑先分块，每块单独排序后再归并，这样能提高缓存命中率。

5.3 常见问题速查表

5.4 几个容易踩的坑

第一个坑：在快速排序里用int mid = (low + high) / 2计算中间位置。当low和high都很大时，相加可能溢出。正确写法是int mid = low + (high - low) / 2。这个细节在面试中经常被问到，实际项目中虽然溢出概率低，但一旦发生就是难以排查的bug。

第二个坑：归并排序的合并过程中，忘记处理剩余元素。当其中一个子数组遍历完后，另一个子数组可能还有剩余元素，需要全部拷贝到原数组。我见过有人只写了主循环，忘记处理剩余部分，导致排序结果丢失数据。

第三个坑：堆排序的heapify函数里，递归调用时传入的数组长度参数写错。调整堆时，数组的有效长度是当前堆的大小，不是原始数组长度。如果传错了，会把已经排好的元素重新卷入堆调整，破坏排序结果。

第四个坑：使用std::sort时，比较函数捕获了外部变量并且修改了它。排序过程中比较函数的调用顺序是不确定的，如果比较函数有副作用，结果不可预测。比较函数应该是纯函数，只依赖传入的参数。

提示：写完排序代码后，一定要用多组测试数据验证，包括空数组、单元素数组、已排序数组、逆序数组、大量重复元素数组。这些边界情况最容易暴露问题。

6. 从手写排序到工程实践的几点体会

排序算法看起来是基础中的基础，但真正写好、用对，需要的不只是记住代码。我在实际项目里最大的体会是：不要重复造轮子，但一定要知道轮子是怎么造的。标准库的std::sort已经足够快、足够稳，绝大多数场景直接用就好。但当你遇到性能瓶颈、需要定制比较逻辑、或者面试被问到原理时，手写排序的能力就体现出来了。

另一个体会是，排序的选择往往不是孤立的。它和数据结构、内存布局、并发模型都有关。比如在多线程环境下，可以把数据分块，每个线程单独排序，最后归并。这样能充分利用多核性能。又比如在数据库里，排序往往和索引结合，通过B+树的有序性避免全量排序。

最后分享一个小技巧：如果你需要频繁地对同一组数据按不同字段排序，可以考虑维护多个索引，而不是每次重新排序。比如一个学生列表，既要按学号排序，又要按成绩排序，可以维护两个指向原始数组的指针数组，分别按不同字段排序。这样原始数据不变，只需要维护索引的有序性，更新代价更小。

排序这件事，入门容易精通难。希望这篇内容能帮你把常见的几种排序算法真正吃透，在需要的时候能做出合适的选择。代码都在上面了，建议你复制到本地跑一遍，改改参数，看看不同数据规模下的表现。有些东西看一遍觉得懂了，亲手跑一遍才会发现细节里的魔鬼。