03 · 排序算法（Sorting Algorithms）

📅 预计 110 分钟　|　⭐ 本章主题：九种排序方法，一张表全搞懂
📌 中英术语见文末

3.1 排序问题与稳定性 ⭐

先分清"比大小"和"数数"两条路线

排序问题：给定 n 个元素，把它们按升序（或降序）排好。几乎所有算法都围绕"比较"展开，但注意存在两条根本不同的路线：

  • 比较排序（comparison sort）：靠两两比较大小决定顺序，如冒泡、选择、插入、希尔、归并、快排、堆排。它们的复杂度下界是 Ω(n log n)——不可能比这更快（原因直觉：n 个元素的排列有 n! 种，每次比较只能二分可能性，需要约 log₂(n!) ≈ n log n 次比较）。
  • 非比较排序（non-comparison sort）：不比较大小，而是利用元素本身的取值直接"按位入桶"，如计数排序，可达到 O(n)。

稳定性（stability）是常被忽略却常考的概念：排序后，值相等的两个元素，若相对顺序保持原样，这个排序就是稳定的；否则不稳定。为什么重要？因为实际排序经常是"多关键字"——先按学号排，再按成绩排，只有稳定排序才能保证第二次排序后，成绩相同的仍按学号排（见 3.10 的 Python sorted 示例）。

# 检验稳定性的例子：按 (值, 原始序号) 观测
data = [(2, "甲"), (1, "乙"), (2, "丙")]
# 值相同的是 (2, 甲) 和 (2, 丙)，稳定排序后它们的顺序应保持 甲 在 丙 前

⚠️ 常见错误

  1. 把"稳定"理解成"每次结果一样"：稳定特指相等元素的相对顺序不变，不是结果唯一。
  2. 说"所有排序下界 O(n log n)"：只对比较排序成立，计数排序这类非比较排序可以突破到 O(n)。
  3. 忽略稳定性在多关键字排序中的作用：第二次按次要关键字排时，稳定性能保住第一次的主关键字顺序。

3.2 冒泡排序

相邻比较，大数一路"冒"到末尾

冒泡排序（bubble sort）：从左到右两两比较，如果左边比右边大就交换。一趟下来，最大的元素像气泡一样"冒"到了末尾；下一趟再对剩下的 n-1 个做同样的事。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):                  # 共 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

print(bubble_sort([5, 1, 4, 2, 8]))
# 输出: [1, 2, 4, 5, 8]

复杂度：两层循环嵌套，O(n²)；空间 O(1)（原地交换）。加上 swapped 标记后，最好情况（已有序）一趟就结束，O(n)。稳定。

⚠️ 常见错误

  1. 内层边界写错：range(n - 1 - i) 里漏掉 - i，会越界比较已排好的元素，虽不崩但多干活。
  2. 没加提前结束：不加 swapped 标记，最好情况也是 O(n²)。
  3. 交换写错：arr[j], arr[j+1] = arr[j+1], arr[j] 才是交换；写成赋值就丢数据。

3.3 选择排序

每趟挑最小的，放到最前面

选择排序（selection sort）：第一趟在整个数组里找出最小值，跟第一个位置交换；第二趟在剩下元素里找出最小值，跟第二个位置交换……第 i 趟就是"在未排序部分挑最小的，放到未排序部分的开头"。

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

print(selection_sort([64, 25, 12, 22, 11]))
# 输出: [11, 12, 22, 25, 64]

复杂度：无论数据怎样，内外两层循环都要完整走完，恒为 O(n²)；空间 O(1)。不稳定——交换可能把相等元素的相对顺序打乱。

⚠️ 常见错误

  1. 以为最好情况是 O(n)：选择排序没有任何"提前结束"机制，已有序也是 O(n²)。
  2. 说它稳定：交换两个远距离元素时，相等元素相对顺序可能被破坏，是不稳定的。
  3. 忘记更新 min_idx：条件里写成 arr[j] < arr[i] 而不是 arr[j] < arr[min_idx]，找的就永远不是最小值。

3.4 插入排序

像打扑克理牌：新牌插到已排好牌堆的合适位置

