1. 为什么这五种排序值得你亲手写一遍

排序算法是计算机科学里最像"九九乘法表"的东西——看起来简单，但真正动手写的时候，各种边界条件、指针越界、递归终止判断会把你折磨得够呛。我带过不少刚入门的同学，他们刷题时能背出快排的平均时间复杂度是O(n log n)，但让他手写一个没有bug的归并排序，十有八九会在merge那一步卡住。

这篇文章面向的是正在学数据结构与算法、准备面试、或者想重新夯实基础的开发者。我会用C++把冒泡、选择、插入、归并、快速排序这五种经典算法完整实现一遍，不只是贴代码，更重要的是讲清楚每一行代码背后的意图、为什么这么写、哪里容易出错、以及实际工程中该怎么选。所有代码我都实际编译运行验证过，你可以直接复制到本地跑。

先给一个全局的复杂度对照，心里有个底：

这张表不是让你背的，而是让你理解每种算法的"性格"。冒泡和插入在近乎有序的数据上表现差异巨大，归并的稳定性和快排的原地特性各有取舍，这些才是真正决定你选哪个算法的依据。

2. 三种O(n²)排序：看似简单，细节全是坑

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？因为每一轮结束后，最大的元素已经被推到了末尾，后面的i个元素已经有序，不需要再比较。这个边界如果写成n - 1，程序不会崩，但会做大量无用功。

那个swapped标志位是冒泡排序唯一值得称道的优化。考虑一个已经有序的数组，没有标志位的话仍然要跑满O(n²)；加上之后，第一轮发现没有交换直接break，退化成O(n)。这就是为什么面试时如果你只写一个裸的双重循环，面试官会觉得你只是背了代码。

注意：冒泡排序的稳定性来自于>而不是>=。如果写成arr[j] >= arr[j+1]，相等元素会被交换，稳定性就破坏了。

2.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，跟数据初始状态无关，所以对近乎有序的数据没有任何优势。

它为什么不稳定？举个例子：序列[5, 5, 3]，第一轮把第一个5和3交换，变成[3, 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; } }

这里有个关键细节：arr[j] > key而不是>=，保证了相等元素不会跨越，维持稳定性。另外注意是"移动"而不是"交换"，这比冒泡的交换效率高，因为一次赋值比三次赋值（swap需要临时变量）便宜。

插入排序在数据近乎有序时接近O(n)，这是它最被低估的地方。实际上很多工业级排序库（比如某些标准库的混合排序）在数组长度小于某个阈值（常见是16或32）时，会直接切换到插入排序。原因很简单：小数组上，插入排序的常数因子远小于快排和归并，递归调用的开销反而成了负担。

我实测过，对100个随机整数排序，插入排序和快排的耗时差异在微秒级别，肉眼根本看不出来。所以别盲目迷信O(n log n)，常数因子在小规模数据上才是决定性的。

3. 归并排序：分治思想的最佳入门范本

3.1 递归框架与merge的核心逻辑

归并排序是理解"分治"最好的例子。它的逻辑非常干净：把数组从中间劈开，分别排好序，再合并两个有序数组。

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

mid = left + (right - left) / 2这个写法比(left + right) / 2更安全，因为当left和right都很大时，相加可能溢出。虽然int的范围在一般场景下够用，但养成这个习惯没坏处。

merge里的L[i] <= R[j]用的是<=，这是保证稳定性的关键。当左右两边元素相等时，优先取左边的，这样左边元素就不会跑到右边相等元素的后面。

3.2 为什么归并的空间复杂度是O(n)而不是O(log n)

很多人会疑惑：递归的栈深度是O(log n)，为什么说空间复杂度是O(n)？因为每一层递归在merge时都创建了临时数组，虽然这些数组在函数返回后会被释放，但在任意时刻，递归调用栈上所有层的临时数组加起来，最坏情况是O(n)。准确地说，归并排序的空间复杂度是O(n)（临时数组）+ O(log n)（递归栈），取大头就是O(n)。

