Ch14 §05 排序与搜索 · 讲解稿¶

章节定位: 排序与查找。教"如何把数据有序 + 快速找": 冒泡 / 插入 / 选择 / 快排 / 归并 / 堆排 / 计数 / 基数 / Tim / 二分。承接: §04 图 → §05 排序 (基础操作) 走向: 后续章节结合排序 (e.g., GNN 邻居选择, Beam search) 篇幅: ~3800 字 / 阅读 11 分钟 / 讲解 22-25 分钟

一 · 一句话总览¶

排序 + 搜索 = 把数据排成有序 + 在有序中找。AI 应用: 分布式 Shuffle (MapReduce), 优先队列 (RL 经验), Top-K (推荐)。Python sorted() 默认 Tim 排序。

二 · 章节主线 (5 段)¶

第 1 段 · 排序总览 (5 分钟)¶

算法	时间 (avg)	空间	稳定
冒泡	\(O(n^2)\)	\(O(1)\)	✓
插入	\(O(n^2)\)	\(O(1)\)	✓
选择	\(O(n^2)\)	\(O(1)\)	✗
快排	\(O(n \log n)\)	\(O(\log n)\)	✗
归并	\(O(n \log n)\)	\(O(n)\)	✓
堆排	\(O(n \log n)\)	\(O(1)\)	✗
计数	\(O(n+k)\)	\(O(k)\)	✓
基数	\(O(nk)\)	\(O(n+k)\)	✓
Tim	\(O(n)\) best, \(O(n \log n)\) avg	\(O(n)\)	✓

第 2 段 · 简单排序 (5 分钟)¶

3.2.1 冒泡排序¶

相邻两两交换, 每轮最大冒到末尾。

def bubble(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped: break  # 已有序
    return arr

3.2.2 插入排序¶

逐个插入到已排序部分。

def insertion(arr):
    for i in range(1, len(arr)):
        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

适合小数组 / 几乎有序。

3.2.3 选择排序¶

每轮选最小放前。

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

第 3 段 · 高效排序: 快排 + 归并 (10 分钟)¶

3.3.1 快速排序¶

分治: 选 pivot, 小左大右, 递归。

def quicksort(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 quicksort(left) + mid + quicksort(right)

\(O(n \log n)\) 平均, \(O(n^2)\) 最坏 (pivot 极端)。随机化 pivot 避免:

import random
def quicksort_inplace(arr, lo=0, hi=None):
    if hi is None: hi = len(arr) - 1
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort_inplace(arr, lo, p - 1)
        quicksort_inplace(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot_idx = random.randint(lo, hi)
    arr[pivot_idx], arr[hi] = arr[hi], arr[pivot_idx]
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

3.3.2 归并排序¶

分治: 拆两半, 各自排, 合并。

def mergesort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(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

\(O(n \log n)\) 严格, 空间 \(O(n)\)。

3.3.3 堆排序¶

建堆 \(O(n)\), 反复取顶 \(O(\log n)\)。

def heapsort(arr):
    import heapq
    heapq.heapify(arr)  # O(n)
    return [heapq.heappop(arr) for _ in range(len(arr))]  # O(n log n)

\(O(n \log n)\) 严格, 空间 \(O(1)\)。

第 4 段 · 线性排序 (5 分钟)¶

3.4.1 计数排序¶

数据范围 \(k\) 小时, \(O(n+k)\)。

def counting(arr, k):
    cnt = [0] * (k + 1)
    for x in arr: cnt[x] += 1
    result = []
    for i, c in enumerate(cnt):
        result.extend([i] * c)
    return result

3.4.2 基数排序¶

按位排序 (低位优先), \(O(nk)\), \(k\) 是位数。

def radix(arr):
    if not arr: return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        arr = sorted(arr, key=lambda x: (x // exp) % 10)
        exp *= 10
    return arr

第 5 段 · 搜索与 Tim 排序 (10 分钟)¶

3.5.1 顺序搜索¶

\(O(n)\), 无序可用。

3.5.2 二分查找¶

\(O(\log n)\), 必须有序。

def binary(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1

3.5.3 二分变种¶

找左边界 / 右边界
旋转数组查找
山脉数组峰值

3.5.4 Tim 排序¶

Python sorted() / list.sort() 默认。归并 + 插入混合。

找有序 run (片段)
run 太短用插入排序扩展
run 合并 (类似归并, 但自适应)

最坏 \(O(n \log n)\), 最好 \(O(n)\) (已排序), 空间 \(O(n)\)。

3.5.5 Python 排序细节¶

sorted([3, 1, 2])  # [1, 2, 3]
sorted([3, 1, 2], reverse=True)  # [3, 2, 1]
sorted([3, 1, 2], key=lambda x: -x)  # [3, 2, 1]
arr.sort()  # 原地
arr.sort(key=len)  # 按字符串长度

3.5.6 排序应用¶

数据库 ORDER BY
Top K (堆 / 快选)
分布式 Shuffle (PyTorch DataLoader)

三 · 易错点 (5 条)¶

稳定性: 排序保留相等元素原顺序, 重要!
快排最坏: pivot 选极端退化为 \(O(n^2)\)。
二分前提: 必须有序。
Tim 空间: \(O(n)\), 不是原地。
Python sort: Tim, 已优化, 自己写比不过。

四 · 跨章连接¶

章节	关联
Ch12 §03 GNN	Top-K 邻居选择
Ch11 §05 SLAM	排序决定路径
Ch13 §04 MapReduce	Shuffle = 排序
Ch06 §04 RL	优先经验回放 (堆)

五 · 自测 5 题¶

排序稳定性举例?
快排最坏情况? 如何避免?
计数排序适用?
二分查找前提?
Tim 排序优势?

六 · 一句话总结¶

排序 + 搜索 = \(O(n \log n)\) 默认 (快排/归并/Tim), \(O(n)\) 特殊 (计数), \(O(\log n)\) 搜索 (二分)。Python 用 Tim。Ch14 至此讲完 — 6 节覆盖数据结构与算法, 是 AI 工程师内功。

七 · 板书建议¶

[板书 1: 简单排序]
   冒泡 / 插入 / 选择
   $O(n^2)$, 教学用

[板书 2: 高效排序]
   快排 / 归并 / 堆排
   $O(n \log n)$

[板书 3: 线性]
   计数 / 基数
   $O(n+k)$ / $O(nk)$

[板书 4: 搜索]
   顺序 $O(n)$ / 二分 $O(\log n)$
   Tim: 归并 + 插入

八 · 参考资料¶

Cormen et al., CLRS Ch 2, 6-8 (排序)
Tim Peters, "Tim Sort", 2002
Python sorted 文档
Ch13 §04 MapReduce (本套书)
Ch06 §04 RL (本套书)