插入排序（insertion sort）：把数组看成"已排好的前缀 + 未处理的当前元素"。每步取当前元素，从后往前在已排序前缀里找位置，把它插进去（后面的元素依次后移）。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]                       # 当前要插入的牌
        j = i - 1
        while j >= 0 and arr[j] > key:     # 比 key 大的都往后挪
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key                   # 找到位置插入
    return arr

print(insertion_sort([5, 2, 4, 6, 1, 3]))
# 输出: [1, 2, 3, 4, 5, 6]

复杂度：平均和最坏 O(n²)；但最好情况（基本有序）只需 O(n)——每步几乎不挪动。空间 O(1)，稳定。它的亮点在于"近乎有序的数据"：元素位移少，实际很快，Python 内置排序对小区间就用了类似思路。

💡 记忆口诀：打牌理牌——新牌从后往前比，比它大的往后挪，找到空位落下去。

⚠️ 常见错误

  1. 忘记从后往前：从前往后插会导致已排序部分顺序错乱，还得再排序。
  2. 边界条件 j >= 0：写成 j > 0 会漏掉和第一个元素的比较。
  3. 移动而不是交换：插入排序用"整体后移 + 插入"，不是每步都交换；用交换虽然结果对，但性能差很多。

3.5 希尔排序

插入排序的"隔空"升级：先分组再精排

希尔排序（shell sort）思路：插入排序慢在"元素只能一步步挪"。希尔先按间隔 gap 分组，把相距 gap 的元素当作一组做插入排序；然后 gap 逐渐缩小，最后 gap=1 时就是普通插入排序。因为前期跳跃式移动把大元素快速送到后面，最后一趟几乎不用挪。

def shell_sort(arr):
    n = len(arr)
    gap = n // 2                          # 初始间隔
    while gap > 0:
        for i in range(gap, n):           # 对每个间隔组做插入排序
            key = arr[i]
            j = i
            while j >= gap and arr[j - gap] > key:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = key
        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 //= 2 下大约是 O(n^(3/2)) ~ O(n²) 之间；空间 O(1)，不稳定（分组跳着比较，相等元素可能被隔开交换）。

⚠️ 常见错误

  1. gap 序列选错：gap 必须最后递减到 1，否则排序不完整。
  2. 说希尔稳定：间隔比较与交换会破坏相等元素的相对顺序，不稳定。
  3. 内层循环边界：while j >= gap 写成 j >= 0，会跟"隔 gap 个之前"混淆。

3.6 归并排序

复习：拆到单元素，两两有序合并

归并排序已在第 02 章详述，这里从排序角度补充要点：

  • 时间：最坏、最好、平均都是 O(n log n)，是"最坏也有保证"的典型；
  • 空间：O(n)——合并需要临时数组；
  • 稳定：合并时取左数组相等元素，稳定。
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    i = j = 0
    res = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= 保证稳定
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res

print(merge_sort([4, 2, 2, 8, 3, 3, 1]))
# 输出: [1, 2, 2, 3, 3, 4, 8]

⚠️ 常见错误

  1. 忘了空间成本：归并 O(n log n) 的时间是拿 O(n) 的空间换来的，面试常问这个 trade-off。
  2. 合并漏尾部：extend 收尾两行不能省。
  3. 稳定性由 <= 保证：写成 < 会把相等的右元素先取，稳定性被破坏。

3.7 快速排序

复习：选基准划分，递归排序两侧

快速排序见第 02 章。排序视角的要点：

  • 平均 O(n log n)、最坏 O(n²)（已有序数据 + 端点基准）；现代实现常选"三数取中"缓解退化；
  • 空间 O(log n)（递归栈平均深度）；
  • 不稳定（分区交换会打乱相等元素相对顺序）。
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quick_sort(less) + equal + quick_sort(greater)

print(quick_sort([3, 0, 2, 5, -1, 4, 1]))
# 输出: [-1, 0, 1, 2, 3, 4, 5]

稳定性对比：同为 O(n log n) 的高级排序，归并稳定、快排不稳定、堆排不稳定（见下节）。