如果你在面试中被问到"能不能把归并排序优化成原地排序"，答案是理论上可以（比如用循环移位实现原地merge），但会让时间复杂度退化到O(n²)或者实现极其复杂，工程上不划算。所以标准归并排序就是O(n)额外空间，接受这个事实就好。

3.3 归并排序在链表场景下的独特优势

归并排序有一个其他排序都比不了的应用场景：链表排序。因为链表的merge操作不需要额外空间，只需要改变指针指向，所以链表上的归并排序空间复杂度可以做到O(log n)（只有递归栈）。这也是为什么很多标准库的链表排序底层用的就是归并。

如果你在写链表相关的题目，需要排序，优先考虑归并而不是快排。快排在链表上无法高效地随机访问，partition操作会变得很别扭。

4. 快速排序：平均最快，但最坏情况要人命

4.1 partition的两种经典写法

快速排序的核心是partition：选一个基准值，把小于它的放左边，大于它的放右边。最常见的是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; } void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partitionLomuto(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }

Lomuto方案好理解，但当数组中有大量重复元素时，性能会退化。另一种是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]); } }

Hoare方案在处理重复元素时更均衡，但边界条件更难写对。我个人的经验是：如果数据随机性较好，Lomuto足够；如果数据可能有大量重复，用三路快排（下面讲）。

4.2 基准值选择：随机化是保命符

快排最坏情况是O(n²)，发生在每次选的基准值都是当前区间的最大或最小值时。比如对一个已经有序的数组，如果固定选第一个或最后一个元素做基准，就会退化成冒泡排序。

解决办法是随机化选基准：

int randomPartition(int arr[], int low, int high) { int randomIdx = low + rand() % (high - low + 1); std::swap(arr[randomIdx], arr[high]); return partitionLomuto(arr, low, high); }

随机化的作用是让"最坏情况"在概率上几乎不可能发生。虽然理论上仍然存在O(n²)的可能，但期望时间复杂度是O(n log n)。工程上这就够了。

4.3 三路快排：重复元素的克星

当数组中有大量重复元素时，标准快排会把相等的元素分到同一侧，导致分区极度不平衡。三路快排把数组分成"小于基准""等于基准""大于基准"三段，等于基准的部分直接到位，不再参与递归。

void quickSort3Way(int arr[], int low, int high) { if (low >= high) return; int pivot = arr[low + rand() % (high - low + 1)]; int lt = low, gt = high, 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++; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt + 1, high); }

这个版本在处理"所有元素都相同"的数组时，一趟partition就直接结束，时间复杂度O(n)。如果你经常处理有大量重复键的数据（比如按年龄排序、按分数排序），三路快排是必备技能。

4.4 递归深度与栈溢出风险

快排的递归深度在最坏情况下是O(n)，当n很大时（比如百万级），可能导致栈溢出。两个应对策略：一是随机化基准值，让期望深度降到O(log n)；二是当递归深度超过某个阈值时，切换到堆排序（这就是introsort的思路，C++标准库的std::sort就是这么干的）。

如果你要自己实现一个工业级快排，建议加一个深度计数器，超过2 * log2(n)就改用堆排序。当然，日常练习和面试中，随机化版本已经足够。

5. 五种算法放在一起跑：实测数据与选型建议

5.1 不同数据规模下的性能对比

我写了一个简单的测试框架，用随机整数数组分别跑五种算法，记录耗时。以下是基于常见硬件的大致趋势（具体数值因机器而异，但相对关系稳定）：

在n=100这个量级，五种算法的差异在微秒级，肉眼无法分辨。所以如果你只是处理小数组，用插入排序就够了，代码简单还不容易出错。

当n超过1000，O(n²)的三种算法开始明显变慢。n=10000时，冒泡可能需要几百毫秒，而快排只要几毫秒。这个差距随着n增大呈平方级扩大。

5.2 近乎有序的数据：插入排序的逆袭

我特意测试了一个"近乎有序"的数组（只有少数几个元素错位）。结果很有意思：插入排序的速度接近快排，远超归并。因为插入排序在近乎有序时，每个元素只需要移动很少的位置，接近O(n)。

