C语言实现排序之堆排序算法

一、堆排序算法

基本思想

堆排序是一种比较有效的排序方法，其基本思想是：

1. 构建最大堆：首先将待排序的数组构建成一个最大堆，即对于每个非叶子节点，它的值都大于或等于其子节点的值。
2. 排序：然后将堆顶元素（最大值）与堆的最后一个元素交换位置，将其移出堆，并调整剩余元素以保持最大堆的性质。

步骤

1. 构建最大堆：从最后一个非叶子节点开始，逐个调整子树，使之满足最大堆的条件。
2. 排序：重复以下操作直到堆为空：
   • 将堆顶元素（最大值）与堆的最后一个元素交换位置。
   • 重新调整剩余元素以保持最大堆的性质。

示例

假设我们有一个数组 [5, 2, 4, 6, 1, 3]：

1. 构建最大堆：
   • [5, 2, 4, 6, 1, 3] -> [6, 5, 4, 2, 1, 3]
2. 排序：
   • 将最大的元素 6 移动到数组的末尾，然后重新调整剩余元素以保持最大堆的性质。
   • 重复此过程，直到所有元素都被排序。

性能分析

• 时间复杂度：O(n log n)，其中 n 是数组中的元素数量。
• 空间复杂度：O(1)（原地排序）。

二、代码

#include <stdlib.h>
#include <stdio.h>
#include <time.h>// 函数声明
int* create_and_generate_random_array(int size);
void print_array(int *array, int size);
void heapify(int *array, int n, int i);
void heap_sort(int *array, int size);
int generate_random_size();int main() {int size = generate_random_size(); // 随机生成数组大小int *array = create_and_generate_random_array(size);if (array == NULL) {// 如果内存分配失败printf("Memory allocation failed\n");free(array);return 1;}// 打印原始数组（如果需要，可以取消注释）// printf("Original array:\n");// print_array(array, size);// 获取开始时间clock_t start_time = clock();// 对数组进行堆排序heap_sort(array, size);// 获取结束时间clock_t end_time = clock();// 计算时间差并转换为毫秒double execution_time = ((double)(end_time - start_time) / CLOCKS_PER_SEC) * 1000;// 打印排序后的数组（如果需要，可以取消注释）// printf("Sorted array:\n");// print_array(array, size);printf("array_size = %d\n", size);// 打印执行时间printf("Execution time: %.2f ms\n", execution_time);// 释放分配的内存free(array);return 0;
}// 生成随机数组大小
int generate_random_size() {srand(time(NULL));return rand() % 9000 + 1000; // 生成1000到9999之间的随机数
}// 创建并生成随机数组
int* create_and_generate_random_array(int size) {int *array = (int *)malloc(sizeof(int) * size);if (array == NULL) {// 如果内存分配失败return NULL;}// 使用当前时间作为随机数种子srand(time(NULL));for (int i = 0; i < size; i++) {array[i] = rand() % 1000; // 生成0到999之间的随机数}return array;
}// 打印数组
void print_array(int *array, int size) {for (int i = 0; i < size; i++) {printf("%d ", array[i]);}printf("\n");
}// 构建最大堆
void heapify(int *array, int n, int i) {int largest = i; // 初始化最大值索引int left = 2 * i + 1; // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点大于根if (left < n && array[left] > array[largest])largest = left;// 如果右子节点大于当前最大值if (right < n && array[right] > array[largest])largest = right;// 如果最大值不是根if (largest != i) {int swap = array[i];array[i] = array[largest];array[largest] = swap;// 递归地堆化受影响的子树heapify(array, n, largest);}
}// 堆排序
void heap_sort(int *array, int size) {// 构建最大堆for (int i = size / 2 - 1; i >= 0; i--)heapify(array, size, i);// 一个接一个从堆顶取出元素for (int i = size - 1; i > 0; i--) {// 将当前根（最大值）移动到数组末尾int temp = array[0];array[0] = array[i];array[i] = temp;// 调整剩余堆，使其成为最大堆heapify(array, i, 0);}
}