精妙的堆排序算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了精妙的堆排序算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2404字，纯文字阅读大概需要4分钟。

内容图文

堆排序是一种不稳定的选择排序法，但在需要排的数的基数很大的时候效率相对较高

堆排序是一种以二叉树结构为思维框架的排序算法

想搞懂堆排序必须先明白什么是二叉树，二叉树应该怎么画，二叉树中每个点与数组每个数下标的对应关系
还有什么是 大/小顶堆，还有堆排序的排序思路

排序思路：
先对二叉树进行排序，使其满足 大/小 顶堆，然后将根节点的数与数组中最后一个数进行交换，并把交换后的最后一个数固定在那里，之后再对除那个数以外的数进行堆排序，不断重复上面的过程直至所有数都被固定，此时堆排序完成

#include<stdio.h>       //从小到大排序，应用大顶堆

 #define LEN 12//排序的数字个数

 void print_array(int *array, int length) //打印数组
 {
     int index = 0;
     printf("array:\n");
     for(; index < length; index++){
         printf(" %d,", *(array+index));
     }
     printf("\n\n");
 }

 void _heapSort(int *array, int i, int length) //堆化函数
 {
     int child, tmp;
     //这个是改变了哪个节点，就从该节点开始对以该节点为根节点的子树进行排序
     for (; 2*i + 1 < length; i = child){//依次到它的子树的子树。。。。从那个节点到其的子节点不断交换
         child = 2*i + 1;//左子节点
         if ((child +1  < length)/*为了防止此叶的父节点只有一个子节点*/ && (array[child+1] > array[child])) child++;//选个最大的孩子节点
         if (array[i] < array[child]){//最大子节点和父节点进行交互
             tmp = array[i];
             array[i] = array[child];
             array[child] = tmp;
         }else break;//不用交换或往后没有子节点则退出
     }
 }

 void heapSort(int *array, int length)
 {
     int i, tmp;

     if (length <= 1) return;//如果元素小于等于1，则退出

     //这一步是先把元素都堆化好，后面的话 哪个节点修改过，就从哪个节点开始对以它为根节点的子树进行堆化
     for (i = length/2 - 1; i >= 0; i--)  _heapSort(array, i, length);//从最后一个非叶子节点（双亲节点）开始堆化，一直到根节点

     // 先抽取到根节点，与最后一个叶互换位置并定住。然后再对元素进行堆化，然后又抽取根节点，再对元素进行堆化...依次循环
     for (i = 0; i < length; i++ ){
         tmp = array[0];
         array[0] = array[length-i-1];
         array[length -i-1] = tmp;
         _heapSort(array, 0, length-1-i);//堆化子树
     }
 }

 int main(void)
 {
     int array[LEN] = {2, 1, 4, 0, 12, 520, 2, 9, 5, 3, 13, 14};
     print_array(array, LEN);//打印排序前的数组
     heapSort(array, LEN);//堆排序
     print_array(array, LEN);//打印排序后的数组（从小到大）
     return 0;
 }




如果想要排从大到小，则把21,22行修改为：
21：array[child+1] < array[child]
22：if(array[i]>array[child])

步骤总结：

1. 找出最后一个双亲节点，先把整个二叉树排成一个堆
2. 把根节点与最后一个叶互换并固定
3. 从根开始再次把剩余未固定的部分排列成堆
4. 不断循环2.3.步直至退出

代码参考自：https://blog.csdn.net/YuZhiHui_No1/article/details/44258297
（代码中有补充别的说明）

内容总结

以上是互联网集市为您收集整理的精妙的堆排序算法全部内容，希望文章能够帮你解决精妙的堆排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---