資源描述：
《堆排序的非遞歸算法分析與java實現(xiàn)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、堆排序的非遞歸算法分析與JAVA實現(xiàn)摘要：本文對經(jīng)典的堆排序非遞歸算法進行了詳細的分析，并用JAVA實現(xiàn)。用過該問題的JAVA實現(xiàn)，可使學習者清晰的觀測到解決該問題的全過程。關(guān)鍵詞：關(guān)鍵詞：堆排序；算法；非遞歸；JAVA中圖分類號：TP312文獻標識碼：A：1.引言n個關(guān)鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(zhì)：ki<=k(2i）且ki<=k(2i+1)(1≤i≤n），當然，這是小根堆，大根堆則換成>=號。若將此序列所存儲的向量arr[1..n]看做是一棵完全二叉樹的存儲結(jié)構(gòu)，則堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均
2、不大于(或不小于)其左右孩子(若存在)結(jié)點的關(guān)鍵字。堆的這個性質(zhì)使得可以迅速定位在一個序列之中的最小(大)的元素。堆排序就是利用堆的這些性質(zhì)進行排序。在下述堆排序算法中，使用的是最大堆。2.堆排序遞歸算法分析1)得到當前序列的最大的元素；2)把這個元素和最后一個元素進行交換,這樣當前的最大元素就放在了序列的最后,而原先的最后一個元素放到了序列的最前面；3)這樣的交換可能會破壞堆序列的性質(zhì),因此需要對序列進行調(diào)整,使之滿足于上面堆的性質(zhì).重復上面的過程,直到序列調(diào)整完畢為止。3.堆排序非遞歸算法分析3.1保持堆的性質(zhì)maxheapsort是對最大堆進行操作的重要子程序。其輸入一個數(shù)
3、組arr和下標i。maxheapsort讓arr[i]在最大堆中“下降”，使以i為根的子樹成為最大堆。如下：arr[1],…,arr[10]={50,10,90,60,70,40,80,30,20},i=2，調(diào)用maxheap(int[]arr,inti,intnum)函數(shù)實現(xiàn)3.2建堆staticvoidbuildmaxheap(int[]arr,intnumber){num=number;for(inti=number/2;i>0;i--){maxheap(arr,i,num);}}利用循環(huán)體for(inti=number/2;i>0;i--)使以i為根的子樹成為
4、最大堆。3.3進行堆排序如果數(shù)組R中存放了堆（n為排序整數(shù)個數(shù)），那么R[1]是最大的記錄，將R[1]和R[n]的交換，使得最大記錄放在R[n]的位置。然后對R[1]，……，R[n-1]進行調(diào)整，使它們構(gòu)成一個堆。調(diào)整后，R[1]是R[1]，R[2]，……，R[n-1]中最大的。然后再交換R[1]與R[n-1]，使R[n-1]中放入次最大的記錄。再對R[1]，R[2]，……，R[n-2]進行調(diào)整，使之成為新堆，再進行類似的交換和調(diào)整，反復進行，直到調(diào)整范圍只剩下一個記錄R[1]為止。此時R[1]是n個記錄中最小的，且數(shù)組R[n]中的記錄已經(jīng)按從小到大排列了。如下：arr[1],…
5、,arr[10]={50,10,90,60,70,40,80,30,20}，調(diào)用堆排序?qū)崿F(xiàn)4.JAVA實現(xiàn)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);}//調(diào)整堆，使節(jié)點1成為前num節(jié)點最大節(jié)點}staticvoidbuildmaxheap(int[]arr,intnumber){//建立初始堆num=number;//使每個節(jié)點成為平凡最大堆的根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("請輸入個
