排序算法：面试通关核心策略与实战

可视化演示

动态演示排序算法的核心机制，通过基础/核心/应用/扩展四种模式展示关键概念与交互流程。

排序算法概述

想象你接到任务：整理一排被翻乱的书架，书厚度各不相同，要按厚度从小到大排好。你还没动手，先要定三件事：书多到一定程度时，你愿意等多久（时间）；桌上能不能腾出临时放书的区域（空间）；两本一样厚的书，整理完能否保持读者原本摆放的相对顺序（稳定性）。这三件事，就是排序算法的三大坐标系。

在计算机里，书架是数组，书的厚度是元素的值。排序算法就是一套把数组元素按非降序重排的指令。面试官问排序，很少让你直接背代码，而是看你对三个坐标系的敏感度：能否脱口说出时间复杂度、空间复杂度、稳定性，并能在不同场景做取舍。

比较类排序基于「两数比大小」，理论上限是下界 O(n log n)；非比较类（计数、桶、基数）通过巧妙的统计直接把元素放进正确位置，可以突破下界。稳定性描述等值元素的相对顺序：若算法是稳定的，等值的书整理后依然保持原有前后次序。这在多关键字排序中极为关键——先按价格再按销量排序时，若第二次排序稳定，第一次的价格顺序不会被破坏。

$$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)$$

1. 常数与对数阶：O(1) 表示无论书有多少本，耗时固定；O(log n) 表示每轮操作能砍掉一半书，增长非常缓慢。

$$\text{常数阶} O(1) < \text{对数阶} O(\log n)$$

2. 线性与线性对数阶：O(n) 表示每本书只被处理常数次；O(n log n) 是比较排序的极限，快排、归并、堆排都停在这个台阶。

$$\text{线性阶} O(n) < \text{线性对数阶} O(n\log n)$$

3. 平方阶与指数阶：O(n²) 对应两两比较的朴素策略；O(2ⁿ) 指数级只出现在暴力列举中。

$$\text{平方阶} O(n^2) < \text{指数阶} O(2^n)$$

定好了三把尺子，接下来的问题就是：用哪种策略来转这几百本书？有人一趟趟邻位倒腾，有人抽出来插到该去的位置，有人干脆把书拆散再合并。下面我们逐一认识这些「整理工匠」。

冒泡与选择排序

最朴素的整理策略是冒泡法：你从书架左端走到右端，遇到相邻两本书就比厚薄，厚的往后推一步。走完一趟，最厚的书就像气泡一样浮到了最右端。下一趟从最左端重新走，但不用再管已经沉底的最厚书。来来回回 n-1 趟，书架就整齐了。

冒泡排序的代码框架是两层循环：外层控制趟数，内层做相邻比较和交换。另一条同样朴素的路是选择排序：每次巡视一遍剩余的乱书堆，找出最薄的一本，与左边第一本对调。它没有冒泡那种频繁交换的「碎动作」，但比较次数完全一样。

冒泡排序平均和最坏都是 O(n²)，交换次数多、常数大；选择排序同样 O(n²)，但每趟只做一次交换、常数小一些。冒泡是稳定排序，因为只有相邻的逆序对才交换，等值元素不会被越过；选择排序不稳定——「挑最薄」时可能把前面等值书的顺序打断。背诵面试题时，这两兄弟常被拿来做「为什么需要更好算法」的反面教材。

$$\sum_{k=1}^{n-1} (n-k) = \frac{n(n-1)}{2} = O(n^2)$$

1. 单趟比较次数：第一趟比较 n-1 次，第二趟 n-2 次，逐趟递减，第 k 趟比较 n-k 次。

$$\text{第 } k \text{ 趟比较 } n-k \text{ 次}$$

2. 累积求和：把每一趟的比较次数累加，得到等差数列求和。

$$\sum_{k=1}^{n-1} (n-k) = \frac{n(n-1)}{2}$$

3. 取最高阶：展开后最高项是 n²/2，常数忽略后就是平方阶。

$$\frac{n(n-1)}{2} = O(n^2)$$

这两兄弟像刚入行的图书管理员，方法直观但费时。它们存在的意义，是让我们真切感受到「慢」长什么样——也为后面抽书插入、对半拆分等聪明方法埋下悬念。

插入与希尔排序

