内部排序课件.pptVIP

具體做法：把待排序的記錄的關鍵字存放在數組r[1..n]之中，將r看成是一棵完全二叉樹的順序表示，每個結點表示一個記錄，第一個記錄r[1]作為二叉樹的根，以下各記錄r[2...n]依次逐層從左到右順序排列，任意結點r[i]的左孩子是r[2i],右孩子是r[2i+1],雙親是r[?i/2?]。對這棵完全二叉樹進行調整，使各結點的關鍵字值滿足下列條件：r[i].key≥r[2i].key並且r[i].key≥r[2i+1].key(i=1,2,...?n/2?)，滿足這個條件的完全二叉樹為堆。堆是滿足下列性質的數列{r1,r2,…，rn}：或堆的定義:{12,36,27,65,40,34,98,81,73,55,49}例如:是小根堆不是堆(小根堆)(大根堆)rir2ir2i+1若將該數列視作完全二叉樹，則r2i是ri的左孩子；r2i+1是ri的右孩子。1236276549817355403498例如:14{12,36,27,65,40,14,98,81,73,55,49}堆排序的過程主要需要解決兩個問題：(1)按堆定義建初堆（2）去掉最大元之後重建堆，得到次大元。問題1:當堆頂元素改變時，如何重建堆?首先將完全二叉樹根結點中的記錄移出，該記錄稱為待調整記錄。此時根結點相當於空結點。從空結點的左、右子中選出一個關鍵字較小的記錄，如果該記錄的關鍵字小於待調整記錄的關鍵字，則將該記錄上移至空結點中。此時，原來那個關鍵字較小的子結點相當於空結點。重複上述移動過程，直到空結點左、右子的關鍵字均不小於待調整記錄的關鍵字。此時，將待調整記錄放入空結點即可。上述調整方法相當於把待調整記錄逐步向下“篩”的過程，所以一般稱為“篩選”法。所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調整”根結點使整個二叉樹也成為一個堆。堆堆篩選98814973556412362740例如:是大根堆12但在98和12進行互換之後，它就不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較篩選演算法為：voidsift（RecordTyper[],intｋ，intｍ）/*假設ｒ[k..m]是以ｒ[k]為根的完全二叉樹，且分別以ｒ[2k]和ｒ[2k+1]為根的左、右子樹為大根堆，調整r[k]，使整個序列r[k..m]滿足堆的性質*/{t=r[k]；/*暫存“根”記錄r[k]*/x=r[k].key；i=k；j=2*i；finished=FALSE；while(j=m!finished){if(jmr[j].keyr[j+1].key)j=j+1；/*若存在右子樹，且右子樹根的關鍵字大，則沿右分支“篩選”*/if(x=r[j].key)finished=TRUE；/*篩選完畢*/else{r[i]=r[j]；i=j；j=2*i；}/*繼續篩選*/}r[i]=t;/*r[k]填入到恰當的位置*/}/*sift*/問題2:如何由一個任意序列建初堆？一個任意序列看成是對應的完全二叉樹，由於葉結點可以視為單元素的堆，因而可以反復利用“篩選”法，自底向上逐層把所有子樹調整為堆，直到將整個完全二叉樹調整為堆。建堆演算法如下：voidcrt_heap(RecordTyper[],intlength)/*對記錄數組r建堆，length為數組的長度*/{n=length;for(i=n/2;i=1;--i)/*自第個記錄開始進行篩選建堆*/sift(r，i，n)；}問題3:如何利用堆進行排序？進行堆排序的步驟：①將待排序記錄按照堆的定義建初堆（演算法9.10），並輸出堆頂元素；②調整剩餘的記錄序列，利用篩選法將前n-i個元素重新篩選建成為一個新堆，再輸出堆頂元素；③重複執行步驟②n-1次進行篩選,新篩選成的堆會越來越小，而新堆後面的有序關鍵字會越來越多，最後使待排序記錄序列成為一個有序的序列，這個過程稱之為堆排序。堆排序的演算法為：voidHeapSort（RecordTyper[],intlength）/*對r[1..n]進行堆排序，執行本演算法後，r中記錄按關鍵字由大到小