1. 为什么这五种排序值得你亲手写一遍排序算法是计算机科学里最像九九乘法表的东西——看起来简单但真正动手写的时候各种边界条件、指针越界、递归终止判断会把你折磨得够呛。我带过不少刚入门的同学他们刷题时能背出快排的平均时间复杂度是O(n log n)但让他手写一个没有bug的归并排序十有八九会在merge那一步卡住。这篇文章面向的是正在学数据结构与算法、准备面试、或者想重新夯实基础的开发者。我会用C把冒泡、选择、插入、归并、快速排序这五种经典算法完整实现一遍不只是贴代码更重要的是讲清楚每一行代码背后的意图、为什么这么写、哪里容易出错、以及实际工程中该怎么选。所有代码我都实际编译运行验证过你可以直接复制到本地跑。先给一个全局的复杂度对照心里有个底算法平均时间最坏时间空间稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定这张表不是让你背的而是让你理解每种算法的性格。冒泡和插入在近乎有序的数据上表现差异巨大归并的稳定性和快排的原地特性各有取舍这些才是真正决定你选哪个算法的依据。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[j1]相等元素会被交换稳定性就破坏了。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::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); }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 不同数据规模下的性能对比我写了一个简单的测试框架用随机整数数组分别跑五种算法记录耗时。以下是基于常见硬件的大致趋势具体数值因机器而异但相对关系稳定数据规模冒泡选择插入归并快排n100极快极快极快快快n1000慢慢较慢快快n10000很慢很慢慢快最快n100000不可接受不可接受不可接受快最快在n100这个量级五种算法的差异在微秒级肉眼无法分辨。所以如果你只是处理小数组用插入排序就够了代码简单还不容易出错。当n超过1000O(n²)的三种算法开始明显变慢。n10000时冒泡可能需要几百毫秒而快排只要几毫秒。这个差距随着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))或者用C11的std::mt19937。如果不设种子每次运行选的基准值序列都一样随机化就失去了意义。7. 从面试角度再看这五种排序面试中手写排序的概率很高但面试官真正想看的不是你能不能默写出代码而是你对细节的理解。几个高频追问快排的最坏情况是什么怎么避免——答已经有序且固定选端点为基准时退化O(n²)用随机化基准或三路快排避免。归并排序为什么稳定——答merge时相等元素优先取左边保证左边元素不会跑到右边相等元素后面。插入排序在什么情况下比快排快——答数据近乎有序且规模较小时插入排序接近O(n)常数因子也小。选择排序为什么不稳定——答交换可能把前面的元素甩到后面相等元素的后面举例[5, 5, 3]。这些问题答得上来比默写代码更能体现你的功底。我的建议是每种排序都亲手写三遍以上第一遍照着思路写第二遍不看参考写第三遍尝试默写并自己构造测试用例验证。三遍之后这些算法就真正长在你脑子里了。最后分享一个我自己的习惯每次写完一个排序我会用assert写几个断言比如排序后检查数组是否非递减、检查元素是否与排序前一致防止漏元素或重复元素。这个习惯帮我抓出过好几次merge时漏拷贝元素的bug。代码写完后花两分钟加断言比事后debug半小时划算得多。