堆排序——C语言实现

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. 总结

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

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