在排序算法家族中，堆排序和归并排序是两种基于不同数据结构与策略的高效排序方法。堆排序利用二叉堆这种数据结构实现选择排序的优化；归并排序则完美体现了“分治”思想，通过合并有序子序列来完成整体排序。本文将系统讲解这两种算法的原理、步骤、实现细节、复杂度分析，并通过大量示例与代码帮助你深入理解。

---

堆排序（Heap Sort）

算法思想

堆排序是一种基于选择排序思想、但借助二叉堆数据结构来加速查找最值过程的排序算法。它的核心是：先将待排序数组构建成一个最大堆（或最小堆），然后反复取出堆顶元素（即当前最大值/最小值），将其与堆尾元素交换，并缩小堆的范围，对剩余元素重新调整成堆。重复此过程直到所有元素有序。

二叉堆是一种完全二叉树，满足：

• 最大堆：每个节点的值都大于或等于其子节点的值，堆顶是全局最大值。
• 最小堆：每个节点的值都小于或等于其子节点的值，堆顶是全局最小值。

堆排序通常使用最大堆进行升序排序，使用最小堆进行降序排序。

算法步骤（升序）

1. 建堆：将无序数组构建成一个最大堆。从最后一个非叶子节点开始，自底向上进行堆化（heapify）操作。
2. 排序：
   • 交换堆顶（最大值）与堆末尾元素，此时末尾元素已归位。
   • 堆长度减1，并对新的堆顶元素执行堆化，恢复剩余部分的最大堆性质。
   • 重复上述交换-堆化过程，直到堆长度为1。

示例演示

假设待排序数组：[4, 10, 3, 5, 1]，使用最大堆升序排序。

第一步：构建最大堆 原始数组（索引0~4）：

        4 (0)
       / \
    10(1) 3(2)
    / \
  5(3) 1(4)

从最后一个非叶子节点索引 = n//2 - 1 = 2//2-1=1? 需要明确：n=5，最后一个非叶子节点索引为 floor(5/2)-1 = 2-1=1，即节点10。但为了直观，我们按完整过程：

• 依次对索引1、0进行堆化。
• 堆化节点1（值10）：其子节点5和1都小于10，无需交换。
• 堆化节点0（值4）：比较4与左右子节点10和3，最大为10，交换4和10 → 数组变为 [10,4,3,5,1]，此时节点0值为10，但节点1（值为4）破坏了堆性质，需要递归堆化节点1。
• 堆化节点1（值4，子节点5,1）：4与5交换 → [10,5,3,4,1]，节点3（原4）已经是叶子，停止。 最大堆构建完成：[10,5,3,4,1]，堆顶10为最大值。

第二步：排序过程

• 交换堆顶10与末尾1 → [1,5,3,4,10]，堆长度减少为4（忽略索引4的10）。对索引0（值1）堆化：
  • 子节点5,3，最大为5，交换1和5 → [5,1,3,4,10]，递归堆化索引1（值1，子节点4, 无）：1与4交换 → [5,4,3,1,10]。此时堆为[5,4,3,1]（忽略10）。
• 交换堆顶5与末尾1（此时末尾指前4个元素的最后索引3）→ [1,4,3,5,10]，堆长度减为3，对索引0堆化：
  • 子节点4,3，最大4，交换1和4 → [4,1,3,5,10]，递归堆化索引1（值1，子节点3）：交换1和3 → [4,3,1,5,10]。
• 交换堆顶4与末尾1（前3个元素的末尾索引2）→ [1,3,4,5,10]，堆长度减为2，对索引0堆化：
  • 子节点3（只有左子），交换1和3 → [3,1,4,5,10]。
• 交换堆顶3与末尾1（前2个元素的末尾索引1）→ [1,3,4,5,10]，堆长度减为1，结束。 最终升序结果：[1,3,4,5,10]

代码实现（Python）

def heapify(arr, n, i):
    """
    将以 i 为根的子树堆化为最大堆
    n: 堆的有效大小
    i: 当前根节点索引
    """
    largest = i          # 初始化最大值为根
    left = 2 * i + 1     # 左子节点索引
    right = 2 * i + 2    # 右子节点索引

    # 如果左子节点存在且大于根
    if left < n and arr[left] > arr[largest]:
        largest = left
    # 如果右子节点存在且大于当前最大值
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是根，则交换并继续堆化受影响的子树
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 1. 构建最大堆（从最后一个非叶子节点开始）
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 2. 一个个取出元素
    for i in range(n - 1, 0, -1):
        # 将当前堆顶（最大值）交换到末尾
        arr[i], arr[0] = arr[0], arr[i]
        # 堆大小减1，并重新堆化根节点
        heapify(arr, i, 0)
    return arr

# 测试
test_arr = [4, 10, 3, 5, 1]
print("排序前:", test_arr)
sorted_arr = heap_sort(test_arr.copy())
print("堆排序后:", sorted_arr)

复杂度与稳定性

• 时间复杂度：
  • 建堆：O(n)
  • 每次堆化：O(log n)，共 n-1 次交换-堆化 → 总 O(n log n)
  • 最好/最坏/平均情况均为 O(n log n)，没有最坏情况退化（与快速排序不同）
• 空间复杂度：O(1)，原地排序
• 稳定性：不稳定（因为堆顶与末尾交换可能打乱相同元素的相对顺序，且堆化过程不保证稳定性）

特点与使用场景

• 优点：时间复杂度稳定 O(n log n)，空间复杂度 O(1)，适合大规模数据且对额外空间敏感的场景（如嵌入式系统）。
• 缺点：实际运行速度通常比快速排序慢（因为缓存不友好，且堆化的常数较大）；不稳定。
• 优先队列应用：堆排序的核心数据结构——堆，广泛用于实现优先队列（如任务调度、Dijkstra 算法）。

