当前位置：首页 > article >正文

堆排序——C语言实现

article 2024/12/25 15:21:31

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) 排序

交换堆顶和数组最后一个元素：
- 结果：{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}。
重复上述过程，每次将堆顶移到未排序部分的末尾，并调整剩余堆。

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