每个网站都有服务器吗,淘宝上网站建设是什么,安徽飞亚建设网站,新余网站开发公司一、堆排序算法
基本思想
堆排序是一种比较有效的排序方法#xff0c;其基本思想是#xff1a;
构建最大堆#xff1a;首先将待排序的数组构建成一个最大堆#xff0c;即对于每个非叶子节点#xff0c;它的值都大于或等于其子节点的值。排序#xff1a;然后将堆顶元素…一、堆排序算法
基本思想
堆排序是一种比较有效的排序方法其基本思想是
构建最大堆首先将待排序的数组构建成一个最大堆即对于每个非叶子节点它的值都大于或等于其子节点的值。排序然后将堆顶元素最大值与堆的最后一个元素交换位置将其移出堆并调整剩余元素以保持最大堆的性质。
步骤
构建最大堆从最后一个非叶子节点开始逐个调整子树使之满足最大堆的条件。排序重复以下操作直到堆为空 将堆顶元素最大值与堆的最后一个元素交换位置。重新调整剩余元素以保持最大堆的性质。
示例
假设我们有一个数组 [5, 2, 4, 6, 1, 3]
构建最大堆 [5, 2, 4, 6, 1, 3] - [6, 5, 4, 2, 1, 3]排序 将最大的元素 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);}
}
