理解堆排序的本质：建堆 + 交换 + 装箱+重复

 什么是堆排序（Heap Sort）？

堆排序是一种基于堆这种特殊结构的选择排序。常见于不允许使用额外空间（in-place）的场景，且性能稳定为 O(n log n)。
它的过程可以非常简单地概括为四步：
我的理解（堆排序核心步骤）

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

一直重复，直到堆中只剩一个元素——排序完成！
图示演示（以最大堆升序为例）

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

1. Step 1: 构建最大堆
2.         [10, 5, 3, 4, 1]
4. Step 2: 交换堆顶与堆尾 → [1, 5, 3, 4, 10]
5.         剔除堆尾（10） → 只对前 4 个元素堆化
7. Step 3: 堆化 → [5, 4, 3, 1, 10]
9. Step 4: 交换堆顶与堆尾 → [1, 4, 3, 5, 10]
10.         剔除 5 → 堆化前 3 个
12. ...
14. 最终结果：`[1, 3, 4, 5, 10]`

复制代码

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

1. public class HeapSorter
2. {
3.     public static void HeapSort(int[] arr)
4.     {
5.         int n = arr.Length;
7.         // 1. 建最大堆
8.         for (int i = n / 2 - 1; i >= 0; i--)
9.             Heapify(arr, n, i);
11.         // 2. 顶底交换 + 3. 干掉底部元素 + 4. 重复
12.         for (int i = n - 1; i > 0; i--)
13.         {
14.             // 交换堆顶和堆尾
15.             (arr[0], arr[i]) = (arr[i], arr[0]);
17.             // 调整剩余部分为最大堆（i 是新堆的大小）
18.             Heapify(arr, i, 0);
19.         }
20.     }
22.     // 调整以 root 为根的子树，使其成为最大堆
23.     private static void Heapify(int[] arr, int heapSize, int root)
24.     {
25.         int largest = root;
26.         int left = 2 * root + 1;
27.         int right = 2 * root + 2;
29.         if (left < heapSize && arr[left] > arr[largest])
30.             largest = left;
31.         if (right < heapSize && arr[right] > arr[largest])
32.             largest = right;
34.         if (largest != root)
35.         {
36.             (arr[root], arr[largest]) = (arr[largest], arr[root]);
37.             Heapify(arr, heapSize, largest);
38.         }
39.     }
40. }

复制代码

Go 实现（同样思路）

1. package main
3. import (
4.     "fmt"
5. )
7. func heapSort(arr []int) {
8.     n := len(arr)
10.     // 1. 建最大堆
11.     for i := n/2 - 1; i >= 0; i-- {
12.         heapify(arr, n, i)
13.     }
15.     // 2. 顶底交换 + 3. 干掉底部 + 4. 重复
16.     for i := n - 1; i > 0; i-- {
17.         arr[0], arr[i] = arr[i], arr[0] // 交换堆顶和堆尾
18.         heapify(arr, i, 0)              // 堆化剩下的部分
19.     }
20. }
22. func heapify(arr []int, heapSize int, root int) {
23.     largest := root
24.     left := 2*root + 1
25.     right := 2*root + 2
27.     if left < heapSize && arr[left] > arr[largest] {
28.         largest = left
29.     }
31.     if right < heapSize && arr[right] > arr[largest] {
32.         largest = right
33.     }
35.     if largest != root {
36.         arr[root], arr[largest] = arr[largest], arr[root]
37.         heapify(arr, heapSize, largest)
38.     }
39. }
41. func main() {
42.     arr := []int{4, 10, 3, 5, 1}
43.     fmt.Println("原始数组:", arr)
44.     heapSort(arr)
45.     fmt.Println("排序后:", arr)
46. }

复制代码

总结一句话：

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

• 如果你用的是最小堆，也可以实现降序排序
  
• PriorityQueue 是堆结构的实际应用
  
• 实时 TopK、图论中的 Dijkstra、调度算法都基于堆
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！