理解堆排序的本质：建堆 + 交换 + 装箱+重复
什么是堆排序（Heap Sort）？堆排序是一种基于堆这种特殊结构的选择排序。常见于不允许使用额外空间（in-place）的场景，且性能稳定为 O(n log n)。
它的过程可以非常简单地概括为四步：
我的理解（堆排序核心步骤）
[*]建最大堆（或最小堆）
[*]所有数据先变成一个“堆”（最大堆适用于升序）
[*]交换顶底元素
[*]堆顶是最大元素，把它跟堆尾交换，最大元素被“摘出来了”
[*]干掉底部元素
[*]把末尾元素从“堆”里踢出去，相当于缩小堆的尺寸，代表它已经排序完了
[*]重复前面步骤
[*]对剩下的堆重新调整（堆化），最大值又回到堆顶，继续摘
一直重复，直到堆中只剩一个元素——排序完成！
图示演示（以最大堆升序为例）
初始数组：
步骤如下：
Step 1: 构建最大堆
Step 2: 交换堆顶与堆尾 →
剔除堆尾（10） → 只对前 4 个元素堆化
Step 3: 堆化 →
Step 4: 交换堆顶与堆尾 →
剔除 5 → 堆化前 3 个
...
最终结果：``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, arr) = (arr, arr);
// 调整剩余部分为最大堆（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 > arr)
largest = left;
if (right < heapSize && arr > arr)
largest = right;
if (largest != root)
{
(arr, arr) = (arr, arr);
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, arr = arr, arr // 交换堆顶和堆尾
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 > arr {
largest = left
}
if right < heapSize && arr > arr {
largest = right
}
if largest != root {
arr, arr = arr, arr
heapify(arr, heapSize, largest)
}
}
func main() {
arr := []int{4, 10, 3, 5, 1}
fmt.Println("原始数组:", arr)
heapSort(arr)
fmt.Println("排序后:", arr)
}总结一句话：
堆排序本质上是一个“摘最大值放到底部 + 重建最大堆”的过程，构造最大堆就是在为这个摘果子流程做准备。
延伸阅读
[*]如果你用的是最小堆，也可以实现降序排序
[*]PriorityQueue 是堆结构的实际应用
[*]实时 TopK、图论中的 Dijkstra、调度算法都基于堆
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]