【堆排序怎么排】堆排序是一种基于二叉堆数据结构的排序算法，它利用了完全二叉树的特性，通过构建最大堆或最小堆来实现对数组的排序。堆排序的时间复杂度为 O(n log n)，具有较高的效率，尤其适合大规模数据的排序。
一、堆排序的基本原理
堆排序的核心思想是：
1. 构建堆：将待排序的数组构造成一个最大堆（或最小堆）。
2. 交换与调整：将堆顶元素（最大值或最小值）与最后一个元素交换，然后重新调整剩余元素为堆。
3. 重复操作：重复上述步骤，直到整个数组有序。
二、堆排序的步骤总结
| 步骤 | 操作说明 |
| 1 | 构建初始堆：将数组构造成一个最大堆（或最小堆）。 |
| 2 | 交换堆顶元素与最后一个元素，使最大的元素“沉”到末尾。 |
| 3 | 将剩下的元素重新调整为堆（排除已排序的部分）。 |
| 4 | 重复步骤2和3，直到所有元素都排序完成。 |
三、堆排序的实现过程（以最大堆为例）
假设我们有一个无序数组：`[4, 10, 3, 5, 1, 7]`
第一步：构建最大堆
将数组构造成一个最大堆，使得父节点大于子节点：
```
10
/ \
5 7
/ \ /
4 1 3
```
第二步：交换堆顶与最后一个元素
交换 `10` 和 `3`，得到新的数组：`[3, 5, 10, 4, 1, 7]`
此时，最大的元素 `10` 已经被放到最后，不需要再参与后续调整。
第三步：调整剩余部分为堆
将 `[3, 5, 10, 4, 1, 7]` 中的前5个元素重新调整为最大堆：
```
7
/ \
5 3
/ \
4 1
```
第四步：重复交换与调整
继续交换堆顶 `7` 与 `1`，得到：`[1, 5, 3, 4, 7, 10]`
再调整前4个元素为最大堆：
```
5
/ \
4 3
/
1
```
依此类推，直到整个数组有序。
四、堆排序的特点
| 特点 | 描述 |
| 时间复杂度 | O(n log n) |
| 空间复杂度 | O(1)（原地排序） |
| 稳定性 | 不稳定（相同元素可能交换位置） |
| 适用场景 | 大规模数据排序，尤其在内存有限的情况下 |
五、总结
堆排序是一种高效的排序方法，其核心在于利用堆结构进行元素的筛选和调整。虽然它的实现逻辑较为复杂，但一旦掌握，可以在实际应用中发挥重要作用。对于需要高效排序且不占用额外空间的场景，堆排序是一个非常不错的选择。
