堆排序是一种基于堆这种特殊结构的选择排序。常见于不允许使用额外空间（in-place）的场景，且性能稳定为 O(n log n)。

它的过程可以非常简单地概括为四步：

我的理解（堆排序核心步骤）

1. 建最大堆（或最小堆）
2. 所有数据先变成一个“堆”（最大堆适用于升序）
3. 交换顶底元素
4. 堆顶是最大元素，把它跟堆尾交换，最大元素被“摘出来了”
5. 干掉底部元素
6. 把末尾元素从“堆”里踢出去，相当于缩小堆的尺寸，代表它已经排序完了
7. 重复前面步骤
8. 对剩下的堆重新调整（堆化），最大值又回到堆顶，继续摘

一直重复，直到堆中只剩一个元素——排序完成！

图示演示（以最大堆升序为例）

初始数组：[4, 10, 3, 5, 1]
步骤如下：

Step 1: 构建最大堆
        [10, 5, 3, 4, 1]

Step 2: 交换堆顶与堆尾 → [1, 5, 3, 4, 10]
        剔除堆尾（10） → 只对前 4 个元素堆化

Step 3: 堆化 → [5, 4, 3, 1, 10]

Step 4: 交换堆顶与堆尾 → [1, 4, 3, 5, 10]
        剔除 5 → 堆化前 3 个

...

最终结果：`[1, 3, 4, 5, 10]`

C# 实现（按步骤清晰注释）

public class HeapSorter
{
    public static void HeapSort(int[] arr)
    {
        int n = arr.Length;

        // 1. 建最大堆
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, n, i);

        // 2. 顶底交换 + 3. 干掉底部元素 + 4. 重复
        for (int i = n - 1; i > 0; i--)
        {
            // 交换堆顶和堆尾
            (arr[0], arr[i]) = (arr[i], arr[0]);

            // 调整剩余部分为最大堆（i 是新堆的大小）
            Heapify(arr, i, 0);
        }
    }

    // 调整以 root 为根的子树，使其成为最大堆
    private static void Heapify(int[] arr, int heapSize, int root)
    {
        int largest = root;
        int left = 2 * root + 1;
        int right = 2 * root + 2;

        if (left < heapSize && arr[left] > arr[largest])
            largest = left;
        if (right < heapSize && arr[right] > arr[largest])
            largest = right;

        if (largest != root)
        {
            (arr[root], arr[largest]) = (arr[largest], arr[root]);
            Heapify(arr, heapSize, largest);
        }
    }
}

Go 实现（同样思路）

package main

import (
    "fmt"
)

func heapSort(arr []int) {
    n := len(arr)

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

    // 2. 顶底交换 + 3. 干掉底部 + 4. 重复
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0] // 交换堆顶和堆尾
        heapify(arr, i, 0)              // 堆化剩下的部分
    }
}

func heapify(arr []int, heapSize int, root int) {
    largest := root
    left := 2*root + 1
    right := 2*root + 2

    if left < heapSize && arr[left] > arr[largest] {
        largest = left
    }

    if right < heapSize && arr[right] > arr[largest] {
        largest = right
    }

    if largest != root {
        arr[root], arr[largest] = arr[largest], arr[root]
        heapify(arr, heapSize, largest)
    }
}

func main() {
    arr := []int{4, 10, 3, 5, 1}
    fmt.Println("原始数组:", arr)
    heapSort(arr)
    fmt.Println("排序后:", arr)
}

总结一句话：

堆排序本质上是一个“摘最大值放到底部 + 重建最大堆”的过程，构造最大堆就是在为这个摘果子流程做准备。

延伸阅读

如果你用的是最小堆，也可以实现降序排序

PriorityQueue<T> 是堆结构的实际应用

实时 TopK、图论中的 Dijkstra、调度算法都基于堆