八大排序算法~堆排序
1，思想：就是利用堆数据结构特点进行排序【堆结构特点~完全二叉树，而咱排序主要是利用（大根堆或者小根堆特点进行排序）】
【小根堆】：每一个父结点的值都比子结点小，因为每个父节点都比子结点小，咱知道 小根堆的最小值就在根结点；
【大根堆】：每一个父结点的值都比子结点大，因为每个父节点都比子结点大，咱知道 大根堆的最大值就在根结点；
（补充一下，因为小根堆要求只是父结点大于子结点，没有要求左右结点的大小关系噢，大根堆也是哈，咱对左右结点大小关系没有关系哈）
2，接下来，咱以大根堆排序为例，讲述好堆排序过程：
我觉得它的思想有些类似于咱总结的“冒泡思想”~
冒泡思想~（从小到大排序哈）【后座就认为是后边哈，没有啥特别，叫后座主要是为了强调后边啦】
冒泡排序思想：从第一个数开始找，要把大数“排除在外”~为大数找后座。（从小到大排序哈） 外层循环~需要放后的大数个数； 内循环~从第一个数拿起与后面位置的数两两比较，实力强的占的位置靠后。
堆排序思想~（从小到大排序哈）~刚好借助大根堆的特点进行排序
堆排序（借助大根堆，实现从小到大排序）思想： 咱对n个结点构建成一个大根堆，然后取根结点（最大值“排除在外”~放到后座上最后一个位置）， 咱在对剩余的n-1个结点构建成一个新的大根堆，然后又取根结点放到后座上倒数第二个位置， 然后对剩余的n-2个结点构建成一个新的大根堆，然后又取根结点放到后座上倒数第三个位置， ........ 直到剩下一个结点结束。//过程：（1）建立成大根堆，（2）for循环（从 i=最后一个结点位置开始直到i=第一个结点 结束）：取根结点放于后座~即进行交换，根结点与后座最后一个位置进行交换，然后重构成新的大根堆，再取根节点跟后座倒数第二个位置交换，然后重新构建新的大根堆，然后。。。ps：本菜菜小白想请问，为什么要先初始化堆，然后for循环 取根结点，重新调整成堆；为什么不能for循环 调整成堆，然后取根结点，然再次调整成堆，然后再取根结点，再调整成堆。。。。就是为什么要单独初始化堆，不把它写到循环里？
3，代码：引自~《【算法】排序算法之堆排序》~https://zhuanlan.zhihu.com/p/124885051
【这个 “developer1024 ” 作者大大这篇文章里的动画可以让你秒懂堆排的】
#include <stdio.h> #include <stdlib.h> 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 arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); int i; for (i = 0; i < len; i++) printf("%d ", arr[i]); printf("\n"); return 0; }
