高级排序（归并、快排、堆排）

🔄 从 O(n²) 到 O(n log n)——质的飞跃

上一节学的三种基础排序（冒泡、选择、插入）都是 O(n²)——数据量翻倍时，时间变为 4 倍。

对一万个数字排序时，O(n²) ≈ 1 亿次操作（可能花几秒）。对一百万个数字排序时，O(n²) ≈ 1 万亿次操作（可能要几天）。

但 O(n log n) 完全不同——一百万数字只需约 2000 万次操作（毫秒级）。

这就是为什么需要”高级排序”——归并排序、快速排序、堆排序全部达到了 O(n log n)。

🏪 类比：整理图书馆的书架

O(n²) 的方式（基础排序）：两个管理员一个个地比，把所有书重新排一遍。

O(n log n) 的方式（高级排序）：

• 归并：两个管理员各负责一半书架，排好后再合并——分而治之
• 快排：选定一个”基准书”，比它小的放左边，比它大的放右边，然后递归处理两边
• 堆排：先把所有书堆成一个”书堆”——最下面的书总是最大的——然后一本本取出来

---

⚔️ 归并排序（Merge Sort）——分治的经典

思想

归并排序是”分治思想”最直观的体现：

1. 分解：把数组分成两半
2. 解决：递归地对两半排序
3. 合并：把两个有序数组合并成一个有序数组

过程演示

原始：[8, 3, 5, 9, 1, 4, 7, 2]

分解：
        [8, 3, 5, 9, 1, 4, 7, 2]
       /                       \
  [8, 3, 5, 9]             [1, 4, 7, 2]
    /        \               /        \
  [8, 3]    [5, 9]        [1, 4]    [7, 2]
  /   \     /   \         /   \     /   \
[8]  [3]  [5]  [9]      [1]  [4]  [7]  [2]

合并（从底向上）：
[8]+[3]→[3,8]  [5]+[9]→[5,9]  [1]+[4]→[1,4]  [7]+[2]→[2,7]
    \             /                \             /
  [3,8]+[5,9]→[3,5,8,9]          [1,4]+[2,7]→[1,2,4,7]
            \                     /
        [3,5,8,9]+[1,2,4,7]→[1,2,3,4,5,7,8,9] ✅

代码实现

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # 分治：排序左半
    right = merge_sort(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) —— 需要额外的数组存合并结果
稳定性	✅ 稳定（合并时 <= 的非严格比较保证稳定）
适用场景	对稳定性有要求的大规模数据

---

⚡ 快速排序（Quick Sort）——实际最快

思想

快速排序也用了分治，但核心步骤在”分解”阶段而不是”合并”阶段：

1. 选择 pivot（基准）：从数组中选一个元素作为基准
2. 分区：把比 pivot 小的放左边，比 pivot 大的放右边
3. 递归：对左右两个分区分别排序

过程演示

原始：[8, 3, 5, 9, 1, 4, 7, 2]

选最后一个元素 2 作为 pivot：
分区后：[1, 2, 5, 9, 8, 4, 7, 3]
         ↑ pivot 到了正确位置

左分区 [1] 排序 → 一个元素，直接返回
右分区 [5, 9, 8, 4, 7, 3]，选 3 为 pivot
分区后：[3, 9, 8, 4, 7, 5]
         ↑ pivot 就位

继续递归……
最终：[1, 2, 3, 4, 5, 7, 8, 9] ✅

代码实现

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)   # 排序左分区
        quick_sort(arr, pivot_idx + 1, high)  # 排序右分区

def partition(arr, low, high):
    """
    分区：把比 pivot 小的放左边，大的放右边
    返回 pivot 的最终位置
    """
    pivot = arr[high]  # 选最后一个元素为 pivot
    i = low - 1        # i 指向"小元素区域"的末尾
    
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

关键特性

