古之立大事者，不惟有超世之才，亦必有坚忍不拔之志。——苏轼
本篇内容简介：一、排序算法-->二、问题呈现-->三、源码实现-->四、输出结果展示-->五、堆排序gif动画-->六、流程分析
磊C语言100题练习专栏计划：目的：巩固练习C语言，增强上机、动手实践能力，交流学习！前期尽量每天更新一题，之后题量随时间的增加会有所增加。中间也会插入一些算法的问题，文章内容也会不断打磨优化，争取做到好、然后更好！
C语言100题练习计划——堆排序
一、堆排序算法
1. 基本思想2. 平均时间复杂度3.gif演示4. 优缺点5. 算法原理步骤 二、问题呈现三、源码实现(+注释)四、输出结果展示
1.输出结果2.输出结果(图示版) 五、堆排序gif动画六、流程分析
1.读题2.构思
一、堆排序算法堆排序(Heap sort)的介绍
堆排序可以看作是一种利用堆的概念来排序的选择排序。
分为两种方法：
最大堆(大顶堆)：每个节点的值都大于或等于其子节点的值，在堆排序算法中一般用于升序排列；最小堆(小顶堆)：每个节点的值都小于或等于其子节点的值，在堆排序算法中一般用于降序排列；
如图：
最大堆(大顶堆)：
最小堆(小顶堆)：
以大根堆来说：
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
2. 平均时间复杂度整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成
Ο(n*logn)
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为n * logn。所以堆排序时间复杂度一般认为就是O(n * logn)。
3.gif演示 4. 优缺点空间复杂度为常数：O(1)
优点：效率高，最节省空间
排序算法中相比较而言，只需要O(1)的辅助空间，占空间确实小。
缺点：难维护，实际应用性较差，不稳定
5. 算法原理步骤如果应用时在数据更新十分不频繁的时候，用到堆排序还是不错的。
过程步骤：
① 将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
一般大顶堆用于升序，小顶堆用于降序
② 将堆顶元素与末尾元素进行交换，使末尾元素最大。
③ 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾(第二大)元素，反复执行调整+交换步骤，直到整个序列有序。
二、问题呈现以最大堆(大顶堆)相关，升序问题为例：
Problem Description
给定数组元素为：10 13 20 22 30 31 35 46 60 65 65 77 81 91 96。使用堆排序对其进行升序排序。
Input
无
Output
数组元升序排序后的结果
Sample Input
无
Sample Output
10 13 20 22 30 31 35 46 60 65 65 77 81 91 96三、源码实现(+注释)
#include#include //交换函数 交换元素的位置 void swap(int *a, int *b) { int temp = *b; *b = *a; *a = temp; } //调整堆 最大堆 调整堆函数 void Max_heapify(int arr[], int start, int end) { // 建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <= end) { //若子节点指标在范围内才做比较 if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点的大小 选择最大的 son++; if (arr[dad] > arr[son]) // 如果父节点大于子节点代表调整完毕 直接跳出函数 return; else { // 否则交换功夫之内容再继续子节点和子子(孙)结点比较 swap(&arr[dad], &arr[son]); dad = son; son = dad * 2 + 1; } } } //堆排序 void Heap_sort(int arr[], int len) { int i; //初始化 i从最后一个父节点开始调整 for (i = len / 2 - 1; i >= 0; i--) Max_heapify(arr, i, len - 1); //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕 for (i = len - 1; i > 0; i--) { swap(&arr[0], &arr[i]); //交换位置 Max_heapify(arr, 0, i - 1);//调整堆 } } int main() { int a[] = {91,60,96,13,35,65,46,65,10,30,20,31,77,81,22};//数组初始化 int len = (int)sizeof(a)/sizeof(*a);//数组长度 //调用堆排排序函数进行排序 Heap_sort(a,len); int i; //循环输出排序后的结果： for (i = 0; i < len; i++) printf("%d ", a[i]); return 0;//返回0，代表程序执行至此结束 }
四、输出结果展示 1.输出结果
10 13 20 22 30 31 35 46 60 65 65 77 81 91 96 -------------------------------- Process exited after 0.1898 seconds with return value 0 请按任意键继续. . .2.输出结果(图示版)
五、堆排序gif动画 六、流程分析 1.读题
给定数组元素为：3,44,38,5,47,15,36,26,27,2,46,4,19,50,48。使用快速排序对其进行升序排序。关键点 ①给定元素内容 ②堆排序 ③升序排序
2.构思①根据第一个关键点给定元素内容，可以先定义一个整数类型的数组对其进行存储，方便后续使用循环对其进行操作。
②第二个关键点就是堆排序，使用堆排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成， 详细来看就是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了 。
③第三个关键点升序排序，升序排序，我们一般用大根堆，借助大根堆特点：每个节点的值都大于或等于其子节点的值，进行比较，交换，排序即可。
3.编程
把你所思所想，以代码的形式，写出来。
ps：这道题的方法，本文虽然只写出这一种，但是思路方法其实不止这一种，其它的方法可自行尝试一下。
作者:Code_流苏（一个喜欢古诗词和编程的Coder）
★喜欢的话，还请多多点赞与关注！ 感谢支持！
C语言100题练习专栏计划持续进行，欢迎评论交流学习！