---

归并排序（Merge Sort）

算法思想

归并排序是一种典型的分治算法。它将待排序数组分成两个子数组，分别对它们递归地应用归并排序，然后将两个有序子数组合并成一个完整的有序数组。归并操作是算法的关键：它需要一个临时数组来存放合并结果。

与快速排序不同，归并排序的“分”总是从中间分割，不依赖基准选择，因此避免了最坏情况退化；但需要 O(n) 的额外空间来存储临时数据。

算法步骤（升序）

1. 分解：如果数组长度大于1，找到中间点 mid，将数组分成 left 和 right 两部分。
2. 递归：对左右两部分分别调用归并排序。
3. 合并：将两个已排序的子数组合并成一个新的有序数组，并覆盖原数组对应位置。

示例演示

待排序数组：[38, 27, 43, 3, 9, 82, 10]

递归分解过程：

              [38, 27, 43, 3, 9, 82, 10]
                     /         \
           [38, 27, 43]       [3, 9, 82, 10]
            /      \            /        \
        [38,27]   [43]      [3,9]      [82,10]
        /    \               /   \       /   \
     [38]   [27]           [3]  [9]   [82]  [10]

合并过程（自底向上）：

• 合并 [38] 和 [27] → [27, 38]
• 合并 [27,38] 和 [43] → [27,38,43]
• 合并 [3] 和 [9] → [3,9]
• 合并 [82] 和 [10] → [10,82]
• 合并 [3,9] 和 [10,82] → [3,9,10,82]
• 合并 [27,38,43] 和 [3,9,10,82] → [3,9,10,27,38,43,82]

最终结果：[3, 9, 10, 27, 38, 43, 82]

代码实现（Python）

递归版本（更直观）

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

# 测试
test_arr = [38, 27, 43, 3, 9, 82, 10]
print("排序前:", test_arr)
sorted_arr = merge_sort(test_arr)
print("归并排序后:", sorted_arr)

原地修改数组的版本（更节省内存，但需要辅助数组）

def merge_sort_inplace(arr, left, right, temp):
    """
    对 arr[left:right] 进行归并排序（右边界不包含）
    temp 为相同长度的辅助数组
    """
    if left + 1 < right:  # 至少两个元素
        mid = (left + right) // 2
        merge_sort_inplace(arr, left, mid, temp)
        merge_sort_inplace(arr, mid, right, temp)
        merge(arr, left, mid, right, temp)

def merge(arr, left, mid, right, temp):
    i, j, k = left, mid, left
    while i < mid and j < right:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1
    while i < mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j < right:
        temp[k] = arr[j]
        j += 1
        k += 1
    # 将临时数组中的有序数据拷贝回原数组
    for idx in range(left, right):
        arr[idx] = temp[idx]

# 使用示例
test_arr = [38, 27, 43, 3, 9, 82, 10]
temp = [0] * len(test_arr)
merge_sort_inplace(test_arr, 0, len(test_arr), temp)
print("原地归并排序后:", test_arr)

复杂度与稳定性

时间复杂度：

递推公式 T(n) = 2T(n/2) + O(n)，解得 最好/最坏/平均均为 O(n log n)

无论数据初始顺序如何，归并排序都会先分解再合并，因此没有性能波动

空间复杂度： O(n)（需要临时数组存放合并结果）。递归版本还有 O(log n) 的调用栈空间

稳定性： 稳定（在合并时当左右元素相等时，优先取左子数组元素，可保证相等元素的相对顺序不变）

特点与使用场景

优点： 稳定，时间复杂度稳定 O(n log n)，适合大规模数据，特别适合链表排序（链表归并不需要额外数组空间，只需调整指针）。

缺点： 需要 O(n) 额外空间，对于内存受限的环境可能不友好；对于小数组，递归和额外数组的开销可能超过收益（可结合插入排序优化）。

典型应用： 外部排序（内存不足以一次装入全部数据时，使用多路归并）、数据量大且稳定性要求高的场景（如数据库中 ORDER BY 操作可能使用归并排序）。

堆排序 vs 归并排序

特性	堆排序	归并排序
时间复杂度	O(n log n) 所有情况	O(n log n) 所有情况
空间复杂度	O(1) 原地排序	O(n) 额外数组
稳定性	不稳定	稳定
适用数据结构	数组（能随机访问）	数组/链表均可高效实现
最坏情况性能	稳定 O(n log n)	稳定 O(n log n)
外部排序支持	不适合（需要随机访问）	非常适合（多路归并）
实现难度	中等（需理解堆结构）	简单（分治+合并）

选择建议：

对内存敏感：堆排序是原地排序，不占额外空间，适合嵌入式或内存严格受限环境。

要求稳定性：归并排序或稳定的 Timsort 是更好的选择。

链表排序：归并排序是链表排序的最佳选择（不需要随机访问，空间 O(log n) 递归栈或迭代实现）。

普通场景：实际语言内置排序（如 Python 的 Timsort）融合了归并排序和插入排序的优点，性能更好。

总结

堆排序通过构建二叉堆，将选择排序中每次 O(n) 查找最值的过程优化为 O(log n)，实现了稳定的 O(n log n) 时间复杂度和 O(1) 空间复杂度。归并排序则采用分治法，先分割再合并，算法简单且性能稳定，还能保证稳定性，是数据库排序的常见选择。

理解这两种算法不仅能加深你对数据结构（堆）和算法范式（分治）的认识，还能帮助你在实际开发中根据场景（内存、稳定性、数据规模）做出更合理的技术决策。希望本文的详细讲解、示例与代码能帮助你彻底掌握堆排序和归并排序。