特性	值
时间复杂度（平均）	O(n log n)
时间复杂度（最坏）	O(n²) —— 每次都选到最大/最小的 pivot
空间复杂度	O(log n)——递归栈空间
稳定性	❌ 不稳定（分区时的交换会改变相对顺序）
适用场景	一般场景——平均最快，但最坏情况要避免

💡 如何避免快排最坏情况 O(n²)？

• 随机选 pivot——而不是固定选第一个或最后一个
• 三数取中法——从第一个、中间、最后一个元素中取中位数
• 当数据量小时切换到插入排序

快排为什么是”实际最快”？

虽然三种排序都是 O(n log n)，但快排通常更快：

• 快排的常数因子小——分区操作只是元素比较和交换，没有额外的数组复制
• 缓存友好——访问模式是顺序的
• 因此实际排序库中（C 语言的 qsort、C++ 的 std::sort）都基于快排

---

🥞 堆排序（Heap Sort）——无额外空间

堆排序的思路已经在 堆 一章讲过了：

1. 建堆：把无序数组建成最大堆（O(n)）
2. 排序：重复把堆顶（最大值）换到末尾，然后对剩余部分下沉（O(n log n)）

def heap_sort(arr):
    n = len(arr)
    
    # 建堆（最大堆）
    for i in range(n // 2 - 1, -1, -1):
        _sift_down(arr, i, n)
    
    # 排序
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # 堆顶→末尾
        _sift_down(arr, 0, i)             # 对剩余部分下沉

关键特性

特性	值
时间复杂度	O(n log n) —— 最好、平均、最坏都一样
空间复杂度	O(1) —— 原地排序，无需额外空间
稳定性	❌ 不稳定
适用场景	内存受限、或不需要稳定排序的场景

---

⚔️ 三种高级排序对比

算法	平均时间	最坏时间	空间	稳定	特点
归并排序	O(n log n)	O(n log n)	O(n)	✅	稳定，额外空间
快速排序	O(n log n)	O(n²)	O(log n)	❌	实际最快，最坏需优化
堆排序	O(n log n)	O(n log n)	O(1)	❌	原地排序，常数较大

实际选择

# Python 的默认排序——Timsort
# 是归并排序的优化版，混合了插入排序
arr.sort()  # 稳定，O(n log n)，适合大多数场景

# C 语言的 qsort —— 快速排序
qsort(arr, n, sizeof(int), compare);  // 不稳定，但快速

# C++ STL 的 sort —— 内省排序（快排 + 堆排混合）
std::sort(arr.begin(), arr.end());  // 快排+堆排混合，避免最坏情况

# Java 的 Arrays.sort —— Dual-Pivot QuickSort（基本类型）
# 或 Timsort（对象类型）

一个重要的优化思想——混合排序

现代排序库通常不是只用一种”纯”算法，而是混合多种：

Python 的 Timsort：
数据量 < 64 → 插入排序
数据量大 → 归并排序
数据部分有序 → 利用已有有序区间（gallopping mode）

C++ 的 std::sort：
递归深度 < 2*log(n) → 快排
递归深度超过阈值 → 切换到堆排
数据量 < 16 → 切换到插入排序

---

📝 小结

概念	一句话
归并排序	分治——先排好两半再合并，稳定但需额外空间
快速排序	分区——选 pivot 分成大小两边再递归，实际最快
堆排序	建最大堆 + 重复取堆顶，原地排序 O(1) 空间
O(n log n)	所有比较排序的理论下界
稳定性	归并稳定，快排和堆排不稳定
Timsort	Python/Java 的默认排序——归并优化版

🎯 小练习：给定 [3, 7, 1, 9, 4, 6, 2, 8]，手动模拟一次快速排序的完整过程（每次都选最后一个元素为 pivot）。

为什么先学这个？ 排序是算法中最经典的问题。理解排序后，学习另一种经典的搜索算法——二分搜索。之后进入算法设计思想——递归与分治。