第9章：排序算法（上）

---

元数据卡

属性	值
难度	（基础型）
前置	数组、链表、递归
关键词	选择排序·冒泡排序·插入排序·希尔排序·归并排序·分治·稳定排序
预计阅读	90 分钟
代码行	~180 行（三语言合计）

---

你的进度

老陈教过你怎么用数据，但没教过你怎么整理它们。你面前一堆杂乱无章的物品（输入），你想快速找到最小的、最大的、中间的——排序是你的第一件武器。

你现在站在整个算法的 起点。

不对，不是 Hello World 那种起点。而是你手头有一个混乱无序的数组，你想让它有序。就这么一个朴素的需求，催生了计算机科学里最经典的一族算法——排序。

第 6 ~ 8 章你一直在建结构（栈、队列、树），现在该让这些结构里的数据听你的话了。本章是排序的上半场，聚焦 O(n²) 的基础排序和 O(n log n) 的归并排序。从最直觉的选、冒、插，到跨越式的希尔，再到真正工业级的分治——你会亲眼看见「聪明」怎么一步步取代「蛮力」。

---

你的任务

本章分层

• 必读：选择排序（每轮选最小放前面）；插入排序（打牌理牌法）——理解它为什么在近乎有序时达到 O(n)；归并排序（递归版）——分治思想的完美体现
• 选读：归并排序的迭代版（Bottom-up）；希尔排序的基本思路（gap 递减的插入排序）
• 进阶：归并排序的复杂度证明（递归树）；自然归并排序（检测已有有序 runs）

本章不会要求你掌握

• 冒泡排序的工程应用（作为反例了解即可）
• 希尔排序的 gap 序列优化
• TimSort 的实现细节

读完本章，你应当能：

1. 徒手写出选择、插入两种 O(n²) 排序，说出与冒泡的区别
2. 理解插入排序为什么在几乎有序时很快
3. 手写归并排序（递归版），分析空间换时间的取舍
4. 口头说明为什么归并排序在任何输入下都是 O(n log n)
5. （选）了解希尔排序的基本思路——第一个突破 O(n²) 的排序

---

遭遇战→获得技能

① 选择排序（Selection Sort）—— 最直觉的「找最小」

核心直觉：每轮选最小的，放到前面去。 像打扑克牌理牌时一张一张抽出最小的。

Python 实现

def selection_sort(arr):
 """每轮找出剩余部分的最小值，与当前位置交换"""
 n = len(arr)
 for i in range(n - 1):
 min_idx = i
 for j in range(i + 1 n):
 if arr[j] < arr[min_idx]:
 min_idx = j
 arr[i] arr[min_idx] = arr[min_idx] arr[i]
 return arr

# 试试看
test = [64 25 12 22 11]
print(selection_sort(test)) # → [11 12 22 25 64]

复杂度分析

	最好	最坏	平均	空间
选择排序	O(n²)	O(n²)	O(n²)	O(1)

关键缺陷：即使数组已经有序了，它还是要完整地跑完两层循环。浪费扫描，不聪明。

Java 对比

// Java: selection sort in-place
void selectionSort(int[] arr) {
 int n = arr.length;
 for (int i = 0; i < n - 1; i++) {
 int minIdx = i;
 for (int j = i + 1; j < n; j++) {
 if (arr[j] < arr[minIdx]) minIdx = j;
 }
 int tmp = arr[i];
 arr[i] = arr[minIdx];
 arr[minIdx] = tmp;
 }
}

C++ 对比

// C++: 使用 std::swap 更简洁
void selectionSort(vector<int>& arr) {
 int n = arr.size();
 for (int i = 0; i < n - 1; ++i) {
 int minIdx = i;
 for (int j = i + 1; j < n; ++j)
 if (arr[j] < arr[minIdx]) minIdx = j;
 swap(arr[i] arr[minIdx]);
 }
}

三语言的逻辑完全一致，差别只在语法糖。swap 在 C++ 是标准库提供的，在 Python 是元组解包，在 Java 得自己写临时变量。 这种细节在实际面试里会咬你一口。

---

② 冒泡排序（Bubble Sort）—— 作为反例了解

冒泡排序的实用性几乎为零，这里作为反例——让你看到"两两交换"为什么不是好策略。

核心直觉：相邻元素两两比较，大的往右「浮」。 每轮结束，最大的元素一定在最右边。

def bubble_sort(arr):
 """标准冒泡：相邻比较，大的上浮"""
 n = len(arr)
 for i in range(n - 1):
 for j in range(n - 1 - i):
 if arr[j] > arr[j + 1]:
 arr[j] arr[j + 1] = arr[j + 1] arr[j]
 return arr

# 试试
print(bubble_sort([5 1 4 2 8])) # → [1 2 4 5 8]

优化版 —— 提前终止

