第 16 章 · 经典排序算法与场景选型
本章目标：理解 时间/空间复杂度 与 稳定性 概念；手写 冒泡、选择、插入、归并、快速、堆 等经典排序；掌握 计数排序、基数排序 适用边界；知道 Python sorted() / list.sort() 底层思路；能根据数据规模与场景选型。
学时建议：4～5 小时（含 2 小时手写与对比实验）
前置：ch04 列表与 sorted() 入门；ch05 函数与递归（归并/快排需要）。
16.1 为什么要学排序
| 场景 | 排序的作用 |
|---|---|
| 商品列表 | 按价格、销量、上架时间展示 |
| 排行榜 | Top N 用户、热门搜索词 |
| 数据库 | ORDER BY 依赖索引或排序算法 |
| 日志分析 | 按时间线合并多文件 |
| 调度系统 | 按优先级处理任务 |
未排序 → 查找/展示成本高
排序后 → 二分查找、双指针、滑动窗口等算法才好用本章原则：工程里 99% 用语言内置排序；手写算法是为了理解复杂度与面试/底层思维，而非生产重复造轮子。
16.2 评价指标
| 指标 | 含义 | 关注点 |
|---|---|---|
| 时间复杂度 | 随数据量 n 增长的操作次数 | 平均 / 最坏 |
| 空间复杂度 | 额外占用内存 | 是否原地 in-place |
| 稳定性 | 相等元素排序后相对顺序是否不变 | 多字段排序时常需要 |
常见量级（n = 元素个数）：
| 符号 | 名称 | 直觉 |
|---|---|---|
| O(1) | 常数 | 与 n 无关 |
| O(log n) | 对数 | 二分查找 |
| O(n) | 线性 | 遍历一遍 |
| O(n log n) | 线性对数 | 优秀通用排序下界 |
| O(n²) | 平方 | 双重循环朴素排序 |
16.3 算法总览与选型速查
| 算法 | 平均时间 | 最坏时间 | 空间 | 稳定 | 典型场景 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | ✅ | 教学演示；数据极小且几乎有序时可提前结束 |
| 选择排序 | O(n²) | O(n²) | O(1) | ❌ | 交换次数少；内存写入敏感的嵌入式（极少用） |
| 插入排序 | O(n²) | O(n²) | O(1) | ✅ | 小规模（n<50）、基本有序数据；Timsort 子过程 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | ✅ | 链表排序、外部排序（大文件分块归并）、要求稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | ❌ | 通用内存排序平均最快；标准库 C 层 qsort 系 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | ❌ | Top K、优先队列、空间受限且要保证最坏 O(n log n) |
| 计数排序 | O(n+k) | O(n+k) | O(k) | ✅ | 整数且范围 k 不大（如 0～1000 分） |
| 基数排序 | O(d·(n+k)) | 同上 | O(n+k) | ✅ | 定长或短键字符串/整数批量排序 |
工程选型一句话：
- 日常 Python：
sorted()/.sort()（Timsort） - 只要前 K 大：
heapq.nlargest - 已排序列表插入：
bisect - 超大数据在磁盘：多路归并
- 面试手写：快排 / 归并 / 堆排
16.4 冒泡排序（Bubble Sort）
相邻比较，大（或小）的「冒泡」到末尾。
def bubble_sort(arr):
a = arr.copy()
n = len(a)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
swapped = True
if not swapped: # 已有序，提前结束
break
return a
print(bubble_sort([5, 1, 4, 2, 8]))
# [1, 2, 4, 5, 8]| 场景 | 是否选用 |
|---|---|
| 教学、理解「交换」「有序区」 | ✅ |
| 生产环境 | ❌ |
16.5 选择排序（Selection Sort）
每轮在未排序区选最小元素，放到已排序区末尾。
def selection_sort(arr):
a = arr.copy()
n = len(a)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
return a| 特点 | 说明 |
|---|---|
| 交换次数 | 最多 n-1 次，少于冒泡 |
| 稳定性 | 不稳定，相等元素可能交换顺序 |
| 场景 | 写闪存次数敏感时理论上可考虑；实际极少 |
16.6 插入排序（Insertion Sort）
像整理扑克牌：把未排序元素插入已排序区正确位置。
def insertion_sort(arr):
a = arr.copy()
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a| 场景 | 说明 |
|---|---|
| n 很小（<20～50） | 常数因子小，实测可能快于 O(n log n) 算法 |
| 数据基本有序 | 接近 O(n) |
| 在线排序 | 流式来一条插一条 |
| Python Timsort | 小片段用插入排序 |
16.7 归并排序（Merge Sort）
分治：拆半 → 递归排序 → 合并两个有序数组。
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
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))| 场景 | 说明 |
|---|---|
| 需要稳定排序 | ✅ |
| 链表排序 | 归并天然适合，无需随机访问 |
| 外部排序 | 大文件分块排序后多路归并（数据库、日志） |
| 内存紧张又要 O(n log n) 最坏 | 可考虑；但常数与额外空间较大 |
16.8 快速排序（Quick Sort）
选 pivot，分区：小于 pivot 放左，大于放右，递归。
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + mid + quick_sort(right)