1. 排序算法整体认知与学习路径排序算法几乎是每个学数据结构的人迈不过去的一道坎。我当年第一次接触排序就是从冒泡排序开始的写完五六个排序算法之后才逐渐明白原来排序不只是“把数字从小到大排一排”这么简单它背后牵扯到比较策略、数据移动方式、稳定性、递归思想、空间换时间等一系列问题。这篇文章就来聊聊初阶数据结构里那些经典排序算法把它们的原理、实现、优缺点和实际选型一次性讲清楚。先说清楚这篇文章适合谁。如果你正在上数据结构课、准备面试笔试中的手写算法题、或者只是想系统地补一下排序这块基础那这篇文章能帮你把散乱的知识点串成一条线。我会从最基础的 O(n²) 排序讲起一路讲到快排、归并、堆排再到计数排序这类不基于比较的排序每一段都会给出可运行的核心代码和重点注释最后再聊聊工程实践里到底该怎么选排序算法。学排序算法有个很重要的心态不要试图一口气把所有排序都背下来而是要理解每一类排序到底解决了一个什么问题。冒泡排序让你理解“交换”这个动作选择排序让你理解“扫描-定位-放置”的思路插入排序让你体会到“局部有序”的价值归并排序是“分治”思想的入门砖快速排序则是分治思想最经典的工程应用。当你把这些算法的来龙去脉弄明白再去写任何复杂算法底气都会不一样。2. 基础排序三兄弟冒泡、选择、插入2.1 冒泡排序最容易理解也最容易被低估冒泡排序的直观逻辑是每次把相邻的两个元素两两比较如果顺序不对就交换。经过一轮比较之后最大的元素就像气泡一样“浮”到数组末尾。重复 n-1 轮整个数组就有序了。void bubble_sort(int arr[], int n) { for (int i 0; i n - 1; i) { // 外层循环执行 n-1 轮 int swapped 0; // 优化标志 for (int j 0; j n - 1 - i; j) { // 内层循环每轮少比较一个 if (arr[j] arr[j 1]) { swap(arr[j], arr[j 1]); swapped 1; } } if (!swapped) break; // 这一轮没有交换说明已经有序提前结束 } }很多人觉得冒泡排序太简单没什么可学的。其实它有两个值得注意的点。一个是上面代码里的swapped标志这个优化能让原本就有序的数组在 O(n) 时间内完成排序这在笔试里是常见的优化考点。另一个是冒泡排序的稳定性——相同的元素相遇时不会交换位置所以它是稳定排序这在某些业务场景下有实际意义。2.2 选择排序思路最直白但交换次数值得斟酌选择排序的逻辑只有一句话每一轮从未排序区间里找到最小值放到已排序区间的末尾。void selection_sort(int arr[], int n) { for (int i 0; i n - 1; i) { int min_idx i; for (int j i 1; j n; j) { if (arr[j] arr[min_idx]) { min_idx j; } } if (min_idx ! i) { swap(arr[i], arr[min_idx]); } } }选择排序的时间复杂度无论数据是否有序都是 O(n²)因为它每一轮都必须完整扫描剩下的区间才能确定最小值。这一点和冒泡排序不同——冒泡排序在最好情况下可以提前退出。选择排序的优点是交换次数只有 O(n)而冒泡排序最坏情况下交换次数是 O(n²)所以在一些交换成本很高的场景比如移动大对象选择排序反而比冒泡更合适。但选择排序有个天生缺点它不稳定。举一个例子数组[5a, 5b, 3]第一轮找到 3 之后和 5a 交换两个 5 的相对顺序就变了。如果你需要排序后保持相同元素的原始先后顺序选择排序就不是一个好选择。2.3 插入排序被很多人忽略的“隐藏强者”插入排序的思想来自打牌你手里有一叠已经排好序的牌新摸到一张就找到合适的位置插进去后面的牌依次后移。void insertion_sort(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; } }插入排序在数据量大时的表现一般但在两个场景下非常能打一是数据基本有序的时候它的时间复杂度可以降到接近 O(n)这也是工程上很多排序算法会先用快排分治、再对小数组切换到插入排序的原因二是数据量很小比如十几个元素时插入排序的常数因子极低实际跑起来可能比快排还快。我实测过一个场景对 16 个随机整数排序插入排序比快速排序快大概 20% 到 30%。原因很简单快速排序的递归调用、基准值选择等操作都有额外开销而这些开销在小数据量下占比很高。所以很多成熟排序实现比如某些标准库里的introsort都会在子数组长度小于某个阈值时切到插入排序。2.4 三种 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)稳定注意这里说的“稳定”指的是排序后相等元素的相对位置保持不变。稳定的意义在业务里很常见比如你先按时间排序了订单再按金额排序如果金额排序是稳定的那金额相同的订单仍然会保持时间先后顺序。这一点在后面的基数排序里还会再次用到。3. 进阶排序希尔、归并、快速3.1 希尔排序插入排序的“跳步”进化希尔排序是插入排序的改进版。插入排序的一个瓶颈是如果小的元素在数组末尾它要一步一步往前挪挪动的次数太多了。希尔排序的思路是先让数组“宏观有序”再逐步缩小间隔做插入排序。void shell_sort(int arr[], int n) { for (int gap n / 2; gap 0; gap / 2) { // 间隔序列逐步减半 for (int i gap; i n; i) { int key arr[i]; int j i; while (j gap arr[j - gap] key) { arr[j] arr[j - gap]; // 跨间隔后移 j - gap; } arr[j] key; } } }上面的代码用的是最经典的gap n/2, n/4...递减序列时间复杂度大约在 O(n²) 附近并没有好到理论上有突破。但如果使用精心设计的间隔序列比如 Hibbard 序列、Sedgewick 序列希尔排序的平均时间复杂度能优化到 O(n^(4/3)) 甚至更好而且实现依然很简单。这也是为什么在嵌入式等对代码体积敏感的场景希尔排序仍然有人使用。希尔排序有一个问题需要注意它是“跨间隔”移动元素的所以相同元素可能会被分到不同的间隔组里导致相对顺序发生改变这也让希尔排序成为不稳定的排序算法。3.2 归并排序分治思想的经典课代表归并排序的思路一句话就能说清把数组从中间分成两半分别排序然后再把两个有序的子数组合并成一个有序数组。递归下去直到子数组长度为 1 自然有序。void merge(int arr[], int left, int mid, int right) { int n1 mid - left 1, n2 right - mid; 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 merge_sort(int arr[], int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); }归并排序最突出的特点是稳定且时间复杂度稳定在 O(n log n)不随输入数据的分布变化。这是它相比快速排序最大的优势之一——快排在极端情况下会退化到 O(n²)而归并排序不会。它的代价是空间复杂度 O(n)需要一个和原数组大小相同的临时数组。我在处理超大数据时见过有人用归并排序做外部排序把数据分块读入内存、排序、写回外存最后再合并这个思路在内存受限的场景下非常实用。面试中经常考“合并两个有序数组”和“计算逆序对”这两个问题其实都可以说是归并排序的变体。3.3 快速排序工程界的头号排序选手快速排序也是分治思想但思路和归并刚好相反归并是先拆再合拆的时候不做事合的时候才排序快速排序是“拆的时候就分区”把某个基准值放到正确位置让左边的元素都小于等于基准值右边的元素都大于等于基准值再对左右两部分分别递归。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; swap(arr[i], arr[j]); } } swap(arr[i 1], arr[high]); return i 1; } void quick_sort(int arr[], int low, int high) { if (low high) { int pi partition(arr, low, high); quick_sort(arr, low, pi - 1); quick_sort(arr, pi 1, high); } }这段代码维护了一个关键不变量[low, i]区间内的元素都小于基准值。每扫描到一个比基准小的元素就把它放到这个区间的尾部。整个遍历结束后基准值交换到i1的位置这个位置就是它最终的正确下标。快排最容易踩的坑就是基准值选择。上面代码选最后一个元素当基准如果输入数组已经有序每次分区都会选到最大或最小值导致左右严重不平衡递归深度达到 O(n)时间复杂度退化成 O(n²)。解决思路有几种随机选基准、三数取中取首、中、尾三个元素的中位数、或者像现在很多标准库实现那样在递归深度超过2*log(n)时切换到堆排序。这也是业内常说的“内省排序”introsort策略。3.4 三种进阶排序的横向对比算法平均时间最坏时间空间稳定性主要特点希尔排序O(n^(4/3))O(n²)O(1)不稳定实现简单适合嵌入式归并排序O(n log n)O(n log n)O(n)稳定适合外部排序、稳定需求快速排序O(n log n)O(n²)O(log n)不稳定平均最快需要防退化4. 线性时间排序当数据分布成为突破口4.1 计数排序用空间换时间的典型代表前面所有排序都是基于比较的基于比较的排序有一个理论下界平均情况不可能低于 O(n log n)。但是如果我们能利用数据的额外信息比如数据范围很小、分布很集中就能突破这个下界。计数排序的前提是已知待排序元素的值域范围是[0, k]k 不太大。它的做法是用一个计数数组记录每个值出现的次数然后根据次数把元素放回原数组。void counting_sort(int arr[], int n, int k) { int count[k 1] {0}; int output[n]; for (int i 0; i n; i) count[arr[i]]; for (int i 1; i k; i) count[i] count[i - 1]; // 逆序遍历保证稳定性 for (int i n - 1; i 0; i--) { output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } for (int i 0; i n; i) arr[i] output[i]; }计数排序的关键在第二个循环把计数数组变成前缀和数组之后count[v]表示“小于等于 v 的元素有多少个”这样就知道值为 v 的元素排序后应该落在哪个区间。第三个循环为什么要逆序遍历因为我们要保证相等元素的相对顺序不变逆序放置能让后面的元素先被放到偏后的位置从而维持稳定性。如果不要求稳定正序也可以但逆序的做法更通用。计数排序的时间复杂度是 O(nk)空间复杂度也是 O(nk)。当 k 远大于 n 时这个算法就不划算了——想象一下对 10 个 1 到 100 万的数排序你要开一个 100 万的计数数组纯粹是浪费空间。4.2 基数排序按位处理的巧妙思路基数排序radix sort不走比较的路而是从最低位到最高位依次对每一位做“稳定的桶式分配”。以十进制整数为例先按个位分到 10 个桶里收集回来之后数组按个位有序再按十位分桶收集此时数组按十位和个位都有序依此类推处理完最高位之后整个数组就有序了。基数排序的稳定性至关重要处理十位时如果两个数的十位相同它们落在同一个桶里的顺序取决于上一轮个位已经排好的顺序。正因为基数排序稳定低位排序的结果才能被高位继承下来最终实现全量有序。void radix_sort(int arr[], int n) { int max_val arr[0], exp 1; for (int i 1; i n; i) { if (arr[i] max_val) max_val arr[i]; } while (max_val / exp 0) { counting_sort_by_digit(arr, n, exp); // 按 exp 位做稳定计数排序 exp * 10; } }这里用到的counting_sort_by_digit其实就是把计数排序的键改成“当前位的数字”值域只有 0 到 9桶的数量固定为 10空间开销非常可控。整个算法的时间复杂度是 O(d·(n10))d 是最大数的位数。对于范围很大但位数不多的数据基数排序会比快速排序更有优势。4.3 桶排序适合均匀分布数据的分桶策略桶排序的思路和基数排序有点像但更灵活把数据按区间分到若干个桶里每个桶内部再用其他排序算法处理最后按桶顺序依次收集。void bucket_sort(float arr[], int n) { // 假设数据均匀分布在 [0, 1) 区间 int bucket_count n; vectorfloat buckets[bucket_count]; for (int i 0; i n; i) { int idx arr[i] * bucket_count; buckets[idx].push_back(arr[i]); } for (int i 0; i bucket_count; i) { sort(buckets[i].begin(), buckets[i].end()); // 桶内排序 } int idx 0; for (int i 0; i bucket_count; i) { for (float val : buckets[i]) arr[idx] val; } }桶排序的性能非常依赖数据分布。如果数据均匀分布每个桶里的元素数量都差不多总复杂度能接近 O(n)。但如果数据集中挤在某一个区间其他桶是空的所有元素都堆在一个桶里排序时间复杂度就会退化。所以用桶排序前一定要评估数据分布这是它相比其他排序最大的不确定性。提醒一句线性时间排序不是银弹。如果数据没有明确的值域或分布信息贸然使用计数排序或桶排序可能让空间开销爆炸。工程实践中先对数据做简单的 min/max 统计和分布采样再决定是否适合用这类排序是更稳妥的做法。5. 排序算法的对比与工程选型5.1 一张表看全所有经典排序算法平均时间最坏时间空间稳定性典型适用场景冒泡排序O(n²)O(n²)O(1)稳定教学演示、几乎有序的小数据选择排序O(n²)O(n²)O(1)不稳定数据量小且交换成本高插入排序O(n²)O(n²)O(1)稳定小规模数据、几乎有序数据希尔排序O(n^(4/3))O(n²)O(1)不稳定嵌入式、代码极简场景归并排序O(n log n)O(n log n)O(n)稳定外部排序、需要稳定的大数据快速排序O(n log n)O(n²)O(log n)不稳定通用场景内存友好的高性能排序堆排序O(n log n)O(n log n)O(1)不稳定需要常数空间的排序计数排序O(nk)O(nk)O(nk)稳定值域小且可枚举的整数基数排序O(d·n)O(d·n)O(n)稳定大范围整数/定长字符串桶排序O(n)O(n²)O(n)稳定均匀分布的浮点数之前一直没单独讲堆排序这里补一句堆排序借助二叉堆来反复取出最大值或最小值能够在 O(n log n) 时间完成排序且只使用 O(1) 额外空间这是它相比归并排序和快速排序的最大卖点。但它的常数因子比较大实际速度不如快排而且堆排序不稳定所以在工程里它更多是作为一种“兜底算法”存在而不是首选。5.2 实际项目中怎么选如果数据量很小十几个到几十个直接插入排序基本不会错。如果数据量中等且对稳定性有要求归并排序。如果数据量大、内存充足、没有稳定性要求快速排序是默认选择但要注意基准值策略防止退化。如果数据值域明确且窄比如成绩排序0 到 100 分或者月份统计1 到 12计数排序简直是降维打击。如果数据类型是定长数字或定长字符串基数排序的稳定性和速度兼顾得非常好。这里还想多说一句排序稳定性在现实业务里的价值。假设你要对一批学生记录先按班级排序、再按分数排序如果两次排序都是稳定的那么最终结果会得到“班级有序、每个班级内部按分数有序”的排列。这个逻辑在不引入复杂分组逻辑的情况下就能实现多级排序这也是很多数据库底层排序实现保持稳定的原因。5.3 标准库的排序实现值得借鉴各语言标准库里的排序实现往往经过大量优化是很好的学习范本。C 的std::sort通常使用内省排序融合了快排、堆排和插入排序三者的优点C 的std::stable_sort则基于归并排序Python 的sorted使用 TimSort它专门针对“包含多个有序片段”的真实数据做了优化这在很多场景下比传统归并排序更快。我在实际开发中很少手写排序算法但这不代表不用学。理解排序算法能帮你搞清楚复杂度的来源、稳定性的意义、分治和递归的边界条件而且当你需要自定义排序规则比如按某个业务字段排序、按多字段组合排序时标准库的排序接口都会要求你理解比较器函数到底怎么设计才正确。6. 常见问题与排查技巧实录6.1 边界条件数组为空、长度为 1、重复元素排序代码最容易翻车的地方不是算法本身而是边界条件。空数组不应该报错长度 1 的数组应该直接返回全数组元素都相等时算法不应该出现死循环。我在给初学者看代码时发现一个高频错误快排分区函数里当arr[j] pivot时让指针 i 前进而有些同学写成结果把所有等于 pivot 的元素都堆到一侧重复元素越多分区越不平衡。这个问题很难用肉眼发现因为小数据量下表现正常一旦数据放大就明显变慢。排查方法是在代码里加入计数器统计每次分区的两侧元素数量比例如果出现明显的极端比例就要检查比较符号。6.2 性能退化数据分布和基准值选择另一个常见问题是同一个排序算法在不同数据分布下表现天差地别。快排对“几乎有序”的数组最敏感如果基准值策略不当它会退化成 O(n²)。希尔排序对间隔序列敏感不同的 gap 序列对性能影响很大。桶排序和计数排序对数据分布敏感分布不均时性能迅速劣化。排查这类性能问题时建议做一组对照实验随机数组、正序数组、逆序数组、全部相同的数组、含有大量重复元素的数组分别记录运行时间。这个测试矩阵能帮你快速定位某个排序算法的适用边界也能帮你理解为什么标准库要实现多种策略混合的内省排序。6.3 稳定性的验证方法很多同学搞不清楚自己的排序实现到底稳定不稳定。这里给一个简单可靠的验证方法构造一组带编号的重复数据。比如将数组[3, 1, 2, 3]改成二元组[(3,0), (1,1), (2,2), (3,3)]排序后检查两个3的相对顺序。如果排序结果里(3,0)仍在(3,3)前面说明算法是稳定的。这个验证方法我几乎每讲一次排序课都会强调。因为稳定性不像时间复杂度那样能通过肉眼观察跑得快不快来判断它必须从逻辑上检验。理解了稳定性的验证方法你之后理解基数排序的“低位排序结果如何被高位继承”就会非常轻松。6.4 递归深度与栈溢出归并排序和快速排序都涉及递归调用递归深度过大时可能触发栈溢出。快排在理想情况下递归深度是 O(log n)但如果数据分布很差深度可以达到 O(n)。如果待排序数据量大或者运行环境栈空间有限比如某些嵌入式环境建议改用非递归写法或者设置递归深度阈值超出后切换成堆排序。非递归版本的归并排序也很实用它的思路是从长度为 1 的子数组开始两两合并步长翻倍直到整个数组合并完成。这种自底向上的实现避免了递归栈开销在对性能要求极高的场景里更受欢迎。顺便说一句我自己在实际编码时凡是写递归函数都会习惯性地在函数开头写清楚递归终止条件和不变量的注释这个习惯能省下大量调 bug 的时间。7. 学习路线与个人体会把排序算法学扎实我的建议是先动手写每一版代码再强行用一张表对比它们的时间、空间、稳定性。写代码时不要直接抄标准库实现也不要看一个写一个而是看完思路描述之后合上资料自己写写错了再去对照纠错。这个过程虽然有点痛苦但记忆效果远好于反复阅读教程。我在实际教学中发现真正理解排序算法的人往往都能从底层逻辑里说出“为什么工程上不常用冒泡排序”这样的判断——因为它的交换次数太多常数因子太大而且有了插入排序这种几乎同复杂度但更优的替代方案后冒泡排序只剩下教学价值。这个判断背后是一种算法敏感度它不是背出来的而是靠比较和动手实践磨出来的。最后分享一个我自己的小习惯每次写完一个排序算法我都会顺手用一组包含负数、重复值、零、最大值的数据去测一遍。因为排序考题和真实需求里最刁钻的往往是这些特殊取值组合而不是一堆规规矩矩的正整数。把这些边界情况处理顺了你写的排序代码才谈得上真正可靠。