请选择 进入手机版 | 继续访问电脑版

堆排序 + C语言实现

[复制链接]
小甜心 发表于 2020-12-31 18:08:21 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
堆排序
首先说一下堆,它可以被视为完全二叉树,大(小)根堆即任意非根结点的值都小(大)于即是其双亲结点的值。
基本原理:创建大(小)根堆,依次将堆顶元素与堆底元素进行互换,每次互换完成后堆大小减一,重复此过程,直到数组中只剩下一个元素为止。
算法框架如下
  1. void HeapSort(int *A,int n)        //此处预留A[0],所以参数n应为数组A的大小减1{    BuildMaxHeap(A,n);        //首先创建大根堆    for (int i = n;i > 1;--i)    {        swap(&A[i],&A[1]);        HeapAdjust(A,1,i - 1);    }        //每次循环将当前堆顶元素与堆底元素互换,此时堆性质大概会被粉碎,            //调用HeapAdjust方法将堆重新调解有序}
复制代码
此处将A数组的第一个元素(A[0])预留出来,后续有用
也就是说n个元素需要一个大小为n+1的数组
创建大根堆:
  1. void BuildMaxHeap(int *A,int n){    for (int i = n / 2;i > 0;--i)    {        HeapAdjust(A,i,n);    }}
复制代码
很简朴的几行代码,原理也很简朴
学习过二叉树,我们知道:对于一个完全二叉树来说,它的最后一个节点是第 n/2(向下取整) 个节点的子节点。
好比说一个完全二叉树有五个节点,那么它的第五个节点就是第二个节点的子节点。
对以此节点为根的子树进行调解,使该子树成为堆。今后依次向前对各节点进行调解(n/2(向下取整)到1),直到根节点,使整个树成为堆。
堆调解
  1. void HeapAdjust(int *A,int i,int n){    A[0] = A[i];        //将待调解节点值存放至A[0]中    for(int j = i * 2;j  A[0])        {            A[i] = A[j];            i = j;        }        //如果i的孩子节点比j大,A[j]放到A[i]的位置上                //并将j作为下一个调解的节点,向下继承调解        else break;        //如果堆性质未被粉碎则直接跳出循环    }    A[i] = A[0];        //最终将A[i]放到它该在的地方(如堆性质未被粉碎则还在原位置)}
复制代码
堆排序,说白了就是将堆顶元素(最大元素)输出,将堆中的剩余元素重新调解有序,再将堆顶元素(此时为第二大元素)输出,循环此过程
如果创建的是大根堆,执行完堆排序后最终元素升序分列,小根堆降序
补上swap函数
  1. void swap(int *x,int *y){    int temp = *y;    *y = *x;    *x = temp;}
复制代码
来源:https://blog.csdn.net/Gnef_Epic/article/details/111997891
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )