波仔
⌨️ 第四章 流程图与算法
📄 一句话概括

把 O(n²) 推进到 O(n log n) 的两位功臣：归并排序——对半劈、各自排好、有序的两摞合成一摞（稳、稳、稳，但要辅助空间）；快速排序——选个基准、小的甩左边大的甩右边再各自递归（平均最快、原地、最坏会退化）。Python 的 sorted＝两者混血的 Timsort。

📝 本节和前面几节的关系

4-11／4-12 的 O(n²) 天花板在这一篇被【分治】捅破。回收 4-7 的递归（分治的骨架）与 3-17 的树（递归深度＝分叉层数，log n 就是这么来的）。

一、分治：大事化小的总思想

两者共用一个套路——分治（divide and conquer）：

  1. 分：把问题劈成两半；
  2. 治：每半各自解决（递归）；
  3. 合：把两半的答案合并成整体答案。

为什么快：n 个元素劈 log n 层（每劈一半），每层合并的总工作量是 n——n x log n。一百万个数据：O(n²) 是一万亿次操作，O(n log n) 约两千万次——差五万倍（回收 4-14 的账）。

二、归并排序：稳扎稳打

合并是灵魂：两摞各自有序的牌怎么合成一摞？——每次比较两摞顶牌、小的拿走：

左摞 [2, 5, 9]   右摞 [1, 3, 8]
比 2 与 1 -> 取 1；比 2 与 3 -> 取 2；比 5 与 3 -> 取 3；比 5 与 8 -> 取 5 ...
合并结果：[1, 2, 3, 5, 8, 9]

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # 等号保证稳定性
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]  # 接走剩余

print(merge([2, 5, 9], [1, 3, 8]))     # [1, 2, 3, 5, 8, 9]

全排序＝递归劈到单元素（天然有序）、再逐层 merge 回去。性格：稳定 O(n log n) 雷打不动（最坏也不退化）；代价是要 O(n) 辅助空间（合并得另开数组）。

三、快速排序：原地快刀

划分是灵魂：选一个基准，一趟把数组分成小于基准、大于基准两堆，基准落在正中；两边再各自递归：

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    small = [x for x in arr if x < pivot]
    mid   = [x for x in arr if x == pivot]
    big   = [x for x in arr if x > pivot]
    return quicksort(small) + mid + quicksort(big)

print(quicksort([5, 3, 8, 1, 9, 2]))   # [1, 2, 3, 5, 8, 9]

性格：平均 O(n log n) 且常数小（原地划分、缓存友好）——实践中通常最快；最坏 O(n²)：每次基准都选得极偏（如对已有序数组总拿头当基准）就退化成冒泡式两半失衡——工业实现用【三数取中】【随机基准】避开。上图的列表推导版（好读）其实开了新列表，真·原地版用双指针交换，思想相同。

四、动手 Demo：Timsort——归并与插入的混血儿

Python 的 sorted()／list.sort() 用 Timsort（2002 年 Tim Peters 发明）：归并的骨架＋插入排序处理小段与近有序段——对真实世界【大量部分有序】的数据格外快，且稳定。这就是 4-11 说【插入排序至今活着】的兑现处：

print(sorted([5, 3, 8, 1, 9, 2]))      # [1, 2, 3, 5, 8, 9] —— Timsort 在干活

data = [5, 3, 8, 1, 9, 2]
print(sorted(data), data)              # [1, 2, 3, 5, 8, 9] [5, 3, 8, 1, 9, 2]

看到什么算成功：两行排序结果——第一行直接返回新表；第二行同时验证 sorted() 不改原数据（对比 4-11 的原地版）。

读结果：一行 sorted 背后是 Timsort：归并的骨架＋插入排序处理小段与近有序段——4-11 与本篇的知识在标准库里会师。

五、30 秒实验

拿 sorted([2, 3, 4, 5, 1]) 与手写快排跑同一条【基本有序】数据——结果一样。再看 sorted 的文档字符串（help(sorted)）：写着【Timsort, stable】——Python 不需要你手写快排，但面试和选型需要你懂它。

六、常见误区

  1. 【快排永远最快】——错。平均最快；最坏 O(n²)（基准选偏）；要【最坏也稳】的场景（数据库、实时系统）用归并系。
  2. 【归并和快排都是 O(n log n)，随便选】——差三点：稳定性（归并稳、快排不稳）、空间（归并要 O(n)、快排原地 O(log n) 栈）、最坏行为（归并不退化）——按需求选。
  3. 【O(n log n) 已经是排序尽头】——对【比较排序】而言是的（信息论下界）；但不比较的排序（计数、基数排序）在特定数据上能到 O(n)——代价是适用面窄。
自测三问（点开对答案） 1. **分治三步是什么？为什么能到 O(n log n)？** 答：分（劈两半）、治（递归解决）、合（合并）；劈 log n 层、每层总工作量 n——相乘得 n log n。 2. **归并排序稳定、快排不稳定的根源？** 答：归并合并时【相等取左边】次序不乱；快排的划分是远距离交换，相等元素会被打乱相对次序。 3. **快排什么时候退化成 O(n²)、怎么防？** 答：基准选得极偏（如已有序时总取头）导致两半失衡；防法＝随机基准或三数取中。

相关笔记