这给了一个重要启示：如果你的数据本身就有一定的有序性（比如日志按时间追加、数据库增量导出），插入排序可能是最优选择，而不是无脑上快排。

5.3 稳定性需求下的选择

如果排序后需要保持相等元素的原始顺序（比如先按姓名排序，再按年龄排序，希望同年龄的人保持姓名有序），那就必须用稳定排序。五种算法中，冒泡、插入、归并是稳定的，选择和快排不稳定。

实际工程中，归并是稳定排序里效率最高的，所以当你需要稳定性且数据量较大时，归并是首选。如果数据量小，插入排序更简单。

5.4 工程中的混合策略

真正工业级的排序不会只用一种算法。以C++标准库的std::sort为例，它用的是introsort：快排为主，递归深度过深时切堆排序，小数组切插入排序。这种混合策略兼顾了平均性能、最坏情况和常数因子。

如果你要自己写一个通用排序函数，我建议的阈值是：数组长度小于16时用插入排序，大于16时用三路快排，递归深度超过2*log2(n)时切堆排序。这个组合在实践中表现非常稳。

6. 手写排序时最容易翻车的几个地方

6.1 边界条件：差一错误是永恒的主题

排序算法的bug绝大多数出在边界上。我整理了几个高频翻车点：

• 冒泡的内层循环写成j < n - 1而不是j < n - 1 - i，结果没错但效率低。
• 插入排序的while条件写成j > 0而不是j >= 0，导致第一个元素无法被正确插入。
• 归并的mid计算写成(left + right) / 2，在极端情况下溢出。
• 快排的递归调用写成quickSort(arr, low, pi)而不是quickSort(arr, low, pi - 1)，导致死循环。

这些错误单独看都很蠢，但在手写时就是会犯。我的建议是：写完先拿一个长度为0、1、2的数组测试，再拿一个已经有序的数组测试，最后拿一个全部相同的数组测试。这三类测试能覆盖90%的边界bug。

6.2 递归终止条件：别忘了base case

归并和快排都是递归算法，base case写错会直接导致栈溢出。归并的终止条件是left >= right，快排是low >= high。注意是>=而不是==，因为可能存在left > right的情况（比如partition返回的pi等于low时，递归调用quickSort(arr, low, pi - 1)会传入low > high）。

6.3 数组下标与指针的混淆

C++里数组传参时会退化成指针，sizeof(arr) / sizeof(arr[0])在函数内部无法得到正确的数组长度。所以我的所有实现都显式传入n或者right边界。如果你在函数内用sizeof算长度，结果一定是错的（得到的是指针大小除以元素大小）。

6.4 随机数种子的设置

用随机化快排时，别忘了在程序开始时调用srand(time(nullptr))或者用C++11的std::mt19937。如果不设种子，每次运行选的基准值序列都一样，随机化就失去了意义。

7. 从面试角度再看这五种排序

面试中手写排序的概率很高，但面试官真正想看的不是你能不能默写出代码，而是你对细节的理解。几个高频追问：

"快排的最坏情况是什么？怎么避免？"——答：已经有序且固定选端点为基准时退化O(n²)，用随机化基准或三路快排避免。

"归并排序为什么稳定？"——答：merge时相等元素优先取左边，保证左边元素不会跑到右边相等元素后面。

"插入排序在什么情况下比快排快？"——答：数据近乎有序且规模较小时，插入排序接近O(n)，常数因子也小。

"选择排序为什么不稳定？"——答：交换可能把前面的元素甩到后面相等元素的后面，举例[5, 5, 3]。

这些问题答得上来，比默写代码更能体现你的功底。我的建议是：每种排序都亲手写三遍以上，第一遍照着思路写，第二遍不看参考写，第三遍尝试默写并自己构造测试用例验证。三遍之后，这些算法就真正长在你脑子里了。

最后分享一个我自己的习惯：每次写完一个排序，我会用assert写几个断言，比如排序后检查数组是否非递减、检查元素是否与排序前一致（防止漏元素或重复元素）。这个习惯帮我抓出过好几次merge时漏拷贝元素的bug。代码写完后花两分钟加断言，比事后debug半小时划算得多。