算法-排序
一句话概括
排序(Sorting) 是把一组元素按某个全序关系重新排列的过程。它是计算机科学中被研究得最透彻的问题:既有 的理论下界,又有突破下界的非比较排序,还有几十年工程打磨出的混合实现(Timsort)。
本篇覆盖:稳定性与原地性、十种排序的逐一讲解与完整 Python 实现(冒泡 / 选择 / 插入 / 希尔 / 归并 / 快速 / 堆 / 计数 / 基数 / 桶)、总对比表、比较排序下界的决策树证明、Timsort 与工程实践、用排序解决实际问题、各语言标准库 API。
每种排序不仅给代码,还会逐步展示数组状态如何变化,让你看清算法在做什么。
是什么
排序问题的定义
输入:一个序列 和一个定义在全序上的比较关系 (满足自反性、反对称性、传递性、完全性)。
输出:输入的一个重排 。
关键点:排序算法本身不关心元素是什么,它只要求「任意两个元素可以比较大小」。
两个核心概念
稳定性(Stability)
稳定性的定义
若序列中有两个相等元素 (),排序后 仍然排在 前面,则称该排序算法稳定。
若相等元素的相对次序可能被打乱,则称不稳定。
为什么重要? 因为稳定排序可以组合实现多关键字排序:
先按「次要关键字」排一次,再按「主要关键字」稳定地排一次,最终结果就是「先按主要关键字、再按次要关键字」的正确顺序。
# 需求:先按分数降序,分数相同时按年龄升序
students = [("A", 90, 25), ("B", 90, 20), ("C", 85, 30)]
# 做法:先按次要键(年龄)排,再按主要键(分数)稳定排序
students.sort(key=lambda s: s[2]) # 次要关键字:年龄升序
students.sort(key=lambda s: -s[1]) # 主要关键字:分数降序(稳定)
# [('B', 90, 20), ('A', 90, 25), ('C', 85, 30)] ✅
Python 的 sort 是 Timsort,天然稳定,所以这个「两趟排序」技巧可以工作。
原地性(In-place)
原地排序:只使用 或 的额外空间(不含输入本身)。反之叫非原地排序,需要 辅助空间。
- 原地:冒泡、选择、插入、希尔、堆排序
- 非原地:归并排序()、计数/基数/桶排序()
快速排序的「原地」要打引号
快排的 partition 确实只用了 额外空间,但递归栈平均要 、最坏要 。
严格说它是「原地但非 空间」。真正 空间的比较排序只有堆排序。
十种排序一览
| 分类 | 算法 | 一句话原理 |
|---|---|---|
| 交换类 | 冒泡排序 | 相邻两两比较,大的往后冒 |
| 快速排序 | 选基准划分,左右递归 | |
| 选择类 | 选择排序 | 每轮选最小的放到已排序末尾 |
| 堆排序 | 用堆反复取最大值放到末尾 | |
| 插入类 | 插入排序 | 把当前元素插到前面有序部分的正确位置 |
| 希尔排序 | 分组做插入排序,逐步缩小增量 | |
| 分治类 | 归并排序 | 分成两半分别排序再合并 |
| 非比较类 | 计数排序 | 统计每个值出现次数,按值域铺开 |
| 基数排序 | 按位从低到高逐位稳定排序 | |
| 桶排序 | 按值域分桶,桶内单独排序 |
为什么需要它
排序是其他算法的前置条件
| 依赖排序的算法/场景 | 为什么需要有序 |
|---|---|
| 二分查找 | 只有有序才能每次砍一半, → |
| 双指针去重 / 两数之和 | 有序后可以用左右指针 完成 |
| 贪心算法(区间调度、霍夫曼编码) | 必须按某个键从小到大依次决策 |
| 并查集 + Kruskal 求最小生成树 | 必须按边权排序后贪心 |
数据库 ORDER BY / GROUP BY | 排序后相邻元素才可归并 |
| 归并连接(Merge Join) | 两个有序表可以线性归并,避免嵌套循环 |
排序是算法分析的样板
排序几乎包含了所有重要的算法思想:
| 思想 | 代表排序 |
|---|---|
| 暴力枚举 | 冒泡、选择 |
| 增量构造 | 插入排序 |
| 分治(Divide and Conquer) | 归并、快速 |
| 数据结构驱动 | 堆排序 |
| 空间换时间 | 计数、基数、桶排序 |
| 随机化 | 随机化快排 |
| 混合优化 | Timsort |
排序无处不在
- 数据库 90% 以上的慢查询与排序有关(缺索引导致 filesort)
- 前端表格、地图 POI 列表、搜索结果排序
git log的拓扑排序、编译器优化中的活跃变量排序
核心内容
一、冒泡排序(Bubble Sort)
思想:反复扫描数组,比较相邻两个元素,若逆序就交换。每一轮结束后,最大的元素「冒」到末尾。
状态变化示例:[5, 1, 4, 2, 8]
| 轮次 | 过程 | 数组 |
|---|---|---|
| 初始 | — | [5,1,4,2,8] |
| 第 1 轮 | 5>1 换;5>4 换;5>2 换;5<8 不换 | [1,4,2,5,8] |
| 第 2 轮 | 1<4;4>2 换;4<5 | [1,2,4,5,8] |
| 第 3 轮 | 无交换(已有序)→ 提前退出 | [1,2,4,5,8] |
优化:若某一轮没有发生任何交换,说明已经有序,可以立即退出——这使最好情况降到 。
def bubble_sort(arr):
"""冒泡排序(原地、稳定)。
时间:最好 O(n)(已有序,靠 swapped 提前退出),最坏/平均 O(n^2)
空间:O(1)
"""
a = arr[:] # 不修改调用者的列表
n = len(a)
for i in range(n - 1):
swapped = False
# 每轮结束后末尾 i+1 个元素已就位,内层可少比较 i 次
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
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | |
| 稳定 | 是 |
| 适用场景 | 教学演示;实际几乎不用 |
二、选择排序(Selection Sort)
思想:每轮从未排序区间中选出最小的元素,与未排序区间的第一个元素交换。
状态变化示例:[5, 1, 4, 2, 8]
| 轮次 | 未排序区间 | 最小值 | 操作 | 数组 |
|---|---|---|---|---|
| 1 | [5,1,4,2,8] | 1(下标 1) | 与下标 0 交换 | [1,5,4,2,8] |
| 2 | [5,4,2,8] | 2(下标 3) | 与下标 1 交换 | [1,2,4,5,8] |
| 3 | [4,5,8] | 4(下标 2) | 自己换自己 | [1,2,4,5,8] |
| 4 | [5,8] | 5 | 自己换自己 | [1,2,4,5,8] |
特点:交换次数固定为至多 次,是所有排序中最少的。当「交换」的代价远大于「比较」时(如元素是大型结构体)有优势。
选择排序不稳定
例:
[5a, 5b, 2]。第 1 轮把 2 与 5a 交换,得到[2, 5b, 5a]——两个 5 的相对次序被打乱了。
def selection_sort(arr):
"""选择排序(原地、不稳定)。
时间:无论输入如何都是 O(n^2)(比较次数固定为 n(n-1)/2)
空间:O(1)
优点:交换次数最少(<= n-1 次)
"""
a = arr[:]
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
if min_idx != i: # 省掉一次自交换
a[i], a[min_idx] = a[min_idx], a[i]
return a
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | |
| 稳定 | 否 |
| 适用场景 | 交换代价高、 很小的场景 |
三、插入排序(Insertion Sort)
思想:把数组看成「已排序前缀 + 未排序后缀」。每次取后缀的第一个元素,在已排序前缀中从后往前找位置插入。
类比:整理扑克牌——摸一张新牌,从右往左找到位置插进去。
状态变化示例:[5, 1, 4, 2, 8]
| 轮次 | 待插入 | 过程 | 数组 | |
|---|---|---|---|---|
| 初始 | — | 认为 [5] 已排序 | `[5\ | 1,4,2,8]` |
| 1 | 1 | 1<5,5 后移,1 放到位置 0 | `[1,5\ | 4,2,8]` |
| 2 | 4 | 4<5,5 后移;4>1,停在位置 1 | `[1,4,5\ | 2,8]` |
| 3 | 2 | 2<5、2<4 依次后移;2>1,插入位置 1 | `[1,2,4,5\ | 8]` |
| 4 | 8 | 8>5,不需要移动 | `[1,2,4,5,8\ | ]` |
关键性质:对近乎有序的数据极快(内层 while 几乎不执行),最好情况 。这是它在 Timsort 中作为小区间排序器被保留的原因。
def insertion_sort(arr):
"""插入排序(原地、稳定)。
时间:最好 O(n)(已有序),最坏/平均 O(n^2)
空间:O(1)
"""
a = arr[:]
for i in range(1, len(a)):
key = a[i] # 待插入的元素,先存起来(否则会被覆盖)
j = i - 1
# 从右往左找位置:比 key 大的元素统统右移一格
while j >= 0 and a[j] > key: # 严格大于才右移 -> 相等元素不跨越 -> 稳定
a[j + 1] = a[j]
j -= 1
a[j + 1] = key # 空出来的位置放 key
return a
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | |
| 稳定 | 是 |
| 适用场景 | 小数组()的首选、近乎有序的数据、在线排序(边接收边排) |
插入排序的隐藏优势:在线算法
插入排序可以在数据边到达边排序(online),不需要看到全部数据。冒泡和选择都做不到。
这个性质使它在流式场景中不可替代。
四、希尔排序(Shell Sort)
思想:插入排序在「小规模」或「近乎有序」时快。希尔排序先用较大的增量(gap)把数组分成若干子序列分别做插入排序,让元素一次能跨越很远,快速接近有序;再逐步缩小 gap,最后 gap=1 时做一次普通插入排序即可收尾。
关键洞察:插入排序慢是因为元素一次只能移动一格。用 gap 分组后,一个元素一次能移动 gap 格,先把「逆序程度」大幅降低,最后一步的小 gap 插入排序就非常快。
状态变化示例:[8, 5, 3, 9, 1, 7],取 gap 序列 [3, 1]
| 阶段 | gap | 分组(同色为一组) | 组内插入排序后 |
|---|---|---|---|
| 初始 | — | [8,5,3,9,1,7] | [8,5,3,9,1,7] |
| 1 | 3 | (8,9)、(5,1)、(3,7) | [8,1,3,9,5,7] |
| 2 | 1 | 整体一组 | [1,3,5,7,8,9] |
增量序列的选择:没有公认最优解。常见有:
| 增量序列 | 最坏复杂度 | 说明 |
|---|---|---|
| 最简单,Hibbard 之前常用 | ||
| Hibbard: | 常用 | |
| Sedgewick: | 实践中很快 | |
| Knuth: | 《算法》教材推荐 |
def shell_sort(arr, gaps=None):
"""希尔排序(原地、不稳定)。
时间:取决于增量序列,Knuth 序列约 O(n^1.5),最好 O(n log n)
空间:O(1)
不稳定原因:相同元素可能被分到不同组,跨组交换会改变相对次序
"""
a = arr[:]
n = len(a)
if gaps is None:
# Knuth 序列 1, 4, 13, 40, ...,先算到不超过 n 的最大值再递减
gaps, h = [], 1
while h < n:
gaps.append(h)
h = 3 * h + 1
gaps.reverse()
for gap in gaps:
# 对每个以 gap 为间隔的子序列做插入排序
for i in range(gap, n):
key = a[i]
j = i - gap
while j >= 0 and a[j] > key:
a[j + gap] = a[j] # 一次跨越 gap 格,这是提速关键
j -= gap
a[j + gap] = key
return a
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / 取决于增量 / (Knuth 序列) |
| 空间 | |
| 稳定 | 否 |
| 适用场景 | 中等规模()、内存受限、要求原地 |
五、归并排序(Merge Sort)
思想:典型的分治(Divide and Conquer)。
- 分(Divide):把数组从中间切成两半
- 治(Conquer):递归地对两半排序
- 合(Combine):把两个有序子数组合并成一个有序数组(双指针线性归并)
合并过程示例:合并 [1, 5] 与 [2, 4]
| 步骤 | 左指针 | 右指针 | 比较 | 取谁 | 结果 |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 1 < 2 | 左 1 | [1] |
| 2 | 5 | 2 | 5 > 2 | 右 2 | [1,2] |
| 3 | 5 | 4 | 5 > 4 | 右 4 | [1,2,4] |
| 4 | 5 | 越界 | — | 左 5 | [1,2,4,5] |
递推式:
用主定理验证:,,,,属情况 2,故 (详见 算法-复杂度分析)。
关键优势:
- 复杂度稳定:无论什么输入都是 ,没有快排的最坏情况
- 天然稳定:合并时若左右相等,优先取左边的即可
- 适合链表:链表归并只需 额外空间
- 适合外部排序:数据大到内存装不下时,归并可以分块读入
def merge_sort(arr):
"""归并排序(非原地、稳定)。
时间:任何情况都是 O(n log n)
空间:O(n)(合并时的辅助数组)+ O(log n)(递归栈)
递推式:T(n) = 2T(n/2) + O(n) = O(n log n)
"""
a = arr[:]
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid]) # 递归排左半
right = merge_sort(a[mid:]) # 递归排右半
return _merge(left, right)
def _merge(left, right):
"""把两个有序数组合并成一个有序数组。"""
merged = []
i = j = 0
while i < len(left) and j < len(right):
# 用 <= 而不是 <:左右相等时先取左边,从而保持稳定
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
merged.extend(left[i:]) # 收尾:把剩余部分整体接上
merged.extend(right[j:])
return merged
def merge_sort_inplace(arr):
"""归并排序的原地版本(只用一个辅助数组,节省反复分配的开销)。"""
a = arr[:]
aux = [0] * len(a)
def sort(lo, hi):
if hi - lo <= 1:
return
mid = (lo + hi) // 2
sort(lo, mid)
sort(mid, hi)
if a[mid - 1] <= a[mid]:
return # 已天然有序(Timsort 也用了这个优化)
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
aux[k] = a[i]; i += 1
else:
aux[k] = a[j]; j += 1
k += 1
while i < mid:
aux[k] = a[i]; i += 1; k += 1
while j < hi:
aux[k] = a[j]; j += 1; k += 1
a[lo:hi] = aux[lo:hi] # 拷回原数组
sort(0, len(a))
return a
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | |
| 稳定 | 是 |
| 适用场景 | 要求稳定性、数据规模大、链表排序、外部排序 |
六、快速排序(Quick Sort)
思想:选一个基准(pivot),把数组划分成「小于等于基准」和「大于基准」两部分(partition),再递归处理两部分。
为什么它最快? 因为 partition 的访存模式对 CPU 缓存极友好(顺序扫描 + 就地交换),而归并需要额外的 拷贝。同为 ,快排的常数因子小得多。
partition 的两种写法
Lomuto 划分(单指针,易懂)
选定末尾元素作基准,用一个指针 i 维护「小于等于区」的右边界。
示例:[3, 7, 1, 5],pivot = 5(末尾)
| j | a[j] | a[j] <= 5? | 操作 | 数组 |
|---|---|---|---|---|
| 0 | 3 | 是 | i=0→1 | [3,7,1,5] |
| 1 | 7 | 否 | 不动 | [3,7,1,5] |
| 2 | 1 | 是 | 交换 a[1],a[2],i=1→2 | [3,1,7,5] |
| — | — | — | 交换 a[2],a[3](pivot 归位) | [3,1,5,7] |
结果:pivot 5 落在下标 2,左边 [3,1] 都 ,右边 [7] 都 。
Hoare 划分(双指针,交换次数少)
左右两个指针向中间靠拢,左指针找「不小于 pivot」的,右指针找「不大于 pivot」的,交换后继续。
示例:[3, 7, 1, 5],pivot = a[0] = 3
| 步骤 | i | j | 说明 | 数组 |
|---|---|---|---|---|
| 初始 | 0 | 3 | 左找 ≥3,右找 ≤3 | [3,7,1,5] |
| 1 | 0→1 | 3→2 | a[1]=7≥3 停;a[2]=1≤3 停 | — |
| 2 | — | — | 交换 a[1],a[2] | [3,1,7,5] |
| 3 | 1→2 | 2→1 | i=2 与 j=1 交错,结束 | — |
| 4 | — | — | 交换 a[0],a[1](pivot 归位) | [1,3,7,5] |
"""快速排序的多种实现:Lomuto、Hoare、随机化、三路划分。"""
import random
def quicksort_lomuto(arr):
"""快排 + Lomuto 划分(取末尾元素作基准)。原地、不稳定。
时间:平均 O(n log n),最坏 O(n^2)(已排序数组 + 固定基准)
空间:O(log n) 平均递归栈,最坏 O(n)
"""
a = arr[:]
def sort(lo, hi):
if lo >= hi:
return
p = partition_lomuto(a, lo, hi)
sort(lo, p - 1) # 基准已在最终位置,不再参与
sort(p + 1, hi)
sort(0, len(a) - 1)
return a
def partition_lomuto(a, lo, hi):
"""Lomuto 划分:返回基准的最终下标。"""
pivot = a[hi] # 取末尾元素作基准
i = lo # i 指向"小于等于区"的下一个空位
for j in range(lo, hi):
if a[j] <= pivot: # <= 保证与 pivot 相等的元素留在左侧
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i] # 把基准放到分界点
return i
def quicksort_hoare(arr, lo=0, hi=None):
"""快排 + Hoare 划分:交换次数更少,实际更快。原地、不稳定。"""
a = arr[:] if hi is None else arr
if hi is None:
hi = len(a) - 1
if lo >= hi:
return a
p = partition_hoare(a, lo, hi)
quicksort_hoare(a, lo, p) # Hoare 划分返回的是分界,不是基准下标
quicksort_hoare(a, p + 1, hi)
return a
def partition_hoare(a, lo, hi):
"""Hoare 划分:返回右半区的起始下标 j(a[lo..j] <= a[j+1..hi])。"""
pivot = a[(lo + hi) // 2] # 取中间元素作基准,天然抗有序输入
i, j = lo - 1, hi + 1
while True:
i += 1
while a[i] < pivot:
i += 1
j -= 1
while a[j] > pivot:
j -= 1
if i >= j:
return j # 两指针交错,划分完成
a[i], a[j] = a[j], a[i]
def quicksort_random(arr):
"""随机化快排:每轮随机选基准,避免被有序输入或恶意输入打成 O(n^2)。"""
a = arr[:]
def sort(lo, hi):
if lo >= hi:
return
r = random.randint(lo, hi) # 随机挑一个位置与末尾交换,复用 Lomuto
a[r], a[hi] = a[hi], a[r]
p = partition_lomuto(a, lo, hi)
sort(lo, p - 1)
sort(p + 1, hi)
sort(0, len(a) - 1)
return a
def quicksort_3way(arr):
"""三路快排(荷兰国旗问题):把数组分成 <pivot / ==pivot / >pivot 三块。
对"大量重复元素"的输入有巨大优势:重复元素一次全部归位,不再递归。
这就是为什么工程实现(如 Java 的 DualPivotQuicksort)要特判重复值。
"""
a = arr[:]
def sort(lo, hi):
if lo >= hi:
return
pivot = a[random.randint(lo, hi)]
lt, i, gt = lo, lo, hi # [lo,lt) < p, [lt,i) == p, (gt,hi] > p
while i <= gt:
if a[i] < pivot:
a[lt], a[i] = a[i], a[lt]
lt += 1
i += 1
elif a[i] > pivot:
a[i], a[gt] = a[gt], a[i]
gt -= 1 # 换过来的元素还没检查,i 不动
else:
i += 1
sort(lo, lt - 1) # 相等区 [lt, gt] 已完成,跳过
sort(gt + 1, hi)
sort(0, len(a) - 1)
return a
基准选择策略
| 策略 | 说明 | 效果 |
|---|---|---|
| 固定取首/尾 | 实现最简单 | 有序输入退化 ,不可用于生产 |
| 随机取 | 每轮 random 选一个 | 期望 ,抗恶意输入 |
| 三数取中 | 取首、中、尾的中位数 | 抗有序输入,无随机开销 |
| 中位数的中位数(BFPRT) | 严格 选出中位数 | 保证最坏 ,但常数大,实践不用 |
| 三路划分 | 额外处理「等于基准」 | 大量重复元素时从 降到 |
快排最坏情况与随机化的作用
若每次划分都分成 与 :。
随机化后,划分结果成为随机变量,任何固定输入都无法保证每次都划分不均,
期望复杂度为 ,退化概率随 指数级下降。
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | 平均 / 最坏(递归栈) |
| 稳定 | 否(划分时远距离交换会打乱相等元素) |
| 适用场景 | 通用内存排序的默认选择,尤其大数组 |
七、堆排序(Heap Sort)
思想:把数组看成一棵完全二叉树(下标 的孩子是 与 )。先建大顶堆(父节点 子节点),然后反复把堆顶(最大值)与末尾交换,堆大小减一,再下沉修复堆。
堆的两个核心操作:
- 下沉(sift down / heapify):节点与较大的孩子交换,直到满足堆性质。
- 建堆(build heap):从最后一个非叶节点开始依次下沉。虽然单次是 ,但整体只需 (因为大部分节点都在底层,下沉距离很短)
状态变化示例:[4, 10, 3, 5, 1]
| 阶段 | 操作 | 数组 | |
|---|---|---|---|
| 建堆 | 从下标 1 开始下沉:10>4 换 | [10,5,3,4,1] | |
| 取最大 | 堆顶 10 与末尾 1 交换,堆缩小 | `[1,5,3,4\ | 10]` |
| 修复 | 1 下沉:与 5 换,再与 4 换 | `[5,4,3,1\ | 10]` |
| 取最大 | 5 与 1 交换 | `[1,4,3\ | 5,10]` |
| 修复 | 1 与 4 换 | `[4,1,3\ | 5,10]` |
| 取最大 | 4 与 3 交换 | `[3,1\ | 4,5,10]` |
| 修复 | 3 不需要下沉 | `[3,1\ | 4,5,10]` |
| 取最大 | 3 与 1 交换 | `[1\ | 3,4,5,10]` |
| 完成 | — | [1,3,4,5,10] |
def heap_sort(arr):
"""堆排序(原地、不稳定)。
时间:任何情况都是 O(n log n) —— 这是它相对快排的最大优势
空间:O(1) —— 所有比较排序里空间最优,不需要递归栈
"""
a = arr[:]
n = len(a)
def sift_down(i, size):
"""把下标 i 的节点下沉到合适位置,维持大顶堆性质。"""
while True:
largest = i
l, r = 2 * i + 1, 2 * i + 2
if l < size and a[l] > a[largest]:
largest = l
if r < size and a[r] > a[largest]:
largest = r
if largest == i: # 已满足堆性质,停止
return
a[i], a[largest] = a[largest], a[i]
i = largest # 继续往下检查
# 第 1 步:建堆。从最后一个非叶节点 n//2 - 1 逆序下沉,整体 O(n)
for i in range(n // 2 - 1, -1, -1):
sift_down(i, n)
# 第 2 步:反复取堆顶(当前最大值)放到末尾,堆区间逐步缩小
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0] # 最大值归位
sift_down(0, end) # 修复剩余部分的堆性质
return a
def heap_sort_with_local_heap(arr, k):
"""堆排序的实用变体:求前 k 大(用大小为 k 的小顶堆),复杂度 O(n log k)。
这是一个非常高频的面试题:n=10^7、k=10 时,比完整排序快几个数量级。
"""
import heapq
a = arr[:]
if k <= 0:
return []
heap = a[:k] # 先放前 k 个
heapq.heapify(heap) # 小顶堆:堆顶是这 k 个里最小的
for x in a[k:]:
if x > heap[0]: # 比当前门槛大才可能进前 k
heapq.heapreplace(heap, x)
return sorted(heap, reverse=True)
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | |
| 稳定 | 否 |
| 适用场景 | 需要保证最坏 且空间受限(嵌入式、实时系统);Top-K 问题 |
八、计数排序(Counting Sort)
思想:如果元素是小范围整数,可以直接统计每个值出现了几次,然后按值从小到大铺开——完全不需要比较。
步骤:
- 找出最大值
max_val与最小值min_val - 开一个大小为
max_val - min_val + 1的计数数组 - 遍历输入,
count[a[i] - min_val] += 1 - 按值从小到大,把
count[v]个v + min_val依次写回
状态变化示例:[4, 1, 4, 2, 1, 4]()
| 步骤 | 计数数组(下标 1..4) |
|---|---|
| 统计完成 | [2, 1, 0, 3](1 出现 2 次、2 出现 1 次、4 出现 3 次) |
| 按值铺开 | [1,1,2,4,4,4] |
稳定性:上面的朴素写法不稳定。要稳定,需要改成前缀和 + 从右往左回填(这是基数排序能用它的前提):
def counting_sort(arr):
"""计数排序(非原地、稳定)。
时间:O(n + k),k 为值域大小
空间:O(n + k)
限制:只适用于整数(或可映射为紧凑整数)的数据
"""
if not arr:
return []
lo, hi = min(arr), max(arr)
k = hi - lo + 1
count = [0] * k
for x in arr: # 第 1 遍:统计频次
count[x - lo] += 1
# 前缀和:count[i] 变成"值 <= i + lo 的元素个数"
for i in range(1, k):
count[i] += count[i - 1]
out = [0] * len(arr)
# 从右往左回填,这样相等元素中后出现的排在后 -> 稳定
for x in reversed(arr):
count[x - lo] -= 1
out[count[x - lo]] = x
return out
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | |
| 稳定 | 是(用前缀和 + 逆序回填的实现) |
| 适用场景 | 值域小的整数,如年龄(0-150)、分数(0-100)、字符(0-255) |
计数排序不适合值域大的数据
若数据是
[1, 10^9]中的两个数,,光开计数数组就要几 GB 内存。这时应该用基数排序或普通比较排序。
九、基数排序(Radix Sort)
思想:把整数按位(digit)拆开,从最低位到最高位(LSD)依次用稳定排序(通常是计数排序)排一遍。因为每轮都是稳定的,高位排序不会破坏低位已建立的次序。
为什么必须稳定? 举例:[13, 21, 12]
| 轮次 | 排序键 | 结果 |
|---|---|---|
| 第 1 轮 | 个位 | [21, 12, 13](个位 1,2,3) |
| 第 2 轮 | 十位 | [12, 13, 21] ✅ |
第 2 轮按十位排时,21 的十位是 2,12 和 13 的十位都是 1。若十位相同时不保持第 1 轮的相对次序(12 在 13 前),结果就会错。
复杂度:设最大数有 位,每位的值域为 (十进制 ):
状态变化示例:[170, 45, 75, 90, 802, 24, 2, 66]
| 轮次 | 按个位排 | 按十位排 | 按百位排 |
|---|---|---|---|
| 结果 | [170,90,802,2,24,45,75,66] | [802,2,24,45,66,170,75,90] | [2,24,45,66,75,90,170,802] |
def radix_sort(arr, base=10):
"""基数排序 LSD(非原地、稳定)。
时间:O(d * (n + base)),d 为最大数的位数
空间:O(n + base)
限制:元素必须是非负整数(负数可先分离再翻转)
"""
if not arr:
return []
a = arr[:]
max_val = max(a)
exp = 1 # 当前处理的位:1=个位,10=十位,...
while max_val // exp > 0:
a = _counting_sort_by_digit(a, exp, base)
exp *= base
return a
def _counting_sort_by_digit(a, exp, base):
"""按 (x // exp) % base 这一位做稳定计数排序。"""
count = [0] * base
for x in a:
count[(x // exp) % base] += 1
for i in range(1, base):
count[i] += count[i - 1] # 前缀和 -> 定位置
out = [0] * len(a)
for x in reversed(a): # 逆序回填 = 稳定
d = (x // exp) % base
count[d] -= 1
out[count[d]] = x
return out
def radix_sort_with_negatives(arr, base=10):
"""支持负数的基数排序:负数取绝对值排好序后翻转再拼接。"""
neg = [-x for x in arr if x < 0]
pos = [x for x in arr if x >= 0]
return [-x for x in reversed(radix_sort(neg, base))] + radix_sort(pos, base)
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / 同 / 同 |
| 空间 | |
| 稳定 | 是 |
| 适用场景 | 位数少的大量整数(如手机号、身份证、IP 地址);字符串排序(按字符位) |
十、桶排序(Bucket Sort)
思想:把值域均匀划分成若干个桶,每个元素按值放进对应桶;桶内单独排序(常用插入排序);最后按桶顺序拼接。
前提:输入数据大致均匀分布。否则所有元素挤进一个桶,退化成对 个元素做插入排序,。
状态变化示例:[0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68],分 10 个桶
| 桶号 | 元素 | 桶内排序后 |
|---|---|---|
| 1 | [0.17, 0.12] | [0.12, 0.17] |
| 2 | [0.26, 0.21, 0.23] | [0.21, 0.23, 0.26] |
| 3 | [0.39] | [0.39] |
| 6 | [0.68] | [0.68] |
| 7 | [0.78, 0.72] | [0.72, 0.78] |
| 9 | [0.94] | [0.94] |
拼接结果:[0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94]
def bucket_sort(arr, bucket_count=None):
"""桶排序(非原地、稳定取决于桶内排序)。
时间:平均 O(n + k)(均匀分布),最坏 O(n^2)(全部落进同一个桶)
空间:O(n + k)
"""
if not arr:
return []
n = len(arr)
if bucket_count is None:
bucket_count = n
lo, hi = min(arr), max(arr)
if hi == lo: # 所有元素相同,直接返回
return arr[:]
span = (hi - lo) / bucket_count
buckets = [[] for _ in range(bucket_count)]
for x in arr:
# 计算桶号;用 min 防止 x == hi 时下标越界
idx = min(int((x - lo) / span), bucket_count - 1)
buckets[idx].append(x)
out = []
for b in buckets:
out.extend(insertion_sort(b)) # 桶内用插入排序(小数组最快)
return out
| 维度 | 值 |
|---|---|
| 最好 / 平均 / 最坏 | / / |
| 空间 | |
| 稳定 | 取决于桶内排序(用插入排序则稳定) |
| 适用场景 | 数据均匀分布的浮点数(如 0-1 之间的随机数) |
总对比表
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定 | 原地 | 适用场景 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | ✅ | ✅ | 教学演示 | ||||
| 选择排序 | ❌ | ✅ | 交换代价高、 极小 | ||||
| 插入排序 | ✅ | ✅ | 小数组()、近乎有序、在线 | ||||
| 希尔排序 | 依赖增量 | ❌ | ✅ | 中等规模、内存受限 | |||
| 归并排序 | ✅ | ❌ | 要求稳定、链表、外部排序 | ||||
| 快速排序 | ❌ | ✅ | 通用内存排序的默认选择 | ||||
| 堆排序 | ❌ | ✅ | 需保证最坏性能、空间受限、Top-K | ||||
| 计数排序 | ✅ | ❌ | 值域小的整数 | ||||
| 基数排序 | ✅ | ❌ | 位数少的大量整数/字符串 | ||||
| 桶排序 | ✅ | ❌ | 均匀分布的浮点数 |
一张表记住怎么选
- 通用默认 → 快速排序(或直接用标准库的 Timsort / introsort)
- 要稳定 → 归并排序 / Timsort
- 空间极紧 → 堆排序
- 要保证最坏 → 堆排序 / 归并排序
- 小数组() → 插入排序
- 值域小的整数 → 计数排序
- Top-K → 大小为 的堆,
比较类排序的下界:
定理
任何只依赖元素两两比较的排序算法,最坏情况下至少需要 次比较。
决策树证明思路:
第 1 步:把算法建模成一棵决策树。
算法的每一次「比较 与 」是一个内部节点,有两个分支( 和 )。到达叶子时算法必须已经确定整个排列。
第 2 步:数叶子数。
个元素有 种可能的初始排列,每种都必须被引导到不同的叶子(否则算法会对两种不同输入给出同一个输出,必然有一个是错的)。所以决策树至少要有 个叶子。
第 3 步:二叉树高度与叶子数的关系。
高度为 的二叉树最多有 个叶子,因此
第 4 步:用 Stirling 公式估计 。
(更精确地用 Stirling 公式:。)
第 5 步:结论。 决策树高度 就是该算法的最坏比较次数,所以
这解释了为什么归并排序和堆排序是「最优」的比较排序——它们达到了这个下界。
下界只针对「比较类」排序
下界依赖「只能通过比较获取信息」这个前提。计数/基数/桶排序通过直接访问元素的值(数组下标索引)绕过了比较,
因此可以突破 。它们被称为非比较排序。
非比较排序的适用条件
| 条件 | 说明 | 反例 |
|---|---|---|
| 元素可映射为有限的整数键 | 计数/基数需要按下标索引 | 任意精度实数、复杂对象 |
| 值域 与 同阶 | 才有意义 | 但值域 |
| 基数排序需要位可分解 | 整数、定长字符串 | 变长字符串(需先补齐) |
| 桶排序需要分布均匀 | 否则退化 | 幂律分布的数据 |
| 需要额外空间 | 内存受限时不行 | 嵌入式环境 |
Timsort 与工程实践
为什么标准库不用「纯快排」或「纯归并」
Python 的
list.sort()、Java 对象排序、Android 都使用 Timsort(Tim Peters 于 2002 年为 Python 设计)。它是归并 + 插入的混合算法,核心洞察是:真实数据往往已经部分有序。
Timsort 的四个关键机制:
| 机制 | 作用 |
|---|---|
| run(自然有序段)检测 | 扫描出已经升序(或严格降序,就地反转)的连续片段,长度记作 run |
| minrun 扩展 | 若 run 长度 (32~64),用插入排序把它补到 minrun 长 |
| 归并栈 | 把 run 压栈,按不变式(类似斐波那契)合并相邻 run,保证 |
| galloping(飞奔模式) | 合并时若一方连续多次胜出,改用二分跳转代替逐个比较,处理部分有序数据极快 |
复杂度:
| 情况 | 复杂度 | 说明 |
|---|---|---|
| 最好 | 数据已完全有序,只有一个 run | |
| 平均 / 最坏 | 有严格证明 | |
| 空间 | 归并需要临时缓冲 | |
| 稳定性 | 稳定 | 这是标准库选择它的重要原因 |
其他语言的工程选择:
| 语言 | 算法 | 原因 |
|---|---|---|
Python(list.sort) | Timsort | 稳定 + 对真实数据快 |
| Java(对象数组) | Timsort | 稳定是规范要求 |
| Java(基本类型数组) | Dual-Pivot Quicksort | 基本类型不需要稳定性,快排更快 |
C++(std::sort) | Introsort(快排 + 堆排 + 插入) | 快排为主,深度超限切堆排保证 |
C++(std::stable_sort) | Timsort 类归并 | 显式要求稳定 |
C#(Array.Sort) | Introsort | 不稳定;OrderBy 用稳定归并 |
Go(slices.Sort) | pdqsort(模式破除快排) | 抗恶意输入 |
工程启示
生产级排序都是混合算法:
① 小区间用插入排序(减少递归开销);
② 主体用快排或归并(保证 );
③ 加随机化或 introsort 的深度限制(防止最坏情况);
④ 针对重复值做三路划分;
⑤ 特殊检测已有序段(利用真实数据的局部性)。
单纯实现「教科书快排」在生产环境是不够的。
用排序解决实际问题
应用 1:合并区间(LeetCode 56)
思路:按区间起点排序后,能合并的区间一定相邻。
def merge_intervals(intervals):
"""合并所有重叠区间。时间 O(n log n)(瓶颈在排序),空间 O(n)。"""
if not intervals:
return []
# 按起点升序排序:排序后重叠区间必然相邻,一趟扫描即可
intervals = sorted(intervals, key=lambda x: x[0])
merged = [list(intervals[0])]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # 与上一个区间重叠或相接
merged[-1][1] = max(merged[-1][1], end) # 只扩展右端点
else:
merged.append([start, end]) # 不重叠,开启新区间
return [tuple(x) for x in merged]
if __name__ == "__main__":
print(merge_intervals([(1, 3), (2, 6), (8, 10), (15, 18)]))
# [(1, 6), (8, 10), (15, 18)]
应用 2:自定义排序与比较器
"""自定义排序的三种写法(Python 生态里 key 优先,cmp_to_key 是兜底)。"""
from functools import cmp_to_key
def sort_by_key():
"""① key 函数:最推荐,O(n log n) 且每次比较不重复计算键。"""
words = ["banana", "apple", "cherry", "date"]
# 先按长度升序,长度相同按字典序
return sorted(words, key=lambda w: (len(w), w))
# ['date', 'apple', 'banana', 'cherry']
def sort_numeric_string():
"""② 混合类型排序:把数字字符串按数值排(否则 '10' < '9')。"""
nums = ["10", "9", "100", "1"]
return sorted(nums, key=int) # ['1', '9', '10', '100']
def sort_with_cmp():
"""③ cmp 比较器:只在 key 表达不出来时用(Python 3 需 cmp_to_key 包装)。"""
def cmp(a, b):
# 规则:先比长度,短的在前;长度相同按字典序倒序
if len(a) != len(b):
return -1 if len(a) < len(b) else 1
if a == b:
return 0
return -1 if a > b else 1
words = ["bb", "a", "cc", "dd"]
return sorted(words, key=cmp_to_key(cmp))
def multi_key_mixed_order():
"""④ 多关键字、方向不同:用元组 + 负号(数值)或分两趟稳定排序(字符串)。"""
students = [("Alice", 90, 25), ("Bob", 90, 20), ("Cara", 85, 30)]
# 分数降序、年龄升序:数值可以直接取负
by_num = sorted(students, key=lambda s: (-s[1], s[2]))
# 字符串无法取负:先按次要键排,再按主要键稳定排序
by_str = sorted(students, key=lambda s: s[2])
by_str.sort(key=lambda s: s[0], reverse=True) # Timsort 稳定,保住上一步顺序
return by_num, by_str
if __name__ == "__main__":
print(sort_by_key())
print(sort_numeric_string())
print(sort_with_cmp())
print(multi_key_mixed_order()[0])
应用 3:多关键字排序(基数思想)
def sort_records(records):
"""按 (优先级降序, 时间升序, 名称升序) 三关键字排序。
如果 key 元组能表达(数值可取负),直接用 key 最清晰;
如果某些键的方向无法用取负表达(如字符串降序),用"逐趟稳定排序"。
"""
# 趟 1:最次要的关键字
records = sorted(records, key=lambda r: r["name"])
# 趟 2:次关键字(时间升序)
records = sorted(records, key=lambda r: r["time"])
# 趟 3:最主要的关键字(优先级降序,必须用稳定排序保住前两趟结果)
records = sorted(records, key=lambda r: r["priority"], reverse=True)
return records
if __name__ == "__main__":
data = [
{"name": "b", "time": 2, "priority": 1},
{"name": "a", "time": 1, "priority": 2},
{"name": "c", "time": 1, "priority": 1},
]
for r in sort_records(data):
print(r)
# priority=2 的 a 最先;priority=1 里 time=1 的 c 在 time=2 的 b 之前
应用 4:Top-K 与前 K 个高频元素
import heapq
from collections import Counter
def top_k_frequent(nums, k):
"""返回出现频率最高的 k 个元素。时间 O(n log k),优于完整排序的 O(n log n)。"""
freq = Counter(nums) # 第 1 步:计数 O(n)
# 第 2 步:维护大小为 k 的小顶堆,堆顶是"当前第 k 名"
return [x for x, _ in heapq.nlargest(k, freq.items(), key=lambda kv: kv[1])]
def kth_largest(nums, k):
"""第 k 大的元素:用快速选择(Quickselect),平均 O(n)。
思路与快排一致,但每次只递归包含目标的那一半,因此
T(n) = T(n/2) + O(n) = O(n)(几何级数收敛)。
"""
import random
a = nums[:]
lo, hi = 0, len(a) - 1
target = len(a) - k # 第 k 大 = 升序的第 len-k 个
while True:
r = random.randint(lo, hi)
a[r], a[hi] = a[hi], a[r]
p = partition_lomuto_local(a, lo, hi)
if p == target:
return a[p]
if p < target:
lo = p + 1 # 目标在右半,丢弃左半
else:
hi = p - 1
def partition_lomuto_local(a, lo, hi):
pivot = a[hi]
i = lo
for j in range(lo, hi):
if a[j] <= pivot:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
return i
if __name__ == "__main__":
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) # [1, 2]
print(kth_largest([3, 2, 1, 5, 6, 4], 2)) # 5
应用 5:数逆序对(归并排序的副产品)
def count_inversions(arr):
"""统计逆序对数量(i < j 但 a[i] > a[j]),用归并排序,O(n log n)。
为什么归并能数逆序对?合并左右两个有序数组时,
每当从右半取一个元素,就说明它比左半剩下的所有元素都小
-> 一次性贡献 len(left) - i 个逆序对。
"""
a = arr[:]
aux = [0] * len(a)
def sort(lo, hi):
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
cnt = sort(lo, mid) + sort(mid, hi)
i, j, k = lo, mid, lo
while i < mid and j < hi:
if a[i] <= a[j]:
aux[k] = a[i]; i += 1
else:
aux[k] = a[j]; j += 1
cnt += mid - i # 关键:左半剩余元素都与 a[j] 构成逆序
k += 1
while i < mid:
aux[k] = a[i]; i += 1; k += 1
while j < hi:
aux[k] = a[j]; j += 1; k += 1
a[lo:hi] = aux[lo:hi]
return cnt
return sort(0, len(a))
if __name__ == "__main__":
print(count_inversions([2, 4, 1, 3, 5])) # 3: (2,1),(4,1),(4,3)
各语言标准库排序 API
Python
data = [3, 1, 2]
data.sort() # 原地排序(Timsort,稳定),返回 None
new = sorted(data, reverse=True) # 返回新列表
out = sorted(data, key=lambda x: -x) # key 函数(推荐)
out = sorted(words, key=str.lower) # 忽略大小写
out = sorted(rows, key=lambda r: (r[0], -r[1])) # 多关键字
# 注意事项
# 1) list.sort() 返回 None,不是列表!写 x = data.sort() 会得到 None
# 2) key 只对每个元素计算一次(Schwartzian transform),比 cmp 快得多
# 3) sorted 是稳定排序,可安全用于"多趟排序"技巧
# 4) heapq.nlargest/nsmallest 在有 k << n 时优于完整排序
JavaScript
const data = [3, 1, 2];
data.sort(); // ⚠️ 默认按 UTF-16 字符串排序!
[10, 9, 1].sort(); // [1, 10, 9] ← 不是数值序
data.sort((a, b) => a - b); // 数值升序(必须给比较器)
data.sort((a, b) => b - a); // 数值降序
rows.sort((a, b) => a.age - b.age || a.name.localeCompare(b.name));
// ES2019 起保证稳定(V8 用 Timsort)
// 注意:sort 原地修改数组,需要副本用 [...data].sort(...)
// Array.prototype.toSorted()(ES2023)返回新数组
Java
int[] a = {3, 1, 2};
Arrays.sort(a); // 基本类型:双轴快排,不稳定
Integer[] b = {3, 1, 2};
Arrays.sort(b, Comparator.reverseOrder()); // 对象:Timsort,稳定
List<Person> people = ...;
people.sort(Comparator.comparingInt(Person::getAge) // 主键
.thenComparing(Person::getName)); // 次键
// 注意:Arrays.sort(int[]) 是不稳定的,需要稳定性时先装箱成 Integer[]
C#
int[] a = { 3, 1, 2 };
Array.Sort(a); // Introsort,不稳定
Array.Sort(a, (x, y) => y.CompareTo(x)); // 降序
var sorted = people.OrderBy(p => p.Age) // OrderBy 稳定(LINQ)
.ThenByDescending(p => p.Name)
.ToList();
C++
#include <algorithm>
std::vector<int> v{3, 1, 2};
std::sort(v.begin(), v.end()); // Introsort,不稳定,O(n log n)
std::stable_sort(v.begin(), v.end()); // 稳定归并
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // 降序
// 注意:比较器必须满足严格弱序(strict weak ordering),
// 写成 <= 会导致未定义行为与段错误!必须用 <
各语言 API 的三大坑
① JS 默认字典序:
[10,9,1].sort()得到[1,10,9],必须传比较器。② C++ 比较器必须是严格弱序:用
<=而不是<会让std::sort越界崩溃。③ Python
sort()返回 None:x = lst.sort()是新手最常见的 bug 之一。
怎么用
选择排序算法的决策流程
数据是什么类型?
├── 整数且值域小(如 0-1000)
│ └── 计数排序 O(n+k)
├── 整数且位数少(如手机号、ID)
│ └── 基数排序 O(d(n+k))
├── 浮点数且分布均匀(如 0-1 之间)
│ └── 桶排序 O(n+k)
└── 一般可比较对象
├── 需要稳定?
│ ├── 是 → 归并排序 / Timsort O(n log n)
│ └── 否 → 快速排序 O(n log n) 平均
├── 需要保证最坏 O(n log n)?
│ └── 堆排序(且 O(1) 空间)
└── n 很小(<= 16)?
└── 插入排序
用实验验证复杂度
"""实测各排序算法的耗时,验证理论复杂度。"""
import random
import time
ALGOS = {
"bubble": bubble_sort,
"selection": selection_sort,
"insertion": insertion_sort,
"shell": shell_sort,
"merge": merge_sort,
"quick(random)": quicksort_random,
"heap": heap_sort,
"counting": counting_sort,
"radix": radix_sort,
"bucket": bucket_sort,
}
def bench(sizes=(200, 400, 800), repeat=3):
"""对每个规模、每个算法测最快一次耗时。"""
print(f"{'算法':16s}" + "".join(f"{'n=' + str(s):>12s}" for s in sizes))
for name, fn in ALGOS.items():
row = f"{name:16s}"
for s in sizes:
data = [random.randint(0, 10_000) for _ in range(s)]
best = float("inf")
for _ in range(repeat):
t0 = time.perf_counter()
out = fn(data)
best = min(best, time.perf_counter() - t0)
# 顺便验证正确性
assert out == sorted(data), f"{name} 在 n={s} 时结果错误"
row += f"{best*1000:11.2f}ms"
print(row)
# 观察:n 翻倍时,O(n^2) 类的耗时约 4 倍,O(n log n) 类约 2.2 倍
def bench_worst_case(n=1500):
"""最坏情况对比:已排序输入对固定基准快排是致命的。"""
data = list(range(n))
for name, fn in (("quick(random)", quicksort_random), ("merge", merge_sort), ("heap", heap_sort)):
t0 = time.perf_counter()
fn(data)
print(f"{name:16s} 已排序 n={n}: {time.perf_counter()-t0:.4f}s")
if __name__ == "__main__":
bench()
bench_worst_case()
实测的注意事项
① 用
time.perf_counter()而不是time.time()(后者精度低且受系统时钟调整影响);② 多次运行取最小值(减少 GC 与系统调度噪声);
③ 一定要在计时外验证结果正确性,否则可能测的是「快速但错误」的算法;
④ 数据用随机生成,并单独测一次「已排序输入」——很多排序的最坏情况就藏在这里。
注意事项与常见坑
坑 1:Python
list.sort()返回 None```python
a = [3, 1, 2]
b = a.sort() # ❌ b 是 None!sort 是原地操作
c = sorted(a) # ✅ 返回新列表
```
这是 Python 新手最高频的错误之一。
坑 2:
sort的 key 在排序期间被修改如果 key 函数依赖可变状态,或者排序过程中修改了列表长度,会导致
ValueError: list modified during sort。key 函数必须是纯函数。
坑 3:混淆「稳定」与「有序」
稳定性说的是相等元素的相对次序,与元素本身是否有序无关。
只有「排序键相同但需要保留原顺序的其他字段」时,稳定性才有意义。
坑 4:快排固定取首元素作基准
在生产代码中直接写
pivot = a[lo]是危险的:用户输入常常已经有序(如按时间导出的日志),这会精确命中 最坏情况。必须随机化或三数取中。
坑 5:计数排序忘记处理负数和偏移
数组下标不能为负。必须先求
min,用x - min作为下标,回填时再加回min。若直接开
max + 1大小的数组,负数会索引到列表末尾,静默出错。
坑 6:基数排序用了不稳定的一趟
若某一位的排序不稳定,之前低位建立好的次序就会被破坏,结果完全错误。
这就是为什么基数排序内部必须用计数排序这种稳定排序,而不能用快排。
坑 7:桶排序桶数设置不当
桶数太少 → 桶内元素太多,退化成 插入排序;
桶数太多 → 大量空桶,遍历开销与内存浪费。
经验值:桶数 ,且必须假设数据分布近似均匀。
坑 8:用比较排序给自定义对象排序却忘了实现比较
Python 中若对象没有
__lt__,sorted()会抛TypeError: '<' not supported between instances of ...。解决:用
key=提取可比较字段(推荐),或functools.total_ordering/dataclass(order=True)。
坑 9:认为「快排总是最快的」
在 大量重复元素 的数据上,两路快排会把等于基准的元素分到同一侧,反复递归同一批相等元素,
退化为 (如全 0 数组)。必须用三路划分或随机化 + 双轴。
实测:100 万个相同元素,两路快排在部分实现下需要数十秒,三路快排 0.2 秒。
坑 10:大数组用递归实现导致栈溢出
归并排序和快排的递归深度是 (平均),但快排最坏是 。
的已排序输入会让朴素快排递归 层,直接
RecursionError。缓解:随机化基准 + 优先递归较小的一半(保证栈深 )。
练习题
题 1(基础)判断稳定性
以下数组序列分别用冒泡、选择、插入、归并、快速、堆排序,判断结果是否稳定。请用 [(2,'a'), (1,'x'), (2,'b'), (1,'y')] 手工推演选择排序与归并排序。
<details>
<summary>参考答案</summary>
稳定:冒泡、插入、归并、计数、基数、桶(桶内插入排序)。
不稳定:选择、希尔、快速、堆。
选择排序推演 [(2,a), (1,x), (2,b), (1,y)]:
| 轮次 | 最小值下标 | 交换 | 数组 |
|---|---|---|---|
| 1 | 1(值 1,'x') | 与下标 0 交换 | [(1,x), (2,a), (2,b), (1,y)] |
| 2 | 3(值 1,'y') | 与下标 1 交换 | [(1,x), (1,y), (2,b), (2,a)] |
结果中 (2,b) 跑到了 (2,a) 前面 → 不稳定。
归并排序推演:
- 分成
[(2,a),(1,x)]与[(2,b),(1,y)] - 左半归并:
1 < 2取(1,x);再取(2,a)→[(1,x),(2,a)] - 右半归并:同理得
[(1,y),(2,b)] - 总归并:比较
(1,x)与(1,y),相等取左 →(1,x);再取(1,y);然后比较(2,a)与(2,b),相等取左 →(2,a),再(2,b) - 结果
[(1,x),(1,y),(2,a),(2,b)]→ 所有相等元素保序 → 稳定 ✅
</details>
题 2(基础)手算快排的一轮划分
对 [3, 8, 2, 5, 1, 4, 7, 6] 用 Lomuto 划分(末尾元素 6 作基准),写出每一步的数组状态与 i、j 的值。
<details>
<summary>参考答案</summary>
pivot = a[7] = 6,i = 0。
| j | a[j] | a[j] <= 6? | 操作后数组 | i |
|---|---|---|---|---|
| 0 | 3 | 是 | [3,8,2,5,1,4,7,6](自己换自己) | 1 |
| 1 | 8 | 否 | 不变 | 1 |
| 2 | 2 | 是 | [3,2,8,5,1,4,7,6] | 2 |
| 3 | 5 | 是 | [3,2,5,8,1,4,7,6] | 3 |
| 4 | 1 | 是 | [3,2,5,1,8,4,7,6] | 4 |
| 5 | 4 | 是 | [3,2,5,1,4,8,7,6] | 5 |
| 6 | 7 | 否 | 不变 | 5 |
| — | — | — | 交换 a[5] 与 a[7] | — |
最终 [3,2,5,1,4,6,7,8],基准 6 落在下标 5,左半 [3,2,5,1,4] 全部 ,右半 [7,8] 全部 。✅
</details>
题 3(中等)三路快排处理重复元素
数组 [2, 0, 2, 1, 1, 0](只有 0、1、2 三种值),手工推演三路快排的划分过程。
<details>
<summary>参考答案</summary>
取 pivot 为随机元素,假设取到 1。初始 lt = 0,i = 0,gt = 5。
| 步骤 | i | a[i] | 比较 | 操作 | 数组 | lt | gt |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 2 | > 1 | 换 a[0],a[5],gt=4 | [0,0,2,1,1,2] | 0 | 4 |
| 2 | 0 | 0 | < 1 | 换 a[0],a[0],lt=1,i=1 | [0,0,2,1,1,2] | 1 | 4 |
| 3 | 1 | 0 | < 1 | 换 a[0],a[1],lt=2,i=2 | [0,0,2,1,1,2] | 2 | 4 |
| 4 | 2 | 2 | > 1 | 换 a[2],a[4],gt=3 | [0,0,1,1,2,2] | 2 | 3 |
| 5 | 2 | 1 | == 1 | i=3 | 不变 | 2 | 3 |
| 6 | 3 | 1 | == 1 | i=4 > gt=3 | 循环结束 | 2 | 3 |
划分完成:[0,0] | [1,1] | [2,2]。相等区 [lt, gt] = [2,3] 已就位,不再递归,只需递归 <1 的 [0,1] 和 >1 的空区间。
结论:三路快排在 内处理完这种输入,而两路快排会递归 层。
</details>
题 4(中等)用归并排序统计逆序对
数组 [5, 4, 3, 2, 1] 有多少个逆序对?用归并过程逐步说明。
完整分步解答:
第 1 步:定义与手算。 逆序对是满足 且 的 数量。
对完全逆序的 5 元素数组,任意两个元素都构成逆序对:
第 2 步:递归分解。
[5,4,3,2,1]
/ \
[5,4] [3,2,1]
/ \ / \
[5] [4] [3] [2,1]
/ \
[2] [1]
第 3 步:自底向上归并并计数。
| 归并操作 | 过程 | 新增逆序对 | 累计 |
|---|---|---|---|
[2] + [1] | 2 > 1,取出 1,左半剩 1 个元素 | +1 | 1 |
[3] + [1,2] | 3>1 取 1(+1);3>2 取 2(+1);取 3 | +2 | 3 |
[5] + [4] | 5 > 4,取出 4,左半剩 1 个 | +1 | 4 |
[4,5] + [1,2,3] | 见下表 | +6 | 10 |
最后一轮归并 left=[4,5]、right=[1,2,3] 的详细过程:
| 比较 | 取值 | 左半剩余元素数 | 新增逆序对 |
|---|---|---|---|
| 4 > 1 | 取 1 | 2(是 4、5) | +2 |
| 4 > 2 | 取 2 | 2 | +2 |
| 4 > 3 | 取 3 | 2 | +2 |
| 右半空 | 取 4、5 | — | 0 |
合计 。
第 4 步:验证。
与手算的 一致。
第 5 步:复杂度。 归并排序 ,计数只是在合并时加一行 cnt += mid - i,不增加渐进复杂度。空间 。
代码见上文「应用 5:数逆序对」。
</details>
题 5(进阶)外部排序
内存只有 1 GB,要排序 100 GB 的文件。设计一个方案。
<details>
<summary>参考答案</summary>
核心思路:分块排序 + 多路归并(external merge sort)。
| 阶段 | 步骤 |
|---|---|
| ① 分块 | 把 100 GB 文件顺序读入,每次填满约 800 MB 内存(留余量),用一个 chunk |
| ② 块内排序 | 对每个 chunk 用 Timsort(充分利用内存内的 排序) |
| ③ 写回 | 把排好序的 chunk 写到磁盘,得到约 125 个有序临时文件 |
| ④ 多路归并 | 用大小为 的最小堆同时归并 个文件( 受文件句柄限制,通常 16~64),每轮把 路合并成 1 路,重复 轮 |
| ⑤ 清理 | 删除临时文件 |
复杂度:读文件 2 遍(1 遍读 + 1 遍归并写),I/O 是瓶颈,时间复杂度 ,其中 是数据量、 是内存、 是块大小。
关键细节:
- 块内用稳定排序,多路归并用「相等时优先取编号小的流」也能保持稳定;
- 用置换选择(replacement selection)可以把平均块长从 提高到 ,减少归并轮数;
- 数据库的
ORDER BY在内存不足时正是这么做的(MySQL 的 filesort + merge)。
</details>
题 6(进阶)实现带稳定性保证的 LSD 基数排序
给定一组长度为 3 的字符串(只含小写字母),按字典序排序,不使用比较排序。
<details>
<summary>参考答案</summary>
字符可以直接映射为数字:ord(c) - ord('a'),值域 ,位数 。
必须从最后一位(最低位)开始,即第 3 位 → 第 2 位 → 第 1 位(LSD),每轮用稳定的计数排序。
def radix_sort_fixed_strings(words, length=3, alphabet=26):
"""按字典序排序等长小写字母字符串,O(d * (n + alphabet))。"""
a = words[:]
for pos in range(length - 1, -1, -1): # 从最低位到最高位
count = [0] * alphabet
for w in a:
count[ord(w[pos]) - 97] += 1
for i in range(1, alphabet):
count[i] += count[i - 1]
out = [""] * len(a)
for w in reversed(a): # 逆序回填保证稳定
d = ord(w[pos]) - 97
count[d] -= 1
out[count[d]] = w
a = out
return a
if __name__ == "__main__":
print(radix_sort_fixed_strings(["bca", "abc", "aaa", "baa", "aab"]))
# ['aaa', 'aab', 'abc', 'baa', 'bca']
为什么必须先低位后高位? 因为低位排序会被后续的高位排序覆盖。
LSD 从低位开始,每一轮都是稳定排序,高位相同时低位建立的次序得以保留,最终结果就是完整字典序。
反之(MSD 从高位开始)需要递归分组,实现更复杂,但适合变长字符串与流式场景。
</details>
常见问题 FAQ
Q1:为什么 Python 的
sorted()比我自己写的快排快得多?四个原因:① Timsort 利用数据已有的有序段(真实数据常常部分有序),最好情况 ;
② C 实现 vs Python 字节码,每次比较的开销差几十倍;
③ key 函数只对每个元素计算一次(Schwartzian transform),而手写
cmp_to_key每次比较都要调 Python 函数;④ 深度工程优化(galloping、内存预分配、避免边界检查)。
结论:生产代码永远用标准库排序。
Q2:为什么归并排序空间是 ,快排是 ,但大家还嫌快排「费内存」?
这是一种误传。快排的额外数组空间确实是 ,但递归栈要 。
相比之下堆排序是真正的 空间(迭代实现,无递归)。
更准确的说法是:归并要额外的 堆内存(大数组时可能是几百 MB),而快排的 栈可以忽略。
在内存受限场景(嵌入式、GPU),堆排序才是首选。
Q3:既然有 的计数排序,为什么还要用 的快排?
因为计数排序的 里 是值域,不是数据量。三个限制:
① 只支持整数(或能映射为紧凑整数);
② 必须与 同阶,否则 会爆炸(
n=100, 值域=10^9时需要 4 GB 计数数组);③ 额外 空间。
比较排序对任意可比较类型都适用,不依赖值的分布,泛用性强得多。
Q4:为什么
std::sort是不稳定的,而std::stable_sort存在?我该用哪个?因为稳定性有代价(需要 额外空间或额外的指针操作)。C++ 把选择权交给用户:
-
std::sort:Introsort,不稳定,但更快、内存更省( 栈)-
std::stable_sort:归并类,稳定,但需要 额外空间选择原则:只有当「排序键相等但元素的相对次序有意义」时才需要
stable_sort。如果排序键是元素的全部可比信息,用
std::sort就够了。
Q5:面试里常说的「手写快排」应该写成什么样?
建议准备随机化基准 + Lomuto 划分的版本(最易写对),并能口头说明:
① 为什么需要随机化(避免有序输入退化);
② 最坏 的触发条件与递推式;
③ 为什么不稳定(远距离交换);
④ 小区间切换插入排序的优化();
⑤ 三路划分如何解决重复元素问题。
如果面试官追问,能写出 Hoare 划分(交换次数更少)会加分。
Q6:如何排序一个 10 GB 的日志文件,机器只有 16 GB 内存?
先估算: 约 行,每行 100 字节。若能在内存里装下(16 GB > 10 GB),
直接用
sorted(),但要注意 Python 对象的开销——一个 100 字节的字符串在 CPython 里约占 150 字节(含头部),加上 list 指针,10 GB 文本对应约 20~25 GB 内存,装不下。
所以要么用外部排序(见题 5),要么改用
numpy/pandas的定长 dtype,要么用 Unix 工具链:
sort -S 8G --parallel=4 bigfile.log > sorted.log(GNU sort 自带外部排序)。
相关笔记
- 算法-复杂度分析:本篇所有 记号、递推式与 下界的理论基础
- 数据结构-树与堆:堆排序与 Top-K 依赖的完全二叉树与优先队列
- 算法-查找与分治:分治思想、二分查找与快速选择的进一步展开
- 算法-动态规划与贪心:Kruskal 等贪心算法以排序作为第一步
- 数据结构-线性结构:数组与链表是排序算法的底层容器
- Python-02-内置数据结构:Python 列表排序 API 与内置容器的配合
- 00-索引:全库笔记导航
- 学习路线图:按阶段的学习顺序建议
参考来源
- OI Wiki 排序基础:https://oi-wiki.org/basic/sort/
- OI Wiki 基数排序:https://oi-wiki.org/basic/radix-sort/
- Python 官方文档 sorted:https://docs.python.org/3/library/functions.html#sorted
- Python 官方文档 Sorting HOW TO(含 key 与稳定性说明):https://docs.python.org/3/howto/sorting.html
- Python 官方文档 functools.cmp_to_key:https://docs.python.org/3/library/functools.html#functools.cmp_to_key
- CPython 源码 listsort.txt(Timsort 设计文档,Tim Peters 著):https://github.com/python/cpython/blob/main/Objects/listsort.txt
- VisuAlgo 排序可视化:https://visualgo.net/en/sorting
- MIT OCW 6.006 Introduction to Algorithms:https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MDN Array.prototype.sort:https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
- cppreference std::sort:https://en.cppreference.com/w/cpp/algorithm/sort
- Java Arrays.sort 文档:https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/Arrays.html#sort(int%5B%5D)
- C# Array.Sort 文档:https://learn.microsoft.com/en-us/dotnet/api/system.array.sort