如果你准备认真刷排序算法LeetCode 912这道题几乎是绕不开的一道坎。它要求你把一个长度不超过 5 万的整数数组升序排好很多题解会让你直接调库函数一行 return但那样学不到任何东西。今天我打算反着来用这道题做一场“基础排序算法实测”把选择排序、冒泡排序、插入排序、希尔排序四个经典选手挨个拉上场看它们各自的表现。适合刚学算法、准备面试、以及想搞清楚“为什么 O(n²) 排序在工程里几乎没有姓名”的人。1. 选题背景与整体思路为什么用 912 来验排序1.1 题目到底在考什么LeetCode 912 的题面非常简单给你一个整数数组返回升序排序后的数组。数组长度最大 50000每个元素的范围是 [-50000, 50000]。不限时空间复杂度也不强制要求“原地”还是“新数组”看起来毫无难度。但正是这种“毫无难度”最容易暴露问题。50000 这个规模相当刁钻它足够大能让各种 O(n²) 算法原形毕露又足够小让优化过的希尔排序能轻松 AC。同时判题系统会跑多组用例包括乱序、逆序、大量重复元素、负数、空数组等任何一个边界没处理好都会被揪出来。很多人遇到这道题的第一反应是直接用系统自带排序。我并不是否定库函数的价值但手写基础排序的价值在于——它能让你亲眼看到算法的每一步移动理解“为什么有的排序慢有的排序快”。这种理解是背模板换不来的也是面试中拉开差距的关键。1.2 为什么偏偏选这四种排序这篇文章选的四种排序恰好覆盖了四种最基本的算法设计思路选择、交换、插入、分组。它们都是基于比较的原地排序空间复杂度 O(1)没有递归调用代码量小逻辑直白非常适合作为算法学习的起点。不过它们的核心策略完全不同选择排序每一轮从剩余区间里挑一个最小元素放到正确位置冒泡排序通过不断交换相邻的逆序对把最大元素“浮”到末尾插入排序维护一个有序前缀把新元素逐个插入到合适位置希尔排序插入排序的升级版先分组跳跃式排序最后再做一次完整插入排序。用同一道题、同一份测试环境去对比这四种排序是再合适不过的“实验场”。你很快会发现看似都是 O(n²) 的排序实际表现大相径庭——有人压哨通过有人直接被超时劝退。这种反差比单纯看复杂度分析要直观得多。2. 四种排序核心原理与代码拆解2.1 选择排序把“最小元素”逐个请上座选择排序的思想特别朴素从第 0 个位置开始每次在 [i, n-1] 这个区间里找到最小元素的下标然后把它和第 i 个位置的元素交换。继续 i1直到数组完全有序。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (nums[j] nums[minIdx]) { minIdx j; } } if (minIdx ! i) { swap(nums[i], nums[minIdx]); } } return nums; } };这里最关键的一点无论输入数据长什么样选择排序的比较次数永远是固定的 n(n-1)/2。也就是说即使数组已经有序它也要把剩余区间全部扫一遍没有任何“提前终止”的机制。这是它最“老实”的地方也是它在 LeetCode 912 上不够讨巧的原因。关于稳定性选择排序是不稳定的。举个例子数组是 [5a, 5b, 2]第一轮选中 2 并把它和最前面的 5a 交换数组变成 [2, 5b, 5a]两个 5 的相对顺序被打破了。所以如果后面有需要保留原始先后顺序的场景选择排序不是一个好选择。2.2 冒泡排序相邻交换加一个“早停”优化冒泡排序的直观理解是从前往后两两比较相邻元素如果顺序不对就交换。一轮扫描结束后最大元素会被推到数组末尾。下一轮再对前面 n-1 个元素重复这个过程。工程上最常用的优化是加一个标志位如果某一轮扫描过程中没有任何交换说明数组已经有序可以提前退出。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); bool swapped true; for (int i 0; i n - 1 swapped; i) { swapped false; for (int j 0; j n - 1 - i; j) { if (nums[j] nums[j 1]) { swap(nums[j], nums[j 1]); swapped true; } } } return nums; } };冒泡排序虽然实现最简单但在实际运行中往往比选择排序还慢。原因在于它每发现一个逆序对就要做一次 swap而一次 swap 相当于三次赋值操作。选择排序一轮最多做一次 swap冒泡排序最坏一轮要做接近 n 次 swap。所以同样是 O(n²) 的比较量冒泡排序的赋值开销会大得多。稳定性这块冒泡排序是稳定的。因为代码里只有严格大于才交换相等元素只会擦肩而过不会越过彼此。2.3 插入排序扑克牌式的增量维护插入排序的思维路径是这样的把数组分成两部分左侧 [0, i-1] 已经有序右侧从 i 开始。每次取出 nums[i]在左侧从后往前找合适的位置插入。这个动作和大多数人打扑克牌时理牌的手法一模一样。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int i 1; i n; i) { int key nums[i]; int j i - 1; while (j 0 nums[j] key) { nums[j 1] nums[j]; --j; } nums[j 1] key; } return nums; } };插入排序的最大亮点是它对“近乎有序”的数组极度友好。比如数组本身已经基本排好每个元素需要移动的距离都很短内层 while 循环几乎不会执行整体时间复杂度可以逼近 O(n)。这也是后来很多高级排序算法在递归到小规模子数组时会改用插入排序的重要原因——常数极小还能吃到“局部有序”的红利。但反过来如果数组完全逆序插入排序每次插入都要一路移动到底比较和移动次数都会达到最坏级别性能直接崩盘。插入排序是稳定排序。关键在 while 循环里的条件是 nums[j] key而不是 。相等元素不会被移动原有顺序得以保留。2.4 希尔排序让插入排序学会跳跃希尔排序的出发点是插入排序对“大体有序”的数据很高效但如果数据整体杂乱它每一步只能移动一个位置效率太低。那把元素先跳着分组、做几次“粗略的插入排序”呢这就是“递减增量排序”的核心思想。希尔排序先把数组按某个间隔 gap 分成若干组每组内部做插入排序。然后缩小 gap重复这个过程。最后当 gap 1 时相当于做一次普通的插入排序但此时数组已经非常接近有序所以这一轮不会有多少移动量。class Solution { public: vectorint sortArray(vectorint nums) { int n nums.size(); for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key nums[i]; int j i; while (j gap nums[j - gap] key) { nums[j] nums[j - gap]; j - gap; } nums[j] key; } } return nums; } };这段代码在结构上和插入排序几乎一模一样唯一的区别就是把下标步长从“1”换成了“gap”。理解这一点希尔排序就不难记忆。gap 序列的选择直接决定希尔排序的上限。最简单的 n/2 递减实现容易平均复杂度约 O(n^1.3)但在某些特殊输入下最坏会退化为 O(n²)。Knuth 提出的 3x1 序列是更稳的选择实现起来也只差几行int gap 1; while (gap n / 3) { gap gap * 3 1; } for (; gap 0; gap / 3) { // 内部逻辑同上 }希尔排序是这四种排序里唯一不稳定但性能提升明显的算法。稳定性之所以丢失是因为相同元素可能被分到不同间隔的子序列中后续跳跃式移动会改变它们的相对顺序。比如 [2a, 2b, 1] 在 gap2 时2a 和 1 先被排成 [1, 2a]数组变成 [1, 2b, 2a]两个 2 的相对顺序就反转了。3. 完整实操逐个提交 LeetCode 9123.1 统一测试模板为了公平对比我建议你在本地也建立一个统一的测试环境。这里用 C17 为例只提供一个 Solution 类模板核心排序逻辑放在 sortArray 方法里不要调用库函数也不额外开大数组。#include vector #include algorithm using namespace std; class Solution { public: vectorint sortArray(vectorint nums) { // 在这里替换四种排序算法 return nums; } };如果你用 Python 做同样的事思路是一样的但提交时的心态要放平。Python 解释器的常数开销非常大对 O(n²) 算法来说基本是硬伤。3.2 四份提交代码与结果第一份选择排序。C 版本在单组 5 万数据规模下勉强能抗住提交后状态可能是 Accepted但耗时在提交记录里属于垫底那一档接近超时红线。如果换成 Python大概率收获一个红色的 TLE。原因是 50000 个元素的比较次数高达约 12.5 亿次Python 跑这个量级的解释器循环基本无望。第二份冒泡排序。我在本地随机生成了 5 万个数带上 flag 优化的冒泡排序依然跑得很吃力。提交后在逆序或近似逆序用例上几乎必挂。它的比较次数和选择排序相当但额外多出海量交换操作赋值开销成倍增加。第三份插入排序。随机数组下C 版本可能压线通过但一旦遇到逆序测试用例直接超时。因为逆序输入正好打在最坏情况上每次插入都得从头挪到尾。Python 版本同样没有讨论的必要。第四份希尔排序。这才是四种排序里“能打”的那一个。C 版本一次通过耗时非常体面Python 版本也能 AC。原因很简单希尔排序把操作次数从亿级别降到了百万到千万级别量级差直接体现为 Accepted 而不是 TLE。四份提交的表现汇总如下排序算法C 提交状态耗时量级关键原因选择排序压线通过数百毫秒比较次数固定约 12.5 亿次冒泡排序大概率超时更差比较加交换赋值开销大插入排序随机压线逆序超时视数据而定逆序输入最坏希尔排序稳定通过数十毫秒量级跳跃式插入分组消逆序3.3 性能差距的本质比较次数和移动次数很多人背了复杂度就以为所有 O(n²) 排序都一样慢实际上差距可以非常悬殊。以 n 50000 为例选择排序比较次数恒定为 50000 × 49999 / 2约 12.5 亿次冒泡排序最坏比较次数同样约 12.5 亿次但交换次数也可能接近这个数量级插入排序随机数据的平均移动量约为 6.25 亿次逆序时回到 12.5 亿次希尔排序根据 gap 序列不同一般操作量在几百万到几千万次之间。这个数量级差距换算成判题机上的真实耗时就是 AC 与 TLE 的分水岭。C 虽然能扛住 12.5 亿次简单整数比较但还要叠加多组测试用例和 IO 开销压线过已经算运气好。Python 面对这个量级基本毫无还手之力。这也提醒我们分析算法时不能只看大 O 级别常数项、输入形态、赋值操作次数全部会影响实际表现。4. 常见问题与避坑清单4.1 最容易写错的四个边界四种排序代码都不长但真正手写时出错率极高。我整理了一个速查表每一行都是实际提交中踩过的坑排序算法最容易写错的地方后果选择排序外循环写成 i n多处理一轮index 越界选择排序minIdx 每轮没有重置使用上一轮的下标结果错误冒泡排序内层边界写成 n - 1访问 nums[j1] 越界插入排序内层忘记先用 key 保存当前位置后移时覆盖原值插入排序循环结束后写成 nums[j] key位置差一位排序错误希尔排序gap 初始为 0循环条件判断错误死循环或根本没有分组排序4.2 别用异或交换数组元素很多“炫技”代码喜欢用异或交换两个整数比如 a ^ b; b ^ a; a ^ b。这个技巧在数组场景下有致命隐患如果 a 和 b 是同一个下标位置的元素交换后该位置会变成 0。这在选择排序中尤其容易发生因为当 nums[i] 恰好就是最小值时minIdx i交换的元素是同一个数组位置异或版本直接清零。统一做法是使用 std::swap 或者临时变量。LeetCode 的判题环境支持 C17直接 swap 即可不要在这个地方追求所谓“炫技”。另外注意数组可能包含负数。在找最小值时不要把初始值设成 0否则遇到全负数数组结果必然错误。最稳妥的方式是把初始最小值设为当前轮次的起点元素 nums[i]。4.3 稳定性为什么值得关心稳定性不是一个只在教科书里出现的高冷概念它在实际开发中非常实用。举个具体例子一个学生名单已经按姓名排好序现在想按成绩重新排。如果使用稳定排序成绩相同的人仍然保持姓名的先后顺序如果使用不稳定排序上一次排序的结果会被打乱。四种排序的稳定性对比如下稳定冒泡排序、插入排序不稳定选择排序、希尔排序。现代语言内置的排序之所以多数采用稳定策略也是因为工程中经常需要对多个字段依次排序稳定性可以避免额外的复合键设计。4.4 提交时遇到的“灵异现象”有一次我写插入排序内层 while 条件写成了 j 0 而不是 j 0结果大部分用例都通过只有包含“数组第一个元素恰好是全局最小值且需要移动”的用例失败。这种错误极其隐蔽因为普通随机数据下第一个元素往往不是拖后腿的那个只有特定输入才能触发。还有一次我写希尔排序gap 的初始值用的是 n/3 而不是 n/2循环里又用了 gap / 2导致 gap 从不是 1 的那一步直接跳到 0最后的普通插入排序被跳过数组永远无法完全有序。这类问题靠肉眼很难发现最好的办法是准备几组对抗数据包括逆序、重复、单元素、空数组逐个自测。5. 进阶思考从四种排序能带走什么5.1 工程里为什么很少单独用它们作战如果你去看主流语言的内置排序实现会发现它们很少单独靠某一种基础排序。快排、堆排、归并是分治思想的产物性能更稳定。但插入排序并没有被丢弃它经常作为大排序的“收尾阶段”被调用。当递归划分到局部子数组规模小于某个阈值常见是 16 到 32 个元素时直接改用插入排序因为它的常数极小对近乎有序的局部数据表现极佳。希尔排序的分组策略在某些场景下依然有用。它提供了一种“先粗粒度调整再精排”的朴素思想这也是很多工程问题的通用优化思路。5.2 同一道题四种性格LeetCode 912 最迷人的地方在于同样一个输入四种基础排序会展现出完全不同的“性格”。选择排序像一个老实人无论数据怎样都一板一眼地扫完冒泡排序像一个急性子看到逆序就忍不住交换插入排序像善于利用环境的聪明人遇到局部有序就手脚麻利希尔排序则像全局规划者先用大步长把大方向摆正再做精细调整。学算法如果只记代码就像背单词只看抄写很快会忘。试着用自己的话解释“为什么希尔排序能比插入排序快”解释清楚了说明你真的掌握了。我个人在实际刷题中最大的体会是912 这道题逼我把那层“反正有库函数”的依赖心理拆掉了。四种排序虽然不常用但它们是理解更高级算法的地基。比如快排的基准选择本质上是对冒泡“交换”思路的分治加强归并排序的合并过程则可以看作插入排序“合并有序区间”的规模化版本。地基打牢之后再看任何排序都不慌。最后送大家一个建议不要一次性把这四种排序都背完再上机最好写一个提交一个亲手试试每种排序在 50000 个数据上到底会收获 Accepted 还是 TLE。只有被超时痛击过一次你才会真正明白复杂度分析的意义。