很多人都会写排序，背得出冒泡、选择、插入的模板，甚至能默写快排的递归。但被问到“为什么插入排序在数据基本有序时能接近线性”“为什么快排平均是O(n log n)却会在有序数组上退化到O(n²)”“稳定性到底在工程里有什么用”时，就开始卡壳。这篇“六大经典排序的真正底层逻辑（上）”要解决的，正是这些问题——我把六大经典排序拆成上下两篇，上篇先把四个最常用的讲透：选择排序、冒泡排序、插入排序、快速排序。归并排序和堆排序涉及“分治的不同形态”和“数据结构驱动”这两套新逻辑，放下一篇单独聊。
这篇适合三类人：一类是背了模板但总被面试官追问到破防的求职者，一类是刷LeetCode时排序题永远靠内建函数、想真正建立底层认知的自学者，还有一类是写业务代码时遇到“sort了一下但结果不如预期”的开发者。我不会只贴代码，重点讲每个算法在设计时面临的选择、它为什么长成这样、什么场景下它才是最优解。这些才是“底层逻辑”。
1. 排序的底层游戏规则：一切从逆序对与比较决策开始
在看具体算法之前，得先建立一个统一的观察框架。不然你会发现四个算法各写各的，很难横向比较。
先说一个概念：逆序对。对于序列里的任意两个元素a[i]和a[j]，如果i < j但a[i] > a[j]，这两个元素就构成一个逆序对。升序排序的本质，就是不断消除逆序对的过程。你可以想象一个杂乱的队伍：队伍里只要还有两个人站反了位置，排序就没完成。这个视角特别重要，因为四种排序的核心差异，恰恰在于它们用什么样的策略去消除逆序对。
再想一个问题：为什么“基于比较的排序”最快也只能做到O(n log n)？这里有个非常漂亮的论证，叫决策树模型。假设有n个互不相同的元素，它们的所有可能排列有n!种。你每做一次“a[i]和a[j]谁大”的比较，就只能得到两个结果——要么大于，要么小于。这就像一次猜谜，每个问题只能把可能性劈成两半。区分n!种排列，至少要log2(n!)次比较。用斯特林公式展开n!，log2(n!) ≈ n log2 n - 1.44n，忽略低阶项就是O(n log n)。
这个结论对所有“只靠比较”的排序都成立，是天花板，谁也绕不过去。你可能会问：那为什么会有O(n²)的排序？因为它们比较了太多次，做了大量“无效区分”——很多次比较的结果在逻辑上早就可以推断出来，但它没有利用这些信息。搞清楚这个框架，再看四种排序，你会看到它们其实是四种不同的“决策策略”。
还要提前说清楚一个概念：稳定性。稳定排序的意思是，值相等的两个元素，排序后相对位置不变。这听着像细枝末节，但在工程里是大事。比如数据库里先按部门排序、再按薪资排序，如果薪资排序是稳定的，部门分组内部还能保留刚才的排序结果；如果它不稳定，第一次排序就白做了。所以稳定性不是一个算法“有没有面子”的属性，而是决定你能不能做多级排序的关键能力。
四个算法在这个框架下的定位先列个表，后面逐个展开：
| 算法 | 比较策略 | 交换是否相邻 | 最好复杂度 | 平均复杂度 | 最坏复杂度 | 稳定 |
|---|---|---|---|---|---|---|
| 选择排序 | 全区间扫描 | 否 | O(n²) | O(n²) | O(n²) | 否 |
| 冒泡排序 | 相邻比较并交换 | 是 | O(n)（改进版） | O(n²) | O(n²) | 是 |
| 插入排序 | 向前扫描并后移 | 是 | O(n) | O(n²) | O(n²) | 是 |
| 快速排序 | 与基准比较分区间 | 否 | O(n log n) | O(n log n) | O(n²) | 否 |
2. 选择排序：做最小的工作，却付出最多的代价
2.1 核心思想与代码
选择排序的思路朴素到令人发指：从头到尾扫描整个序列，找到最小值，放到第一个位置；再从剩下的序列里找最小值，放到第二个位置；不断重复。这个过程像极了你在一个乱抽屉里反复挑最小的东西往外拿。
def selection_sort(arr): n = len(arr) for i in range(n - 1): # 找到[i, n-1]区间内最小元素的下标 min_idx = i for j in range(i + 1, n): if arr[j] < arr[min_idx]: min_idx = j # 将最小值放到位置i arr[i], arr[min_idx] = arr[min_idx], arr[i] return arr代码只有十几行，逻辑也没有任何绕弯。但注意，它一共要做n-1轮的“找最小值”，每轮要扫描n-i-1个元素。所以总比较次数是 (n-1) + (n-2) + ... + 1 = n(n-1)/2，无论数据本来是否有序，这个扫描代价一分都省不掉。
2.2 只做n-1次交换，为什么依然笑不出来
选择排序有个很反直觉的优点，大多数教材没讲透：它的交换次数只有n-1次，是所有排序中最少的。每次交换是“把最小值放到最终位置”，一次性消除它和很多元素的逆序关系，所以交换次数真的少。
那它为什么还是O(n²)？因为找最小值的过程本身就是一种“探测成本”。你为了做一次“少而精准”的交换，必须先付出大量比较来确认哪个才是最小值。这就好比你为了在市场上买到最便宜的菜，把整个菜市场每个摊位都问了个遍——最后确实只买了一次，但打听成本高得离谱。在很多机器上，比较/选择操作的CPU代价不比交换低多少，所以这笔账并不划算。
2.3 不稳定之坑与实战提醒
选择排序的不稳定性是面试高频考点。看这个过程：序列 [5, 5, 2]，第一轮找到最小值2，把它和第一个5交换。两个5的相对顺序在交换后直接翻转，后面的过程也无法再纠正。这里的关键在于：选择排序做的是跨区间的直接交换，而跨区间的交换可以轻易改变相等元素的相对位置。
实战中我不推荐手写选择排序，除非是竞赛入门教学，或者你要处理超大对象数组而且交换成本远高于比较成本——这时候n-1次交换的优势才可能压过O(n²)比较的劣势。但在绝大多数场景里，这个收益撑不起性能，因为它对“数据是否有序”完全不敏感，该扫的都扫。一个完全有序的数组，它也照样给你扫描n(n-1)/2次。
3. 冒泡排序：相邻交换背后的“局部博弈”
3.1 核心思想与代码
冒泡排序的设计逻辑比选择排序更“物理化”：从左到右依次比较相邻元素，如果左边大于右边就交换。这样每一轮过后，当前区间内最大的元素就像气泡一样“浮”到末尾。为什么叫冒泡？因为每一轮只做相邻位置之间的比较和交换，大元素是一步一步往外挪的。
def bubble_sort(arr): n = len(arr) for i in range(n - 1): # 每轮把[0, n-1-i]中的最大值冒到最后 swapped = False for j in range(n - 1 - i): if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # 如果本轮没有任何交换，说明已经有序，提前结束 if not swapped: break return arr我这里的代码加了一个优化标志位swapped，后面会讲这个优化到底意味着什么。
3.2 冒泡的两个优化方向
第一个优化就是上面代码里的提前终止。每一轮如果全程没有发生任何交换，说明相邻元素之间已经没有逆序对——而一串相邻都不逆序的序列，整个序列必然有序。此时直接break。这个优化让冒泡对“基本有序”的数据有很好的响应，最好情况能做到O(n)。
第二个优化是缩小扫描区间。每轮结束后，最大值已经到达最终位置，下一轮扫描就可以少看一个元素。这个优化所有冒泡版本都会写，但我要提醒你一个细节：优化后的冒泡仍然只处理“相邻逆序对”。每一轮比较后，一个元素最多只能从当前位置移动一个位置，这就是它低效的根因。
想象你在一条单行道上倒车：你后面有20辆车堵着，但你每次只能和最近的那辆协商换位，要换20次才能脱身。相邻交换很稳妥，但代价是每交换一次只消除一对逆序对。逆序对数量在随机序列里大约是n(n-1)/4的量级，所以冒泡排序的最坏复杂度必然是O(n²)——它把大量成本花在了“一格一格挪动”上。
3.3 在计算机上，冒泡的天然劣势
有一点值得玩味：冒泡排序在人类感官里最直观——你真实地看到大的元素逐步“漂移”到右侧。但计算机处理“相邻交换”的效率并不比直接交换高，反而多了大量内存读写。更糟的是，冒泡的交换次数几乎等于逆序对数量，在随机数据上，这个数字比选择排序和插入排序都高。
不过冒泡有一个被低估的优点：稳定。因为相邻元素的值相等时不会交换，相等元素的相对位置天然得到保留。这在多级排序场景里有用。另外，它和插入排序一样，在“数据基本有序”的时候表现很好，但插入排序的比较次数更低、代码也更简洁，所以工程里基本都选插入而不是冒泡。我的建议是：冒泡作为教学排序理解“相邻交换+提前终止”的思想非常合适，写业务代码时没必要用它。
4. 插入排序：被严重低估的“序列整理员”
4.1 核心思想与代码
插入排序的思路再生活化不过：你打牌时，每抓一张新牌，就会把它插到手里已经排好序的牌中合适的位置。算法过程也这样——把序列分成“已排序前缀”和“待排序后缀”，每次从后缀取一个元素，在前缀里从后往前扫描，找到合适的位置插进去。
def insertion_sort(arr): n = len(arr) for i in range(1, n): key = arr[i] j = i - 1 # 从右往左扫描已排序区，比key大的都往后移一位 while j >= 0 and arr[j] > key: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr很多人觉得插入排序是O(n²)的“弱小算法”，其实它才是隐藏的强者。相比选择排序的“无脑全扫描”，插入排序每轮扫描到合适位置就停下来，不需要看遍整个前缀。尤其当数据基本有序时，它每一轮几乎只做一次比较就入位，整体会退化到接近O(n)——这是它区别于其他两个O(n²)排序的核心优势。
4.2 基本有序时的“逆序对红利”
回到逆序对的视角：插入排序每一轮处理的其实是“把当前元素往左移动它距离正确位置的步数”。如果整个数组已经基本有序，每个元素离正确位置都很近，移动次数极少，比较次数也随之锐减。最极端的情况，一个已经排好的数组，插入排序每一轮只需要比较一次，总共n-1次比较就完成任务——O(n)。
这就是“逆序对红利”：数据的有序度越高，插入排序越快。这种特性在处理“近乎有序”的流式数据或小规模数据时价值巨大。生产环境的很多排序库都会做这样的设计：当区间长度小于某个阈值（比如16或32）时，不再递归调用高级排序，而是直接用插入排序收尾。因为高级排序的“分治框架”在小区间上的常数开销太大了，插入排序反而更快。
4.3 插入排序为什么是排序算法的“基建”
插入排序不只是自成一派，它还是很多进阶算法的基石。希尔排序就是它的改良版，通过大步长分组先做“宏观调整”，最后再用小步长排序。快速排序和归并排序在小区间上会调用插入排序作为兜底。JDK里的Arrays.sort对原始类型数组用的DualPivotQuicksort，在长度小于47时就直接用插入排序；对对象数组做归并排序时也用了类似策略。
另外插入排序在链表上也很自然：链表不需要移动元素，只需要改指针就能完成“插入”，比数组更丝滑。很多语言自带的链表排序，底层就是插入排序或其变体。所以千万别小看它——它是一个组合拳选手，真正的产业级价值体现在“配合”中。我自己写归并排序或者快排的分治实现时，一定会带一句“if (r - l < 20) { insertionSort(...); }”，这句话能省掉大量递归常数开销，在实测中性能提升非常明显。
5. 快速排序：一次“分而治之”如何实现平均最快
5.1 核心思想与代码
快速排序是现代排序界真正的主角。它的思路同样朴素：从序列中选一个基准值pivot，然后把剩下的元素分成两组——小于基准的放左边、大于基准的放右边——基准放到中间，此时基准已经在它的最终位置。这个动作叫partition（分区）。然后对左右两个区间各自做同样的事情，直到所有区间都只剩一个或零个元素。
def quick_sort(arr, left, right): if left >= right: return pivot_idx = partition(arr, left, right) quick_sort(arr, left, pivot_idx - 1) quick_sort(arr, pivot_idx + 1, right) def partition(arr, left, right): # 这里用Lomuto分区：选最右元素为基准 pivot = arr[right] i = left for j in range(left, right): if arr[j] < pivot: arr[i], arr[j] = arr[j], arr[i] i += 1 arr[i], arr[right] = arr[right], arr[i] return i这里用的是Lomuto分区方案，简洁但性能不是最优。工业界更常用Hoare分区，它从两头向中间逼近，交换次数更少，但实现起来更容易出错。我觉得新手先掌握Lomuto理解思路，再进阶去写Hoare，顺序是对的。
5.2 为什么快排平均是O(n log n)
快排的平均复杂度O(n log n)可以用递归分摊来理解。理想情况下，每次partition把一个区间分成两个近似相等的子区间，递归深度是log n层，每层partition的扫描总量是O(n)，总工作量就是O(n log n)。这符合主定理的情形。
但更本质的解释在于：快排的分治策略让每个元素在每一层只需要参与O(1)次比较。第一层所有元素都和基准比较一次；第二层是左右两组元素各自和新的基准比较，每一组只扫描它自己那部分。所以每层总比较量约等于n，乘以深度log n，就是n log n。相比之下，冒泡和选择排序每轮的扫描都是“重复扫描”，而快排每轮的partition是“减治扫描”——每个元素一旦被分到某个区间，它永远不会再回到另一个区间，之前的所有比较结果都被有效利用。
5.3 最坏O(n²)是怎么被“逼”出来的
快排在最好的情况下每次partition都能把区间对半分，这是O(n log n)。但如果每次选的基准恰好是区间里的最小或最大值，那么partition后一边为空、一边是n-1个元素，递归深度直接变成n层，每层扫描量是n，总复杂度就是O(n²)。
最典型的就是对已经有序的数组固定取最右或最左元素做基准：每轮partition几乎什么都不用分，快排直接退化成选择排序的效率。很多人初学时在这里栽过跟头——对一个有序数组排序，快排反而慢得离谱。这时你才真正理解为什么工业级快排不会傻乎乎固定选基准。
5.4 稳定性、原地性与缓存友好性
快排的一个显性短板是不稳定。partition过程中，为了把小于基准的元素交换到左侧，很可能把相等的元素交换到彼此后面，而且这种交换是跨区间的，无法保证相等元素的相对顺序。所以你对稳定排序有明确需求时（多级排序），不能直接上快排，要么换成归并排序，要么用稳定化改造的版本。
快排的另一面是原地排序。除了递归栈空间，它不需要额外的大块内存。这一点在内存受限的嵌入式环境或超大数组场景下是巨大优势。它还有很好的缓存局部性：partition操作是线性扫描内存，访问模式非常规整，CPU预取友好，实际运行速度往往比理论上更漂亮的算法更快。这也是为什么在很多语言的标准库里，快排是默认选择——它不只是理论好看，在真实硬件上真的最快。
5.5 工程级快排的细节：三数取中、随机基准、插入兜底
生产级快排不会直接裸写上面的代码。核心调优集中在三个点：
- 基准选取最狠的一招是三数取中（median-of-three）：在区间左、中、右三个位置取值，选其中位数做基准。这个手段同时解决两件事——避免有序数组落入最坏情况，也在大部分随机数据上让基准更接近区间中位数。
- 随机基准：简单地从区间里随机选一个元素作为基准。它不能保证避开最坏情况，但能把“最坏情况”变成概率事件，几乎不可能连续倒霉很多层。在对抗性输入场景下（比如在线判题、恶意测试数据），随机化是必需的。
- 小区间插入排序兜底：分治递归到区间长度小于某个阈值（经验值16到32）时不再递归，改用插入排序直接排完。这避免了小规模递归的函数调用开销，实测能带来可观加速。
我实际写快排时还会额外注意递归深度的问题。递归实现如果刚好遇到糟糕的partition，栈深度可能到n，导致栈溢出。所以我会在实现里加一个尾递归优化：先递归短的子区间，长的子区间用迭代处理，把最大递归深度控制在O(log n)。这个细节在很多教科书里不讲，但如果你写的快排要在生产环境跑大数组，这是必须考虑的。
6. 横向对比与实战选型：什么时候用它
四个算法的复杂度多层面对比，集中在一张表里看最清楚：
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 | 适用信号 |
|---|---|---|---|---|---|---|
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 | 几乎无一适合 |
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 | 数据近似有序且极在乎稳定 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 | 小规模、近似有序、流式输入 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 | 大规模随机数据、内存敏感 |
实战选型的核心不是“平均复杂度谁低就选谁”，而是一句话：你需要什么样的稳定性，你的数据长什么样，你的内存是不是吃紧。数据量小于几十个，直接用插入排序，不必纠结；数据量大且内存不吃紧，归并排序（下一篇会细讲）是最稳的选择，因为稳定且最坏情况有保证；数据量大且内存敏感，快排是对的，但要处理好基准和递归深度；数据近乎有序，插入排序的O(n)是碾压级的优势。
还有一个细节值得放上台面：比较成本和交换成本的差异。如果你的元素是巨大的对象，交换（或者移动）代价远比比较昂贵，选择排序的n-1次交换就变得有吸引力了。反之，如果元素是基本类型如int、float，比较和交换几乎一样廉价，插入排序的平均性能就要优于选择排序。很多人在选择算法时只盯着Big O，忽略了常数和操作类型，这在实际工程里会吃大亏。
我最后分享一个实用经验。手写排序时，优先写那个你能在五分钟内讲清楚“它为什么这样工作”的算法。我之前面试候选人写快排时，最欣赏的不是谁写得多漂亮，而是谁能说出“我选三数取中是因为要避免有序数组退化”这种话。排序考的不是默写，而是你是否理解操作背后的决策依据。如果你能把这篇里的“逆序对”“比较下界”“不稳定来源”讲明白，面试官对你的算法功底会立刻高看一眼。
下一篇写归并排序和堆排序时，我会把“分治的两种形态”再做一次对比：归并排序的分治是“先分后合，合并时要额外空间”，堆排序是“用数据结构驱动选择，每轮取堆顶就得到最小值”。这两个算法能补全你对排序全景的认知——尤其是归并的稳定性与堆排的原地性，正好和快排形成互补。排序这事，真的不是背模板那么简单。