def bubble_sort_early(arr):
 """加入 swapped 标志，提前结束"""
 n = len(arr)
 for i in range(n - 1):
 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

# 最坏情况依然 O(n²)，但最好情况降至 O(n)

什么时候该用它？ 几乎从不。除非你确定数据几乎有序，否则冒泡比选择还慢。但它的教学价值在于：「交换」是排序最朴素的原子操作，所有更快的算法都在思考「能不能少交换几次」。

③ 插入排序（Insertion Sort）—— 打牌理牌法

核心直觉：把当前牌插入到已排序的牌堆中正确位置。 你理扑克牌时就是这么干的。

def insertion_sort(arr):
 """摸一张牌，插入前面已排序区间的正确位置"""
 n = len(arr)
 for i in range(1 n):
 key = arr[i]
 j = i - 1
 while j >= 0 and arr[j] > key:
 arr[j + 1] = arr[j] # 后移腾位
 j -= 1
 arr[j + 1] = key
 return arr

print(insertion_sort([12 11 13 5 6])) # → [5 6 11 12 13]

插入排序为什么重要？ 因为它有两个好性质：

1. 在线：可以一边读数据一边排
2. 对几乎有序的数据极快（O(n)）

这两个性质让它成为 工业级排序的粘合剂——TimSort 在数据接近有序时退化成插入排序。

C++ 对比：用迭代器风格

void insertionSort(vector<int>& arr) {
 for (size_t i = 1; i < arr.size(); ++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;
 }
}

---

④ 历史旁注：希尔排序（Shell Sort）—— 第一个突破 O(n²) 的排序

希尔排序是历史性的突破，但现代工程中已被更优方案取代。这里作为历史旁注了解即可。

1959 年，Shell 提出一个洞见：插入排序太慢是因为每次只挪一位。如果我让元素一次跨好几步，排序不就加速了吗？

def shell_sort(arr):
 """希尔排序：递减步长（gap）的插入排序"""
 n = len(arr)
 gap = n // 2

 while gap > 0:
 # 对每个子序列做插入排序
 for i in range(gap n):
 temp = arr[i]
 j = i
 while j >= gap and arr[j - gap] > temp:
 arr[j] = arr[j - gap]
 j -= gap
 arr[j] = temp
 gap //= 2 # 缩小步长

 return arr

print(shell_sort([9 8 3 7 5 6 4 1])) # → [1 3 4 5 6 7 8 9]

为什么要逐渐缩小 gap？

想象一下：gap = 4 时，你实际上在排 4 个独立的「子数组」。这些子数组变得大致有序后，gap = 2 再排一次，最后 gap = 1 一次常规插入排序就能搞定。分而治之的思想，在希尔排序里已经萌芽了。

复杂度迷思：希尔排序的复杂度至今未彻底解决。已知最坏 O(n²)，但精心选择的 gap 序列可以达到 O(n^(3/2)) 甚至 O(n log² n)。

---

⑤ 归并排序（Merge Sort）—— 真正工业级的分治

核心直觉：把数组对半切，分别排好，再合并。 递归地切到只剩一个元素（天然有序），然后回溯合并。

5.1 Top-down 归并（递归版）

def merge_sort(arr):
 """归并排序入口"""
 if len(arr) <= 1:
 return arr

 mid = len(arr) // 2
 left = merge_sort(arr[:mid])
 right = merge_sort(arr[mid:])

 return merge(left right)


def merge(left right):
 """合并两个已排序数组"""
 result = []
 i = j = 0

 while i < len(left) and j < len(right):
 if left[i] <= right[j]:
 result.append(left[i])
 i += 1
 else:
 result.append(right[j])
 j += 1

 # 收尾
 result.extend(left[i:])
 result.extend(right[j:])
 return result

print(merge_sort([38 27 43 3 9 82 10])) # → [3 9 10 27 38 43 82]

合并过程可视化

左: [27 38 43] 右: [3 9 10 82]
 ↑ ↑
i=0 j=0

比较 27 和 3 → 取 3
比较 27 和 9 → 取 9
比较 27 和 10 → 取 10
比较 27 和 82 → 取 27
... 以此类推

5.2 Bottom-up 归并（迭代版）

递归版直观但会占用 O(log n) 的调用栈。迭代版彻底去掉递归，从长度为 1 的子数组开始两两合并：

def merge_sort_bottom_up(arr):
 """自底向上归并排序"""
 n = len(arr)
 size = 1 # 子数组初始大小

 while size < n:
 for left in range(0 n size * 2):
 mid = left + size
 right = min(left + size * 2 n)

 if mid < right: # 有第二个子数组才需合并
 # 合并两个子数组 arr[left:mid] 和 arr[mid:right]
 left_arr = arr[left:mid]
 right_arr = arr[mid:right]

 i = j = 0
 k = left
 while i < len(left_arr) and j < len(right_arr):
 if left_arr[i] <= right_arr[j]:
 arr[k] = left_arr[i]
 i += 1
 else:
 arr[k] = right_arr[j]
 j += 1
 k += 1

 while i < len(left_arr):
 arr[k] = left_arr[i]
 i += 1
 k += 1

 while j < len(right_arr):
 arr[k] = right_arr[j]
 j += 1
 k += 1

 size *= 2

 return arr

