---
title: "08-排序"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 08 排序

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 8 篇，相关系列见 [[00-基础与理论|基础与理论]]。

排序是 408 数据结构的收官章，也是**稳定性 + 复杂度总表**必须一字不差背下来的地方。本章按"简单 → 分治 → 计数 → 外部"推进，核心资产是一张总表和一次快排 partition 手算。

**稳定性**定义：相等元素排序后**相对次序不变**。为什么重要：多关键字排序要"先按次要键排、再按主要键**稳定**排"——不稳定算法会毁掉前面的排序成果（数据库 ORDER BY 多列的现实需求）。

## 一、插入排序家族

### 直接插入：像整理扑克牌

第 i 张牌向前比较，比它大的都往后挪一格，插入。

- 最好（已有序）**O(n)**，最坏（逆序）O(n²)，平均 O(n²)；**稳定**
- **数据基本有序时它是最快的 O(n) 级算法**——所以混合排序（Timsort）里负责小段

### 折半插入：只省比较不省移动

插入位置用折半找（O(log n)），但**移动次数不变**，总量仍 O(n²)。稳定。

### 希尔排序：分组插入

按增量 d 分组做插入排序，d 逐轮减半到 1——**先宏观粗调、最后微调**，把"逆序对"提前消灭。

- 复杂度 O(n^1.3) 左右（依增量序列，408 只记"约 n^1.3，最坏 O(n²)"）；**不稳定**
- ⚠️ 希尔是唯一"分组"的插入排序，选择题常拿它和快排的"分治"混淆——希尔没有递归

## 二、交换排序家族

### 冒泡：一轮把最大顶到末尾

相邻逆序就交换，一轮冒一个最大值。加 `swapped` 标志，**已有序时一轮就停 = O(n)**。平均 O(n²)；**稳定**。

### 快速排序 ⭐（必考）

**分治思想**：选一个基准 pivot，一趟 partition 把数组切成"≤ pivot | pivot | ≥ pivot"三段，递归两侧。

**一趟 partition 手算（挖坑法）**：对 {49, 38, 65, 97, 76, 13, 27}，pivot = 49：

```
初始:  [49, 38, 65, 97, 76, 13, 27]   pivot=49, low=0, high=6
1. high 找 <49: 27 → 填坑 low:  [27, 38, 65, 97, 76, 13, _]  low=0
2. low 找 >49:  65 → 填坑 high: [27, 38, _, 97, 76, 13, 65]  high=2
3. high 找 <49: 13 → 填坑 low:  [27, 38, 13, 97, 76, _, 65]  low=2
4. low 找 >49:  97 → 填坑 high: [27, 38, 13, _, 76, 97, 65]  high=3
5. low==high=3 → pivot 放 3 号位
结果:  [27, 38, 13, 49, 76, 97, 65]   ← 一趟结束，49 归位第 4 位 ✅
```

- 平均 **O(n log₂n)**（每趟 O(n)，log n 层递归）；**空间 O(log₂n)**（递归栈）
- **最坏 O(n²)**：序列已有序/逆序 + 固定取首元素为 pivot（每层只切出 1 个）→ 解药：**三数取中 / 随机选 pivot**
- **不稳定**（如 [3a, 3b, 2]：3b 可能被换到 3a 前面）
- 划分越平衡越快——理想每次对半切；这也是它和归并的本质差别（快排先干活后递归，归并先递归后干活）

## 三、选择排序家族

### 简单选择：每轮挑最小放前面

比较 O(n²) 次雷打不动（无论有序与否），移动最多 O(n)。**不稳定**（例：[3a, 3b, 1] 一轮后 3b 跑到 3a 前）。

### 堆排序 ⭐

**完全二叉树顺序存储**（[[05-树与二叉树|树]]性质 5：i 的孩子 2i、2i+1）当优先队列：

- **大根堆**（父 ≥ 子）排升序：建堆 → 堆顶（最大）与末尾交换 → 堆大小减 1、**向下调整（sift-down）** → 循环
- **建堆 O(n)**：从最后一个非叶结点 ⌊n/2⌋ 倒序调整；**每次调整 O(log n)**，总共 **O(n log₂n)** 雷打不动（最坏也是）
- **不稳定**；空间 O(1)
- ⚠️ 手算题：给序列建大根堆，画树、从 ⌊n/2⌋ 结点开始逐个下沉——口算顺序：先看最后一片"父-双子"，从后往前
- 💡 "Top K 大问题用小根堆维护 K 个元素" = 堆排序思想的应用，[[00-刷题理模型|刷题理模型]] 高频

## 四、归并排序与基数排序

### 归并（2 路归并）⭐

分治到单元素，两两**有序合并**：

- 最好最坏平均都是 **O(n log₂n)**；**空间 O(n)**（辅助数组）；**稳定**——它是"稳定 + O(n log n)"的唯一常规选择
- 手算：{49,38,65,97,76,13,27} 第 2 趟归并后 = 4 组各 2 元素内部有序：[38,49,65,97,13,76,27]？注意第 1 趟 [38,49],[65,97],[13,76],[27]——27 落单；第 2 趟 [38,49,65,97],[13,27,76]——**"第 k 趟后子序列长 2^k"**，408 常考"第 2 趟后的状态"

### 基数排序：不比较，按位分桶

 LSD（最低位优先）：按个位分桶 → 按桶序收集 → 按十位分桶 → …d 轮后有序。

