1. 代码结构概述

• 核心功能：将数组中的元素按照升序排列。
• 主要步骤：
  1. 构建最大堆：将输入数组组织成最大堆（每个节点的值都大于或等于其子节点）。
  2. 堆排序：每次将堆顶（最大值）移到数组末尾，然后调整剩下的部分为最

2. 函数解析

(1) refresh 函数

作用：从指定节点开始调整堆，使其满足最大堆的性质。

void refresh(int array[], int start, int range) {int largest = start;           // 当前节点位置while (largest * 2 + 1 < range) { // 当存在子节点int left = largest * 2 + 1;   // 左子节点int right = largest * 2 + 2;  // 右子节点int maxChild = left;          // 假设左子节点是最大的// 如果右子节点存在且值更大，则更新最大子节点if (right < range && array[right] > array[left]) {maxChild = right;}// 如果当前节点比最大子节点还大，退出调整if (array[largest] >= array[maxChild]) {break;}// 交换当前节点和最大子节点int temp = array[largest];array[largest] = array[maxChild];array[maxChild] = temp;// 更新节点位置，继续向下调整largest = maxChild;}
}

---

(2) Heap_sort 函数

作用：实现堆排序的完整流程。

void Heap_sort(int array[], int size) {// (1) 构建最大堆for (int i = size / 2 - 1; i >= 0; i--) { // 从最后一个非叶节点开始refresh(array, i, size);             // 调整堆结构}// (2) 排序for (int i = size - 1; i > 0; i--) {    // 从数组末尾逐步移除最大元素// 将堆顶（最大值）与当前范围的最后一个元素交换int temp = array[0];array[0] = array[i];array[i] = temp;// 调整剩余部分为最大堆refresh(array, 0, i);}
}

---

3. 主函数 main

作用：测试堆排序算法。

int main(void) {int array[maxsize] = {3, 5, 7, 9, 1, 4, 2, 6, 8, 0}; // 初始化数组Heap_sort(array, maxsize);                          // 调用堆排序// 输出排序后的数组for (int i = 0; i < maxsize; i++) {printf("%d ", array[i]);}return 0;
}

---

4. 运行过程

假设输入数组为 {3, 5, 7, 9, 1, 4, 2, 6, 8, 0}：

(1) 构建最大堆

通过从最后一个非叶节点向上调整，最终堆变成：

          9/     \8       7/ \     / \6   5   4   2/3

数组形式为：{9, 8, 7, 6, 5, 4, 2, 3, 1, 0}。

---

(2) 排序

1. 交换堆顶和数组最后一个元素：

   • 结果：{0, 8, 7, 6, 5, 4, 2, 3, 1, 9}。
   • 调整剩余部分为堆：

             8/     \6       7/ \     / \3   5   4   2/
     0
     

     数组：{8, 6, 7, 3, 5, 4, 2, 0, 1, 9}。

2. 重复上述过程，每次将堆顶移到未排序部分的末尾，并调整剩余堆。

最终结果：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。

---

5. 时间复杂度

• 建堆：O(n)。
• 排序：O(n log n)（每次调整堆的复杂度为 O(log n)，需要调整 n 次）。
• 总复杂度：O(n log n)。

---

6. 空间复杂度

堆排序是原地排序算法，不需要额外的数组存储数据，空间复杂度为 O(1)。

---

7. 总结

这段代码实现了标准的堆排序算法，具有以下特点：

• 稳定性：堆排序是不稳定排序（相同值的元素相对顺序可能改变）。
• 效率：适合对大规模数据进行排序。
• 应用场景：适用于对内存有限的环境中进行高效排序。