print(merge_sort_bottom_up([38 27 43 3 9 82 10]))

Java 的归并实现（in-place 合并版）

void merge(int[] arr int left int mid int right) {
 int n1 = mid - left + 1;
 int n2 = right - mid;
 int[] L = new int[n1];
 int[] R = new int[n2];

 System.arraycopy(arr left L 0 n1);
 System.arraycopy(arr mid + 1 R 0 n2);

 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 mergeSort(int[] arr int left int right) {
 if (left < right) {
 int mid = left + (right - left) / 2;
 mergeSort(arr left mid);
 mergeSort(arr mid + 1 right);
 merge(arr left mid right);
 }
}

---

常见陷阱

为什么归并排序「最坏也是 O(n log n)」？

这是它最性感的地方。

看归并排序的递归树：每次切一半，深度是 log₂n。每层合并的总代价是 O(n)。所以总代价 = 层数 × 每层工作量 = O(log n × n)。

这比 O(n²) 好多少？拿 n = 1000000 举例：

• O(n²)：≈ 10¹² 次操作（几小时到几天）
• O(n log n)：≈ 20 × 10⁶ 次操作（毫秒级）

这就是分治的力量。你在第 6 章学的递归树分析，在这里第一次产生实际价值。

三种 O(n²) 排序怎么选？

	最好场景	交换次数	稳定性	实际用
选择	没用	最少（n 次）	不稳
冒泡	几乎有序 O(n)	最多	稳定	（除非面试）
插入	几乎有序 O(n)	中等	稳定	（作为高级排序的垫脚石）

经验法则：除非面试官指定，否则不要用 O(n²) 排多于几百个元素。

---

通关挑战

1. 反转实现：用递归实现冒泡排序——你做得到吗？
2. 步长序列实验：在希尔排序中用不同的 gap 序列（Shell 原始、Knuth、Sedgewick），对 10⁵ 个随机数测量性能
3. 归并空间优化：当前的 merge() 函数每次合并都分配新数组。改成只分配一个全局辅助数组，反复使用
4. 自然归并排序：先扫描找出已经有序的「自然 runs」，再合并它们——比严格二分更快

---

验收标准

• [ ] 能徒手写出五种排序的 Python 实现
• [ ] 能解释为什么插入排序在几乎有序时很快（冒泡也能 O(n)，但插入常数更小）
• [ ] 能画出 n = 8 的归并排序递归树
• [ ] 能区分 top-down 和 bottom-up 归并的优缺点
• [ ] 敢回答面试题：「手写归并排序，分析复杂度」

---

常见卡点

卡点	破解
归并的递归容易晕	用纸笔画递归树，标记每个节点处理的区间
希尔排序的 gap 选择	先记住 gap = n/2 → n/4 → ... → 1，再探索更优序列
冒泡优化后依然很慢	冒泡的交换次数是逆序对数量，和插入一样，但常数大（每次交换 3 次赋值 vs 插入的 1 次移位）
Bottom-up 归并的下标	用纸笔跑 size=1→2→4 的过程，下标错位的根本原因是 right 需要 min() 防越界

---

现在不需要理解

• TimSort（Python / Java 实际用的排序）—— 它本质是「归并 + 插入」的混合体，但夹杂了很多工程细节（galloping mode、run 的反向合并）。留到后面章节讲「工业级算法优化」时再碰。
• in-place 归并 —— 学术界有 O(1) 额外空间的归并算法，但工程上几乎不用（常数太大），面试也不会考。

---

旅人笔记

• 选择排序「最老实」，但无论输入好坏都 O(n²)。
• 冒泡排序「最直观」，但性能也是真的差。
• 插入排序「最实用」，小数组首选，高级排序的基石。
• 希尔排序「第一次飞跃」，证明了一个道理：有时候换个大步子思考，就能突破瓶颈。
• 归并排序「分治的完美例题」，稳定、可预测、易理解——缺点只有一个：吃内存。

一句话记住本章：「基础排序拼常数，归并排序拼空间，都在为下一章的快速排序造势。」

---

→ 下一站预告

第 10 章将三路出击：

1. 快速排序 —— 工业级的王者，平均最快但最坏 O(n²)
2. 堆排序 —— 借助二叉堆，不额外吃空间
3. 线性时间排序 —— 计数 / 基数 / 桶排序

以及一个灵魂拷问：比较排序最快能有多快？（答案：O(n log n)）

→ 进入第 10 章：排序算法（下）