- 复杂度 **O(d(n + r))**：d 位数、r 基数（十进制 r=10）——**与 n 几乎线性**，前提是 d、r 不大
- **稳定**；空间 O(r)
- ⚠️ 唯一"不基于比较"的排序（计数/桶排序同族）；大题考"分配-收集"过程手写

## 五、必背总表（408 原题就考这张表的排列组合）

| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入 | **O(n)** | O(n²) | O(n²) | O(1) | ✅ 稳定 |
| 折半插入 | O(n log 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²) | O(n²) | O(n²) | O(1) | ❌ 不稳定 |
| 堆 | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ 不稳定 |
| 归并 | O(n log n) | O(n log n) | O(n log n) | **O(n)** | ✅ 稳定 |
| 基数 | O(d(n+r)) | 同左 | 同左 | O(r) | ✅ 稳定 |

**记忆钩子**：

- **稳定四兄弟**：插（直接/折半）、冒、归、基——"**插冒归基**"（想象插着香（烟）冒烟的鸡）
- **不稳定三 + 希**：快、选、堆、希尔——"**快些选一堆**"（选一堆快的）
- **最坏仍 O(n log n)** 的：堆、归并（+基数不比较无此概念）
- **原数组有序时最快**：直接插入 / 冒泡（O(n)）；**反而最慢**：快排（O(n²)）
- **空间 O(n)**：归并；**O(log n)**：快排递归栈；其余 O(1)（基数 O(r)）

### 各场景选型（面试）

- 通用库排序 → 混合派：**Timsort**（归并+插入，稳定，Python/Java 对象排序）、**Introsort**（快排+堆排+插入，C++ `std::sort`）
- 求前 K 大 → 小根堆 O(n log K)
- 整数、位数少 → 基数/计数
- 稳定性硬需求 → 归并系
- 内存塞不下 → 外部排序（见下）

## 六、外部排序：内存装不下的大文件（一段话）

k 路归并：先把大文件**分块读入内存排序**成若干有序段（run）写回磁盘，再**多路归并**。败者树让 k 路归并每次取最小只需 O(log k)；**置换-选择排序**生成更长的初始段减少归并遍数；**最佳归并树**（哈夫曼思想的复用，[[05-树与二叉树|树]]）安排归并顺序使 I/O 最少。408 只考概念：**败者树 / 置换选择 / 最佳归并树**三个名词对号入座。

## 七、盲点自测

1. 稳定的四种排序？（插入、冒泡、归并、基数）
2. 快排最坏什么时候发生？怎么防？（有序 + 固定 pivot；三数取中/随机）
3. 建堆从哪个下标开始？（⌊n/2⌋ 倒序下沉）
4. 哪个排序一趟能保证一个元素最终归位？（快排、简单选择、堆（顶元素交换）、冒泡——**插入和归并不行**）
5. "第 2 趟归并后"的子序列长多少？（2²=4）
6. 数据基本有序选什么？（直接插入——O(n)）
7. 空间 O(1) 且 O(n log n) 且不稳定的？（堆排序）
8. Top K 用大根堆还是小根堆？（K 大用**小**根堆，堆顶是 K 个里最小的，随时可被更大的顶替）

## 八、动手玩

```python
# 快排挖坑法 partition（对照本文手算）
def quicksort(a, lo=0, hi=None):
    hi = len(a) - 1 if hi is None else hi
    if lo >= hi: return
    pivot, i, j = a[lo], lo, hi          # 挖坑：pivot 存起来
    while i < j:
        while i < j and a[j] >= pivot: j -= 1   # 右边找小的填左坑
        a[i] = a[j]
        while i < j and a[i] <= pivot: i += 1   # 左边找大的填右坑
        a[j] = a[i]
    a[i] = pivot                          # 基准归位
    quicksort(a, lo, i-1); quicksort(a, i+1, hi)

arr = [49, 38, 65, 97, 76, 13, 27]
quicksort(arr)
print(arr)    # [13, 27, 38, 49, 65, 76, 97]

# 亲手验证"第 2 趟归并后子序列长 4"
import math
def merge_pass_state(a, k):              # k=2^趟数
    return [sorted(a[i:i+k]) for i in range(0, len(a), k)]
print(merge_pass_state([49,38,65,97,76,13,27], 4))
# [[38,49,65,97],[13,27,76]] —— 组内有序，正好是"第 2 趟后"的状态
```

## 参考资料

- 王道《数据结构考研复习指导》第 8 章——总表 + 手算题的标准口径
- 《算法图解》第 4 章——快排与 D&C 的图解
- [[08-IO管理]]——外部排序与磁盘 I/O 的配合
- [[00-刷题理模型|刷题理模型]]——排序/堆题单（合并 K 个链表、数组第 K 大、手撕快排）

🏁 **基础与理论六大分区至此全部完成**：速览、信息表示、操作系统、计算机网络、计算机组成原理、数据结构——408 四门齐了。从理论到实战，下一站：[[00-刷题理模型|刷题理模型]]（算法刷题的感悟体笔记，与本章配套使用）。**算法是数据结构的延伸**——算法区已重制为独立分区，正式入口 [[00-算法|00-算法]]，逐章对应的板子见 [[00-数据结构总览|总览]]"通往算法"锚点处。

⬅️ [[07-查找|查找]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[00-刷题理模型|刷题理模型]]