当你整理书架时，手里已经有一摞按厚度排好的书，新摸到一本薄书，你会怎么办？自然是从左到右扫一眼，找到它该待的位置「塞」进去，后面的书往右挪一格。这就是插入排序——像整理扑克牌一样，把每一张新牌插进手里已有的有序牌堆，一边摸牌一边理牌。

插入排序的代码是：外层遍历每个元素，内层把它与前面已排序序列从右往左比较，找到合适位置插入。它最迷人的特性是「自适应」：如果书架近乎有序，每本书只需挪动一两格，整体近乎 O(n)；但如果完全逆序，每次都要从头挪到尾，退化成 O(n²)。

希尔排序是对插入的改进：先让相距较远的书「大步比较交换」，把序列迅速变得大致有序，最后再用普通插入排序收尾。面试中希尔排序一般只需说出「分组插入」的思想和复杂度介于 O(n) 与 O(n²) 之间。核心考点在于：插入排序在「近乎有序」的数据上，是 O(n log n) 算法都难以匹敌的选项——因此它常被用作快速排序在小区间上的收尾策略。

$$T_{\text{insert}}(n) = \begin{cases} O(n), & \text{数据近乎有序} \\ O(n^2), & \text{数据完全逆序} \end{cases}$$

1. 最优情况：数据基本有序时，每本书只与前面少数几本比较就落位，总耗时线性。

$$T(n) = O(n)$$

2. 最坏情况：数据完全逆序时，第 k 个元素平均要与前面 k/2 个元素比较，总和是平方量级。

$$T(n) = \sum_{k=1}^{n} k = O(n^2)$$

所以别小看这位「见缝插针」的管理员——书越整齐他越快。排序世界没有绝对强弱，只有是否适合当前书架的乱序程度。

快速排序分治

资深管理员会这样干：随手抽一本书当「基准」，把比它薄的全放到左区，比它厚的全放右区，基准夹在中间。接着对左右两堆书分别重复同样操作。这就是快排，典型的「分而治之」——把大难题拆成小难题，各自解决再拼起来。

快排的核心是 partition：一趟扫描把数组分成「小于基准 | 基准 | 大于基准」三个区域，并返回基准最终下标。基准选得好不好，直接决定算法命运。如果每次基准都恰好是中位数，左右规模相当，递推式 T(n) = 2T(n/2) + O(n) 解出 O(n log n)；如果基准总选到最小或最大，就退化成 O(n²)。

面试的高频考点是「如何规避最坏情况」。经典手法有：三数取中（首、中、尾取中位数做基准）、随机选基准、子数组规模小于阈值时切换插入排序。手写快排推荐记忆 Lomuto 分区法：pivot 取末尾元素，i 指针维护「小于区」边界，j 指针从左往右扫描，遇到小于等于 pivot 的元素就与 i 交换。代码短、不容易写错，是面试中最稳的版本。

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n) = O(n\log n)$$

1. 划分代价：一趟 partition 扫描整个数组，花费 O(n)。

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$

2. 递归展开：每次分成两个规模为 n/2 的子问题，递归树每一层的总代价都是 O(n)，共有 log₂n 层。

$$O(n) \times \log_2 n = O(n\log n)$$

三数取中就像老管理员凭经验挑一本「不太极端的书」当基准，运气稳定，书架也随之快速整好。快排是面试中出场率最高的排序，必须能闭眼写出 partition。

归并排序合并

另一位管理员的思路截然不同：先把整架书从中间一分为二，再各自一分为二，直到每堆只剩一本书——单本书天然有序。然后开始「两两合并」：两堆有序书各抽最薄一本比较，薄的进新堆。如此一层层合并回去，最终得到完整有序书架。这就是归并排序。

归并排序的时间递推与快排相同，T(n) = 2T(n/2) + O(n)，稳定在 O(n log n)，且不受基准选择影响——无论数据多乱，它都稳定发挥。代价是需要额外 O(n) 空间存放合并结果，这是它与快排最大的差异。

归并的「合并两个有序数组」是一道独立高频题：双指针分别指向两个数组头部，比较后把较小值写入辅助数组。归并排序天生稳定，因为合并时遇到相等元素，优先取左半边的，不破坏相对顺序。正因如此，外部排序（磁盘数据量巨大、无法全部装入内存）都爱用归并：把大文件切成能装进内存的小块分别排好，再多路归并成大文件——数据库 ORDER BY 底层就有它的身影。

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n), \qquad S(n) = O(n)$$

