堆排序：从原理到实践的全方位解析

堆排序（Heap Sort）是基于二叉堆数据结构实现的高效排序算法，其核心思想借鉴了 筛选最大 / 最小值 的逻辑 —— 通过构建有序的堆结构，反复提取堆顶元素并调整堆，最终实现整个序列的排序。作为一种原地、不稳定的比较排序算法，堆排序在大规模数据处理场景中表现突出。

1、核心原理与步骤拆解

堆排序的实现依赖二叉堆的特性，整个过程可拆分为 构建堆 和 调整堆 两大核心环节，具体逻辑如下：

1. 将待排序序列转化为大顶堆（这里构建可采用自下而上、自上而下的方式，可按照动态插入和已有完整数组来考虑具体的方式）；

2. 提取堆顶的最大值，将其与堆的最后一个元素交换，此时最大值已放置在序列末尾（完成排序）；

3. 对剩余元素重新执行堆调整，恢复大顶堆特性。

重复 提取 - 调整 步骤，直到堆的规模缩减为 1，整个序列完成排序。

1.1 排序拆解

以数组 [8, 5, 3, 9, 1] 为例，直观展示堆排序的完整过程：

1.2 伪代码

function heapSort(arr):
    n = 数组长度
    // 1. 构建大顶堆（从最后一个非叶子节点开始调整）
    for i from n//2 - 1 down to 0:
        heapify(arr, n, i)

    // 2. 提取堆顶元素并调整堆
    for i from n-1 down to 1:
        swap(arr[0], arr[i])  // 堆顶最大值与末尾元素交换
        heapify(arr, i, 0)    // 对剩余 i 个元素调整为大顶堆
    return arr

// 堆调整函数：将以 i 为根的子树调整为大顶堆
function heapify(arr, heapSize, rootIndex):
    largest = rootIndex       // 初始化最大值为根节点
    leftChild = 2*rootIndex + 1  // 左子节点索引
    rightChild = 2*rootIndex + 2 // 右子节点索引

    // 若左子节点大于根节点，更新最大值索引
    if leftChild < heapSize and arr[leftChild] > arr[largest]:
        largest = leftChild
    // 若右子节点大于当前最大值，更新最大值索引
    if rightChild < heapSize and arr[rightChild] > arr[largest]:
        largest = rightChild

    // 若最大值不是根节点，交换并递归调整子树
    if largest != rootIndex:
        swap(arr[rootIndex], arr[largest])
        heapify(arr, heapSize, largest)

2、算法实现

2.1 Java

public class HeapSort {
    // 基础堆排序（升序，基于大顶堆）
    public static void heapSort(int[] arr) {
        // 边界判断：空数组或单元素数组无需排序
        if (arr == null || arr.length <= 1) {
            return;
        }

        int n = arr.length;
        // 1. 构建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }

        // 2. 提取堆顶元素并调整堆
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶（最大值）与当前堆的末尾元素
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // 对剩余元素重新调整为大顶堆
            heapify(arr, i, 0);
        }
    }

    // 堆调整：将以 rootIndex 为根的子树转为大顶堆
    private static void heapify(int[] arr, int heapSize, int rootIndex) {
        int largest = rootIndex;
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;

        // 比较左子节点
        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        // 比较右子节点
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        // 若最大值不在根节点，交换并递归调整子树
        if (largest != rootIndex) {
            int temp = arr[rootIndex];
            arr[rootIndex] = arr[largest];
            arr[largest] = temp;

            heapify(arr, heapSize, largest);
        }
    }
}

2.2 Go

package main

// 基础堆排序（升序，基于大顶堆）
func heapSort(arr []int) []int {
    // 边界判断：空数组或单元素数组无需排序
    if arr == nil || len(arr) <= 1 {
        // 返回副本避免修改原数组
        result := make([]int, len(arr))
        copy(result, arr)
        return result
    }

    // 创建数组副本，避免修改原数组
    result := make([]int, len(arr))
    copy(result, arr)
    n := len(result)

    // 1. 构建大顶堆
    for i := n/2 - 1; i >= 0; i-- {
        heapify(result, n, i)
    }

    // 2. 提取堆顶元素并调整堆
    for i := n - 1; i > 0; i-- {
        // 交换堆顶与当前堆的末尾元素
        result[0], result[i] = result[i], result[0]
        // 调整剩余元素为大顶堆
        heapify(result, i, 0)
    }

    return result
}

// 堆调整：将以 rootIndex 为根的子树转为大顶堆
func heapify(arr []int, heapSize, rootIndex int) {
    largest := rootIndex
    leftChild := 2*rootIndex + 1
    rightChild := 2*rootIndex + 2

    // 比较左子节点
    if leftChild < heapSize && arr[leftChild] > arr[largest] {
        largest = leftChild
    }
    // 比较右子节点
    if rightChild < heapSize && arr[rightChild] > arr[largest] {
        largest = rightChild
    }

    // 若最大值不在根节点，交换并递归调整子树
    if largest != rootIndex {
        arr[rootIndex], arr[largest] = arr[largest], arr[rootIndex]
        heapify(arr, heapSize, largest)
    }
}

3、关键优化策略

堆排序的时间复杂度主要由 构建堆 和 堆调整 决定，针对性能瓶颈可进行以下优化：

3.1 迭代式堆调整

基础实现中 heapify 采用递归方式，当堆规模极大时可能触发栈溢出，且递归调用存在函数栈开销。优化方案为将递归改为迭代：

private static void iterativeHeapify(int[] arr, int heapSize, int rootIndex) {
    while (true) {
        int largest = rootIndex;
        int leftChild = 2 * rootIndex + 1;
        int rightChild = 2 * rootIndex + 2;

        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        if (largest == rootIndex) {
            break; // 无需继续调整，退出循环
        }
        // 交换元素
        int temp = arr[rootIndex];
        arr[rootIndex] = arr[largest];
        arr[largest] = temp;

        rootIndex = largest; // 继续调整子树
    }
}

3.2 混合排序

当堆调整后剩余元素规模较小时（通常 n ≤ 16），堆排序的常数项开销（如循环、索引计算）超过插入排序的优势。优化方案为：当剩余元素数量小于阈值时，切换为插入排序，减少整体执行时间。

4、复杂度与特性分析

5、与其他基础排序算法的对比

关键结论：

• 堆排序的核心优势是复杂度稳定，无最坏情况退化，适合对排序稳定性要求高（指时间复杂度稳定）的场景；

• 与快速排序相比，堆排序缓存友好性较差（堆操作涉及的节点在内存中不连续），但在数据量极大时，堆排序的稳定性更可靠；

• 与归并排序相比，堆排序无需额外存储空间，适合内存受限场景，但不支持稳定排序。