1、堆排序堆排序是利用堆的性質進行的一種選擇排序，下面先討論一下堆。1 .堆堆實際上是一棵完全二叉樹，其任何一非葉節點滿足性質：Keyi<=key2i+1&&Keyi<=key2i+2或者Keyi>=Key2i+1&&key>=key2i+2即任何一非葉節點的關鍵字不大于或者不小于其左右孩子節點的關鍵字。堆分為大頂堆和小頂堆，滿足Keyi>=Key2i+1&&key>=key2i+2稱為大頂堆，滿足Keyi<=key2i+1&&Keyi<=key2i+2稱為小頂堆。由上述性質可知大頂堆的

2、堆頂的關鍵字肯定是所有關鍵字中最大的，小頂堆的堆頂的關鍵字是所有關鍵字中最小的。2 .堆排序的思想利用大頂堆（小頂堆）堆頂記錄的是最大關鍵字（最小關鍵字）這一特性，使得每次從無序中選擇最大記錄（最小記錄）變得簡單。其基本思想為（大頂堆）：1）將初始待排序關鍵字序列（R1,R2.Rn購建成大頂堆，此堆為初始的無序區；2）將堆頂元素R1與最后一個元素Rn交換，此時得到新的無序區（R1,R2,.Rn-1沐口新的有序區（Rn）,且滿足R1,2.n-1<=Rn;3）由于交換后新的堆頂R1可能違反堆的性質，因此需要對當前無序區（R1,R2,.Rn-1調整為新堆，然后再次將R1與無序區最后一個元素交換

3、，得到新的無序區（R1,R2.Rn-2）和新的有序區（Rn-1,Rn）o不斷重復此過程直到有序區的元素個數為n-1,則整個排序過程完成。操作過程如下：1）初始化堆：將R1.n構造為堆；2）將當前無序區的堆頂元素R1同該區間的最后一個記錄交換，然后將新的無序區調整為新的堆。因此對于堆排序，最重要的兩個操作就是構造初始堆和調整堆，其實構造初始堆事實上也是調整堆的過程，只不過構造初始堆是對所有的非葉節點都進行調整。下面舉例說明：給定一個整形數組a尸16,7,3,20,17,8,對其進行堆排序。首先根據該數組元素構建一個完全二叉樹，得到然后需要構造初始堆，則從最后一個非葉節點開始調整，調整過程如下:2

4、0和16交換后導致16不滿足堆的性質，因此需重新調整，這樣就得到了初始堆。即每次調整都是從父節點、左孩子節點、右孩子節點三者中選擇最大者跟父節點進行交換（交換之后可能造成被交換的孩子節點不滿足堆的性質，因此每次交換之后要重新對被交換的孩子節點進行調整）。有了初始堆之后就可以進行排序了。此時3位于堆頂不滿堆的性質，則需調整繼續調整這樣整個區間便已經有序了。從上述過程可知，堆排序其實也是一種選擇排序，是一種樹形選擇排序。只不過直接選擇排序中，為了從R1.n中選擇最大記錄，需比較n-1次，然后從R1.n-2中選擇最大記錄需比較n-2次。事實上這n-2次比較中有很多已經在前面的n-1次比較中已經做過，

5、而樹形選擇排序恰好利用樹形的特點保存了部分前面的比較結果，因此可以減少比較次數。對于n個關鍵字序列，最壞情況下每個節點需比較10g2(n)次，因此其最壞情況下時間復雜度為nlogn。堆排序為不穩定排序，不適合記錄較少的排序。/*堆排序(大頂堆)測試程序*/#inc1ude<iostream>#inc1ude<a1gorithm>usingnamespacestd;intlchild=2*i;intrchild=2*i+1;intmax=i;if(i<=size/2)voidHeapAdjust(int*a,inti,intsize)/調整堆/i的左孩子節點序號/i

6、的右孩子節點序號臨時變量/如果i是葉節點就不用進行調整if(lchild<=size&&alchild>amax)max=lchild;if(rchild<=size&&archild>amax)max=rchild;if(max!=i)swap(ai,amax);max為父節點的子樹不是堆HeapAdjust(a,max,size);/避免調整之后以voidBuildHeap(int*a,intsize)/建立堆inti;for(i=size/2;i>=1;i-)非葉節點最大序號值為size/2HeapAdjust(a,i,siz

7、e);)voidHeapSort(int*a,intsize)/堆排序(inti;BuildHeap(a,size);for(i=size;i>=1;i-)(/cout<<a1<<""swap(a1,ai);/交換堆頂和最后一個元素，即每次將剩余元素中的最大者放到最后面/BuildHeap(a,i-1);/將余下元素重新建立為大頂堆HeapAdjust(a,1,i-1);/重新調整堆頂節點成為大頂堆)intmain(intargc,char*argv口)(/inta=0,16,20,3,11,17,8;inta100;intsize;while(scanf("%d",&size)=1&&size>0)inti;for(i=1;i<=size;i