⚠️ 常见错误

  1. 把快排当"稳定"：分区时跨位置交换，相等元素顺序可能翻转。
  2. 只记平均不记最坏：T(n) = T(n-1) + n 的退化情形复杂度是 O(n²)。
  3. 基准选第一个元素：对已排序数据会直接退化，实践中常用随机或三数取中。

3.8 堆排序

用二叉堆当"优先队列"，反复取最大值

堆（heap）是一棵完全二叉树，满足堆序：父节点不小于（最大堆）或不大于（最小堆）子节点。堆排序思路：把数组建成最大堆，堆顶就是最大值；把它和末尾交换，堆大小减一，再调整恢复堆序……重复 n-1 次。

直接利用 Python 的 heapq（它实现的是最小堆）可以一行做堆排序：

import heapq

def heap_sort(arr):
    heapq.heapify(arr)                    # 建堆，O(n)
    return [heapq.heappop(arr) for _ in range(len(arr))]

print(heap_sort([4, 10, 3, 5, 1]))
# 输出: [1, 3, 4, 5, 10]

复杂度：建堆 O(n)，每次弹出 O(log n)，共 n 次 → O(n log n)；空间 O(1)（原地堆排序）；不稳定。堆的另一个重要用途是优先队列：反复取最大/最小元素只需 O(log n)，是实现贪心算法（第 04 章哈夫曼编码）和调度问题的常用工具。

# heapq 的两个高频操作
import heapq
pq = []
heapq.heappush(pq, 5)        # 入队 O(log n)
heapq.heappush(pq, 2)
heapq.heappush(pq, 8)
print(heapq.heappop(pq))     # 取最小元素 O(log n)
# 输出: 2

⚠️ 常见错误

  1. 建堆复杂度记成 O(n log n)：把 n 个元素逐个 push 才是 O(n log n)，heapify 直接建堆是 O(n)。
  2. 说堆排稳定：堆内跳跃式交换，不稳定。
  3. heapq 只给最小堆：要最大堆，存 -x 或用其他技巧，heapq 没有内置最大堆。

3.9 计数排序

非比较排序：直接数每个值出现几次

计数排序（counting sort）完全不比较大小。它适用于取值范围有限且已知的整数数组（如 0~k）：先统计每个值出现多少次，再按值从小到大把对应个数的元素"倒"回结果里。

def counting_sort(arr, k):
    """对 0..k 范围内的整数排序"""
    count = [0] * (k + 1)
    for x in arr:
        count[x] += 1                       # 统计频次
    res = []
    for v in range(k + 1):
        res.extend([v] * count[v])          # 按值从小到大回填
    return res

print(counting_sort([4, 2, 2, 8, 3, 3, 1], 8))
# 输出: [1, 2, 2, 3, 3, 4, 8]

复杂度：统计一遍 O(n)，回填一遍 O(n + k)，总计 O(n + k)，当 k 与 n 同量级时就是 O(n)——比比较排序的下界还快，因为它绕开了"两两比较"。代价是空间 O(k)，且只能排整数或可映射到整数的值。它稳定（按值回填时保持原顺序），是基数排序的基础。

💡 记忆口诀：计数排序不比大小——数一数每个值出现几回，按从小到大倒回去，快但挑食（只吃范围小的整数）。

⚠️ 常见错误

  1. 把"计数"和"比较"搞混：计数排序是非比较排序，这是它能突破 O(n log n) 的原因。
  2. k 很大时空间爆炸：k=10⁹ 时建 count 数组不现实，只适合值域紧凑的数据。
  3. 忘了定义值域：函数参数 k 必须大于等于数组最大值，否则数组越界。

3.10 复杂度对照总表与适用场景 ⭐

一张表记全部排序

算法 最好 平均 最坏 空间 稳定
冒泡排序 O(n) O(n²) O(n²) O(1) ✅
选择排序 O(n²) O(n²) O(n²) O(1) ❌
插入排序 O(n) O(n²) O(n²) O(1) ✅
希尔排序 O(n log n) 视间隔 O(n²) O(1) ❌
归并排序 O(n log n) O(n log n) O(n log n) O(n) ✅
快速排序 O(n log n) O(n log n) O(n²) O(log n) ❌
堆排序 O(n log n) O(n log n) O(n log n) O(1) ❌
计数排序 O(n+k) O(n+k) O(n+k) O(k) ✅

