|
>
上节课讲了关于C语言堆排序的介绍，本节来说一说关于堆排序如何应用，举出一个详细的例子来实践！
你可能不知道的C语言排序神器：堆排序
概念回顾：
堆排序是一种基于堆这种数据结构的排序算法，它的时间复杂度为
空间复杂度为
是一种原地排序和不稳定排序的算法。堆排序的一个典型的应用场景是优先队列，它可以用于实现高效的任务调度等问题。堆排序的实现需要用到指针，指针是一种存储地址的变量，它可以用来访问和修改数组中的元素。
堆排序的应用案例
堆排序的一个典型的应用场景是优先队列。优先队列是一种特殊的队列，它的每个元素都有一个优先级，出队的时候总是按照优先级从高到低的顺序出队。优先队列可以用堆来实现，具体的做法是：
入队：把新元素放到堆的末尾，然后向上调整堆的结构，使其满足堆的性质。
出队：把堆顶元素和堆尾元素交换，然后缩小堆的大小，再向下调整堆的结构，使其满足堆的性质，最后返回堆顶元素。
优先队列的一个应用例子是任务调度。假设有一些任务需要在一台计算机上执行，每个任务都有一个优先级和一个执行时间，计算机每次只能执行一个任务，而且不能中断正在执行的任务。我们希望按照优先级从高到低的顺序执行任务，以尽快完成所有的任务。这个问题可以用优先队列来解决，具体的做法是：
1、把所有的任务放入一个大顶堆中，以优先级作为排序的依据。
2、每次从堆中取出优先级最高的任务，执行该任务，然后从堆中删除该任务。
3、重复上述步骤，直到堆为空。
这样，我们就可以保证每次执行的任务都是优先级最高的，从而达到最优的任务调度效果
程序
#include <stdio.h>#include <stdlib.h>
// 定义一个交换函数，用于交换两个整数的值void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp;}// 定义一个调整函数，用于将一个数组调整为一个大顶堆void adjust(int *arr, int len, int index) { // 计算左右子节点的索引 int left = 2 * index + 1; int right = 2 * index + 2; // 初始化最大值的索引为当前节点的索引 int max = index; // 如果左子节点存在，并且左子节点的值大于当前节点的值，更新最大值的索引为左子节点的索引 if (left < len && arr[left] > arr[max]) { max = left; } // 如果右子节点存在，并且右子节点的值大于当前节点的值，更新最大值的索引为右子节点的索引 if (right < len && arr[right] > arr[max]) { max = right; } // 如果最大值的索引不等于当前节点的索引，说明当前节点不满足大顶堆的性质，需要交换当前节点和最大值节点的值，并对最大值节点进行递归调整 if (max != index) { swap(&arr[max], &arr[index]); adjust(arr, len, max); }}// 定义一个堆排序函数，用于对一个数组进行升序排列void heapSort(int *arr, int len) { // 从最后一个非叶子节点开始，从右到左，从下到上，对每个节点进行调整，使整个数组成为一个大顶堆 for (int i = len / 2 - 1; i >= 0; i--) { adjust(arr, len, i); } // 从最后一个元素开始，将堆顶的元素（最大值）与堆尾的元素交换，然后缩小堆的大小，对堆顶的元素进行调整，重复这个过程，直到堆的大小为1 for (int j = len - 1; j > 0; j--) { swap(&arr[0], &arr[j]); adjust(arr, j, 0); }}// 定义一个打印函数，用于打印一个数组的元素void printArray(int *arr, int len) { printf("["); for (int i = 0; i < len; i++) { printf("%d", arr); if (i < len - 1) { printf(", "); } } printf("]\n");}
// 定义一个主函数，用于测试int main() { // 创建一个测试用的数组 int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1}; // 获取数组的长度 int len = sizeof(arr) / sizeof(arr[0]); // 打印原始数组 printf("原始数组是：\n"); printArray(arr, len); // 调用堆排序函数，对数组进行升序排列 heapSort(arr, len); // 打印排序后的数组 printf("排序后的数组是：\n"); printArray(arr, len); // 返回0，表示程序正常结束 return 0;}
运行调试
运行VC6.0，输入原始数组：【9，8，7，6，5，4，3，2，1】
经过堆排序运算结果：【1，2，3，4，5，6，7，8，9】
堆排序的缺点是：
- 它是一种不稳定的排序算法，即相同的元素在排序后可能会改变原来的相对顺序；
- 它的数据交换次数较多，会影响缓存的命中率，降低排序的性能；
堆排序适用于以下的场景：
- 数据量较大，且需要频繁地找出最大值或最小值的问题，比如优先队列、任务调度、中位数、前K大等；
- 数据量较小，且对稳定性要求不高的问题，比如一些简单的排序问题；
堆排序不适用于以下的场景：
- 数据量较大，且对稳定性要求高的问题，比如一些涉及到人员信息或者业务逻辑的排序问题；
- 数据量较小，且对时间效率要求高的问题，比如一些实时性较强的排序问题；
觉得有用的话可以转发给你身边需要的朋友！非常感谢！！！
点赞加关注，学习不迷路
微信公众号｜工控小新
EPLAN电气绘图、TIA博图基础 、CAD、C语言教学、单片机基础、三菱PLC ... 每日持续更新中
发现“分享”和“赞”了吗，戳我看看吧
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
