资源描述：
《堆排序的非递归算法分析与java实现》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、堆排序的非递归算法分析与JAVA实现摘要：本文对经典的堆排序非递归算法进行了详细的分析，并用JAVA实现。用过该问题的JAVA实现，可使学习者清晰的观测到解决该问题的全过程。关键词：关键词：堆排序；算法；非递归；JAVA中图分类号：TP312文献标识码：A：1.引言n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质：ki<=k(2i）且ki<=k(2i+1)(1≤i≤n），当然，这是小根堆，大根堆则换成>=号。若将此序列所存储的向量arr[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均
2、不大于(或不小于)其左右孩子(若存在)结点的关键字。堆的这个性质使得可以迅速定位在一个序列之中的最小(大)的元素。堆排序就是利用堆的这些性质进行排序。在下述堆排序算法中，使用的是最大堆。2.堆排序递归算法分析1)得到当前序列的最大的元素；2)把这个元素和最后一个元素进行交换,这样当前的最大元素就放在了序列的最后,而原先的最后一个元素放到了序列的最前面；3)这样的交换可能会破坏堆序列的性质,因此需要对序列进行调整,使之满足于上面堆的性质.重复上面的过程,直到序列调整完毕为止。3.堆排序非递归算法分析3.1保持堆的性质maxheapsort是对最大堆进行操作的重要子程序。其输入一个数
3、组arr和下标i。maxheapsort让arr[i]在最大堆中“下降”，使以i为根的子树成为最大堆。如下：arr[1],…,arr[10]={50,10,90,60,70,40,80,30,20},i=2，调用maxheap(int[]arr,inti,intnum)函数实现3.2建堆staticvoidbuildmaxheap(int[]arr,intnumber){num=number;for(inti=number/2;i>0;i--){maxheap(arr,i,num);}}利用循环体for(inti=number/2;i>0;i--)使以i为根的子树成为
4、最大堆。3.3进行堆排序如果数组R中存放了堆（n为排序整数个数），那么R[1]是最大的记录，将R[1]和R[n]的交换，使得最大记录放在R[n]的位置。然后对R[1]，……，R[n-1]进行调整，使它们构成一个堆。调整后，R[1]是R[1]，R[2]，……，R[n-1]中最大的。然后再交换R[1]与R[n-1]，使R[n-1]中放入次最大的记录。再对R[1]，R[2]，……，R[n-2]进行调整，使之成为新堆，再进行类似的交换和调整，反复进行，直到调整范围只剩下一个记录R[1]为止。此时R[1]是n个记录中最小的，且数组R[n]中的记录已经按从小到大排列了。如下：arr[1],…
5、,arr[10]={50,10,90,60,70,40,80,30,20}，调用堆排序实现4.JAVA实现4.1编程如下：importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.Scanner;publicclassheapsort{staticinttmp,num;staticvoidHeapSort(int[]arr,intnumber){//堆排序算法inti;num=number;buildmaxheap(arr,numbe
6、r);//建立初始堆for(i=number;i>1;i--){tmp=arr[1];arr[1]=arr[i];arr[i]=tmp;//交换值num--;maxheap(arr,1,num);}//调整堆，使节点1成为前num节点最大节点}staticvoidbuildmaxheap(int[]arr,intnumber){//建立初始堆num=number;//使每个节点成为平凡最大堆的根for(inti=number/2;i>0;i--){maxheap(arr,i,num);}}staticvoidmaxheap(int[]arr,inti,intnum){
7、intj=i,largest;arr[l]>arr[j]){largest=l;}if(r<=numarr[r]>arr[largest]){largest=r;}if(largest!=j){tmp=arr[j];arr[j]=arr[largest];arr[largest]=tmp;j=largest;}else{break;}}}publicstaticvoidmain(String[]args)thro;System.out.println("请输入个