1. 拆分：把规模 n 的问题拆成两个 n/2 的子问题，递归直到单元素。

$$T(n) = 2T\left(\frac{n}{2}\right) + O(n)$$

2. 合并代价：合并两个有序子数组时最多比较 n-1 次，每层合计 O(n)。

$$\text{每层合并总代价} = O(n)$$

3. 空间账本：辅助数组长度与 n 同阶，递归深度 log n 不计入辅助空间。

$$S(n) = O(n)$$

归并管理员不求快而求稳：内存多花一点，换来雷打不动的 O(n log n) 和稳定性。面试里只要写对 merge，这道题基本稳了。

堆排序结构

还有一种「垒书塔」的整理法：把所有书堆成一颗树，保证「爸爸永远比儿子厚」，塔尖是最厚的那本。每次取走塔尖放进书架末端，再把剩余的书重新堆出新的塔尖——重复 n 次，书架就齐了。这个「爸爸比儿子厚」的结构，叫大顶堆。

堆是一棵完全二叉树，用数组就能存：下标 k 的左右孩子是 2k+1、2k+2。建堆从最后一个非叶子节点开始做「下沉」（让父亲与较大的儿子交换，直到父亲大于等于两个儿子）。面试必须记住两个结论：单次下沉 O(log n)，但整体建堆是 O(n)——因为越矮的节点数量越多，平均下沉高度很小。

堆排序的完整流程：建堆 → 重复「堆顶与末尾交换，缩小堆范围，再下沉堆顶」。它原地完成，空间 O(1)，时间稳定 O(n log n)，但常数比快排大，实际速度通常不如快排。堆的真正舞台是 Top-K 问题：找前 K 大元素，维护一个大小为 K 的小顶堆，每来一个新元素与堆顶比，比堆顶大就替换并下沉，最终堆里就是前 K 大。这个套路在流式数据与推荐系统中极其常用，几乎是算法面试的必问题。

$$\text{单次下沉} = O(\log n), \qquad \text{整体建堆} = O(n)$$

1. 单次下沉：节点从堆顶一路下坠到叶子，路径长度不超过树高。

$$h = \log_2 n, \quad T_{\text{sink}} = O(\log n)$$

2. 整体建堆：所有非叶子节点从下往上做下沉，总代价被「矮节点多、高节点少」抵消，结果只是线性阶。

$$T_{\text{heapify}} = \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \times h = O(n)$$

垒书塔的管理员从不慌：每次只取塔尖，稳扎稳打。堆排序和堆结构是面试的「万能工具箱」——排序、Top-K、优先级队列都从它来。

线性时间排序

如果书架上的书只有五档厚度：超薄、薄、中、厚、超厚，聪明的管理员绝不会一本本两两比较，而是先数清每一档有几本，然后按档位直接摆进对应区域。整个过程不做比较，只做统计——这就是线性时间排序的思路：跳出「两两比较」框架。

计数排序：数据范围是 0~k，开一个长度 k+1 的计数数组，遍历一遍统计每个值出现次数，再按次数把数字回填。桶排序：把数据均匀分到若干个桶里，桶内分别排序，再依次倒出。基数排序：按个位、十位、百位逐位做稳定排序，从低位到高位（可以用计数排序当内层排序），得到全局有序。

这三兄弟都突破了比较排序 O(n log n) 的下界，但都有前提：计数排序要求 k 不太大，否则计数数组过大；桶排序要求数据分布均匀，否则桶之间严重不平衡；基数排序要求数据可分解成有限位。面试常考一个犀利问题：「计数排序是 O(n + k)，如果 k 远大于 n，它比快速排序快吗？」答案是不快，甚至更慢——此时空间和时间都被 k 拖垮。

$$T(n) = O(n + k)$$

1. 统计阶段：遍历 n 个元素做计数，耗时 O(n)。

$$\text{计数遍历} = O(n)$$

2. 回填阶段：从计数数组取出每个值出现次数，共 n 个元素回填，再扫描 k 个计数桶。

$$\text{扫描计数桶} = O(k)$$

3. 加总：两阶段串行相加，保留 n 与 k 中的较大者。

$$O(n) + O(k) = O(n + k)$$

当书的厚度档位极少时，管理员用「数数 + 摆位」瞬间搞定。面试中记住一句话：能不能用线性排序，取决于数据取值范围是否合理可控。

面试实战套路

