您好,登录后才能下订单哦!
这篇文章主要介绍“C++如何实现堆排序”,在日常操作中,相信很多人在C++如何实现堆排序问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C++如何实现堆排序”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!
堆排序是利用构建“堆”的方法确定具有最大值的数据元素,并把该元素与最后位置上的元素交换。可将任意一个由n个数据元素构成的序列按照(a1,a2,...,an),按照从左到右的顺序按层排列构成一棵与该序列对应的完全二叉树。
一棵完全二叉树是一个堆,当且仅当完全二叉树的每棵子树的根值ai≥其左子树的根值a2i,同时ai≥其右子树的根值a 2i+1 (1<i<n/2)。
实现堆排序需要实现两个问题:
如何由无序序列建成一个堆?如何在输出堆顶元素之后,调整剩余元素成为一个新的堆?
堆排序算法思想:1、从最后一个非叶子节点逐步到树根,对每个子树进行调整堆。
2、重复n-1次如下处理:将堆的根与最后一个叶子交换,除最后一个叶子之外剩余部分再调整为堆。
调整堆算法思想:1、将树根与其左右子树根值最大者交换;(大顶堆)
2、对交换后的左(或右)子树重复过程1,直到左(或右)子树为堆。
时间复杂度:O(nlogn)
调整堆算法:
void HeapAdjust(int *array,int i,int length){ //调整堆 int leftChild=2*i+1; //定义左右孩子 int rightChild=2*i+2; int max=i; //初始化,假设左右孩子的双亲节点就是最大值 if(leftChild<length&&array[leftChild]>array[max]){ max=leftChild; } if(rightChild<length&&array[rightChild]>array[max]){ max=rightChild; } if(max!=i){ //若最大值不是双亲节点,则交换值 swap(array[max],array[i]); HeapAdjust(array,max,length); //递归,使其子树也为堆 } }
堆排序算法:
void HeapSort(int *array,int length){ //堆排序 for(int i=length/2-1;i>=0;i--){ //从最后一个非叶子节点开始向上遍历,建立堆 HeapAdjust(array,i,length); } for(int j=length-1;j>0;j--){ //调整堆 ,此处不需要j=0 swap(array[0],array[j]); HeapAdjust(array,0,j); //因为每交换一次之后,就把最大值拿出(不再参与调整堆),第三个参数应该写j而不是length Print(array,length); } }
完整代码:
//堆排序 #include <iostream> using namespace std; void Print(int array[],int length){ //每执行一次打印一次序列 for(int i=0;i<length;i++){ cout<<array[i]<<" "; } cout<<endl; } void HeapAdjust(int *array,int i,int length){ //调整堆 int leftChild=2*i+1; //定义左右孩子 int rightChild=2*i+2; int max=i; //初始化,假设左右孩子的双亲节点就是最大值 if(leftChild<length&&array[leftChild]>array[max]){ max=leftChild; } if(rightChild<length&&array[rightChild]>array[max]){ max=rightChild; } if(max!=i){ //若最大值不是双亲节点,则交换值 swap(array[max],array[i]); HeapAdjust(array,max,length); //递归,使其子树也为堆 } } void HeapSort(int *array,int length){ //堆排序 for(int i=length/2-1;i>=0;i--){ //从最后一个非叶子节点开始向上遍历,建立堆 HeapAdjust(array,i,length); } for(int j=length-1;j>0;j--){ //调整堆 ,此处不需要j=0 swap(array[0],array[j]); HeapAdjust(array,0,j); //因为每交换一次之后,就把最大值拿出(不再参与调整堆),第三个参数应该写j而不是length Print(array,length); } } int main(){ int array[]={49,38,65,97,76,13,27,49}; int length=sizeof(array)/sizeof(*array); Print(array,length); //先打印原始序列 HeapSort(array,length); return 0; }
运行示例:
第一行是原始序列,第二到八行分别是经过7次调整堆所得到的序列。
到此,关于“C++如何实现堆排序”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。