C++如何实现堆排序
这篇文章主要介绍“C++如何实现堆排序”，在日常操作中，相信很多人在C++如何实现堆排序问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++如何实现堆排序”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
概述：
堆排序是利用构建“堆”的方法确定具有最大值的数据元素，并把该元素与最后位置上的元素交换。可将任意一个由n个数据元素构成的序列按照（a1，a2，...，an），按照从左到右的顺序按层排列构成一棵与该序列对应的完全二叉树。
一棵完全二叉树是一个堆，当且仅当完全二叉树的每棵子树的根值ai≥其左子树的根值a2i，同时ai≥其右子树的根值a 2i+1 (1实现堆排序需要实现两个问题：
如何由无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？
思路：
堆排序算法思想：1、从最后一个非叶子节点逐步到树根，对每个子树进行调整堆。
2、重复n-1次如下处理：将堆的根与最后一个叶子交换，除最后一个叶子之外剩余部分再调整为堆。
调整堆算法思想：1、将树根与其左右子树根值最大者交换；（大顶堆）
2、对交换后的左（或右）子树重复过程1，直到左（或右）子树为堆。
时间复杂度：O(nlogn)
代码：
调整堆算法：
voidHeapAdjust(int*array,inti,intlength){//调整堆intleftChild=2*i+1;//定义左右孩子intrightChild=2*i+2;intmax=i;//初始化，假设左右孩子的双亲节点就是最大值if(leftChildarray[max]){max=leftChild;}if(rightChildarray[max]){max=rightChild;}if(max!=i){//若最大值不是双亲节点，则交换值swap(array[max],array[i]);HeapAdjust(array,max,length);//递归，使其子树也为堆}}
堆排序算法：
voidHeapSort(int*array,intlength){//堆排序for(inti=length/2-1;i>=0;i--){//从最后一个非叶子节点开始向上遍历，建立堆HeapAdjust(array,i,length);}for(intj=length-1;j>0;j--){//调整堆，此处不需要j=0swap(array[0],array[j]);HeapAdjust(array,0,j);//因为每交换一次之后，就把最大值拿出(不再参与调整堆)，第三个参数应该写j而不是lengthPrint(array,length);}}
完整代码：
//堆排序#includeusingnamespacestd;voidPrint(intarray[],intlength){//每执行一次打印一次序列for(inti=0;iarray[max]){max=leftChild;}if(rightChildarray[max]){max=rightChild;}if(max!=i){//若最大值不是双亲节点，则交换值swap(array[max],array[i]);HeapAdjust(array,max,length);//递归，使其子树也为堆}}voidHeapSort(int*array,intlength){//堆排序for(inti=length/2-1;i>=0;i--){//从最后一个非叶子节点开始向上遍历，建立堆HeapAdjust(array,i,length);}for(intj=length-1;j>0;j--){//调整堆，此处不需要j=0swap(array[0],array[j]);HeapAdjust(array,0,j);//因为每交换一次之后，就把最大值拿出(不再参与调整堆)，第三个参数应该写j而不是lengthPrint(array,length);}}intmain(){intarray[]={49,38,65,97,76,13,27,49};intlength=sizeof(array)/sizeof(*array);Print(array,length);//先打印原始序列HeapSort(array,length);return0;}
运行示例：
第一行是原始序列，第二到八行分别是经过7次调整堆所得到的序列。
到此，关于“C++如何实现堆排序”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注恰卡编程网网站，小编会继续努力为大家带来更多实用的文章！