现在你是一位即将上战场的整理大师，八种策略烂熟于心。但面试官不会只问「背一遍快排」，他更爱问：「有一千万本书要按厚度排，内存只够装十分之一，用哪个方法？」「找出第 100 厚的书，最快多快？」只有在脑中有一张「战术地图」，才能见招拆招。

第一张地图是复杂度速查：比较类最优 O(n log n)（快排、归并、堆排），朴素类 O(n²)（冒泡、选择、插入），线性类 O(n + k)。选型口诀：乱序求快用快排，稳定优先用归并，内存吃紧用堆排，近乎有序用插入。第二张地图是边界条件：空数组、单元素、全等、正序、逆序、大量重复——动手写代码前先在脑中跑一遍，这往往是区分新人老手的分水岭。

高频变种题「快速选择（QuickSelect）」是快排的脱胎：找第 K 大元素，只对包含答案的那一侧递归。期望复杂度 O(n)，递推 T(n) = T(n/2) + O(n)。记忆点和快排一样——基准随机或三数取中，否则退化 O(n²)。另一个高频变种是「多关键字排序」，本质考察稳定性：先按次要关键字排序，再按主要关键字做稳定排序。处理大量重复数据的「三路快排」也值得掌握：把数组拆成小于、等于、大于三区，重复元素不参与递归，在重复多的数据上快得多。

$$T(n) = T\left(\frac{n}{2}\right) + O(n) = O(n)$$

1. 单侧递归：QuickSelect 每轮只进入包含第 K 大元素的那一半，规模减半。

$$T(n) = T\left(\frac{n}{2}\right) + O(n)$$

2. 累加展开：每层代价 O(n)、O(n/2)、O(n/4)… 是等比数列，总和收敛为 O(n)。

$$O(n) + O\left(\frac{n}{2}\right) + O\left(\frac{n}{4}\right) + \cdots = O(n)$$

有了这张战术地图，无论面试官把书架摆成什么样——乱序、有序、极多重复、内存受限——你都能第一时间选出正确的整理策略，并写对边界。这就是排序面试通关的核心心法。

AI 应用场景

Python 演示

import random  def quick_sort(arr):    """经典快速排序：pivot 取三数中位数，规避最坏情况。"""    if len(arr) <= 1:        return arr    first, mid, last = arr[0], arr[len(arr) // 2], arr[-1]    pivot = sorted([first, mid, last])[1]    less, equal, greater = [], [], []    for x in arr:        if x < pivot:            less.append(x)        elif x == pivot:            equal.append(x)        else:            greater.append(x)    return quick_sort(less) + equal + quick_sort(greater)  def partition(arr, low, high):    """Lomuto 分区：原地交换，返回基准最终位置。"""    pivot = arr[high]    i = low - 1    for j in range(low, high):        if arr[j] <= pivot:            i += 1            arr[i], arr[j] = arr[j], arr[i]    arr[i + 1], arr[high] = arr[high], arr[i + 1]    return i + 1  def quick_sort_inplace(arr, low=0, high=None):    """原地版快速排序，避免额外数组开销。"""    if high is None:        high = len(arr) - 1    if low < high:        p = partition(arr, low, high)        quick_sort_inplace(arr, low, p - 1)        quick_sort_inplace(arr, p + 1, high)    return arr  if __name__ == '__main__':    test = [random.randint(0, 100) for _ in range(10)]    print('原始：', test)    print('排序：', quick_sort(test))    assert quick_sort(test) == sorted(test)     inplace = test[:]    quick_sort_inplace(inplace)    print('原地：', inplace)    assert inplace == sorted(test)    print('全部通过！')

1. pivot = sorted([first, mid, last])[1]三数取中：取首、中、尾三个元素的中位数当基准，避免每次挑到极端值。
2. less, equal, greater = [], [], []三路划分：把数组分成小于、等于、大于三堆，重复元素不参与递归。
3. return quick_sort(less) + equal + quick_sort(greater)递归拼接：左右两侧分别排序后，与等于区直接连接。
4. pivot = arr[high]Lomuto 分区选末尾元素做基准，实现最简洁。
5. if arr[j] <= pivot:小于等于都放进左区，保证等值元素不被漏掉。
6. arr[i + 1], arr[high] = arr[high], arr[i + 1]把基准从末尾换到正确位置，完成一趟分区。
7. if low < high:递归终止条件：子区间只剩一个元素时不再划分。

常见误区

面试题