适用场景速记：

  • 数据基本有序 / 数据量小 → 插入排序（最好 O(n)）。
  • 数据量中等，代码越简单越好 → 冒泡、选择、插入随便选。
  • 数据量大，要求最坏也有保证 → 归并排序。
  • 数据量大，默认通用选择 → 快速排序（实践中最快）。
  • 要求 O(1) 空间 + 稳定的大规模排序 → 优先考虑归并（稳定但空间大）或堆（省空间但不稳定）。
  • 值域小且都是整数 → 计数排序，能到 O(n)。

生产环境：Python 内置 sorted / list.sort() 用的是 Timsort——一种结合归并与插入的稳定排序，最坏 O(n log n)，对"已有序片段"特别快。日常写代码永远优先用内置排序。

# 内置排序 + 多关键字 + 稳定性
students = [("乙", 90), ("甲", 90), ("丙", 85)]
ordered = sorted(students, key=lambda s: -s[1])   # 先按成绩降序
print(ordered)
# 输出: [('乙', 90), ('甲', 90), ('丙', 85)]
# 成绩同为 90 的 乙、甲 保持原相对顺序 —— 这就是稳定性在起作用

⚠️ 常见错误

  1. 照搬复杂度表不看场景：插入排序是 O(n²) 却适合"基本有序"的大数组，快排是 O(n log n) 却怕已有序数据——场景比裸复杂度重要。
  2. 生产代码自己写排序：内置 sorted 是 Timsort，稳定且经过极限优化，除非学习或特殊需求否则别手写。
  3. 漏记"稳定"列：多关键字排序、面试追问时稳定性是高频问题。

🧠 记忆口诀

  • 冒泡：相邻比较，大数冒泡到末尾；加个标记，有序提前停。
  • 选择：每趟挑最小放开头，好坏都是 O(n²)，不稳定。
  • 插入：打牌理牌从后往前插，基本有序 O(n)，稳定。
  • 希尔：隔空插入，间隔递减到 1；不稳定。
  • 归并：拆单元素再合并，最坏也 O(n log n)，稳定但费空间。
  • 快排：基准划分，平均 O(n log n) 最坏 O(n²)，不稳定。
  • 堆排：建堆取顶，O(n log n) 省空间，不稳定。
  • 计数：数频次按值回填，O(n+k) 只吃范围小的整数，稳定。
  • 稳定性三兄弟：冒泡、插入、归并、计数稳；选择、快排、堆排不稳。

📌 中英术语表（本讲）

中文 English 说明
排序算法 sorting algorithm 把元素按序排列
稳定性 stability 相等元素保持原相对顺序
比较排序 comparison sort 靠两两比较，下界 Ω(n log n)
非比较排序 non-comparison sort 利用取值入桶，可达 O(n)
冒泡排序 bubble sort 相邻交换，大数上浮
选择排序 selection sort 每趟选最小放开头
插入排序 insertion sort 新元素插入已排序前缀
希尔排序 shell sort 间隔分组插入排序
归并排序 merge sort 拆到单元素两两合并
快速排序 quick sort 基准划分递归排序
堆排序 heap sort 最大堆反复取堆顶
计数排序 counting sort 统计频次按值回填
二叉堆 binary heap 完全二叉树，满足堆序
优先队列 priority queue 支持快速取最大/最小
多关键字排序 multi-key sort 靠稳定排序层层排序

⭐ 本章考点清单

  1. 稳定性定义与三个稳定/三个不稳定排序
  2. 冒泡、选择、插入代码与复杂度推导
  3. 插入排序对"基本有序"数据的优势（最好 O(n)）
  4. 希尔排序思想：间隔分组、递减到 1
  5. 归并排序 O(n log n) 最坏保证、空间 O(n)、稳定
  6. 快速排序平均/最坏复杂度差异与退化原因
  7. 堆排序：建堆 O(n)、弹出 O(log n)、heapq 用法
  8. 计数排序 O(n+k)、非比较、只适用整数小值域
  9. 八种排序复杂度/空间/稳定对照表
  10. Python 内置 sorted 为 Timsort、多关键字稳定排序