【文章內容簡介】 都選較大的部分進棧，處理較短的部分，則棧內積累的元素就會較少，在這種情況下，對棧的大小的需求為O(log2n)。 167。 選擇排序 選 擇 排 序（ Selection sort） 的基本思想是：依次選出第 1小 、 第 2小 , … 的記錄 ， 主要有兩種形式的選擇排序：直接選擇排序和堆排序 。 167。 直接選擇排序 設待排序的記錄集中記錄的下標（位置）為 0~n1，則直接選擇排序的基本做法是：首先位置0~n1的記錄中選出鍵值最小的記錄，把它與位置 0的記錄交換，然后，位置 1~n1的記錄中選出鍵值最小的記錄，把它與位置 1的記錄交換，依此類推，最后在位置 n2與 n1中選出最小者，把它與位置n2的記錄交換。至此，所有記錄都按升序排列了。 這種思想可描述如下： for (i=0。 in1。 i++) 在 a[i]a[n1]中選擇一個最小記錄并令其與 a[i]交換位置； 而 “ 在 a[i]—a[n1]中選擇一個最小記錄并令其與 a[i]交換位置 ” 的實現(xiàn)為： k=i。 //將 k做為一面 “ 旗幟 ” ， 指向當前掃描發(fā)現(xiàn)的最小記錄 for (j=i+1。 jn。 j++) if (a[k]a[j]) k = j。 //當前 “ 旗幟 ” 比新掃描到的記錄大時 ， 旗幟指向新記錄 //退出循環(huán)后 ， “ 旗幟 ” 所指即為掃描范圍內的最小者 t = a[k]。 //交換 a[k]=a[i]。 a[i]=t。 例如 ， 對具有初始輸入序列 8， 4， 3， 6， 9， 2，7的記錄 ， 采用直接選擇排序進行排序 ， 過程如下 （ 方拓號表示無序區(qū) ） ： [8 4 3 6 9 2 7] 2 [4 3 6 9 8 7] 2 3 [4 6 9 8 7] 2 3 4 [6 9 8 7] 2 3 4 6 [9 8 7] 2 3 4 6 7 [8 9] 2 3 4 6 7 8 [9] 該選擇排序算法主要部分是兩層嵌套的 for循環(huán) ，顯然其時間復雜性為 O（ n2） 。 167。 堆排序 (一 ) 基本思想 對直接選擇排序來說，為了從 n個鍵值中找出最小的，需要進行 n1次比較。然后又在 n1個鍵值中找出次最小的。需進行 n2次比較，等等。事實上，后面這 n2次比較中有許多比較可能在前面的 n1次比較中已經(jīng)做過，但由于第一次比較時這些結果沒有保留下來，所以在第二次又重復進行。樹形選擇排序可以克服這一缺點，它的基本思想是：首先對 n個記錄的鍵值進行兩兩比較。然后在其中 [n/2]個較小者之間再進行兩兩比較。如此重復，直至選出最小鍵值的記錄為止。 可用一棵樹來表示這一排序過程 。 樹中的 n個葉子代表待排序記錄的鍵值 。 葉子上面一層是葉子兩兩比較的結果 ， 依此類推 ，樹根表示最后選擇出來最小關鍵字 。 在選擇出最小鍵值后 ， 將其輸出 ， 然后 ， 再在剩余的樹結點中 ，按類似的方法選擇最小者 ， 這樣 ， 一共經(jīng)過 n1選擇 ， 就將全部記錄按升序輸出了 。 但不同的是 ， 以前的比較結果 ， 通過樹記錄下來了 ， 使得后面的選擇可以在它們的基礎上進行 。 如果專門設立樹 ， 則造成存儲浪費 。 堆排序是一種巧妙的樹形選擇排序 ， 它不需要專門設立樹 。 首先給出幾個概念 。 堆結構 ：即前面介紹的順序二叉樹 。 堆 ：若某堆結構中 ， 每個結點的值均小于它的兩個兒子的值 ，則稱該堆結構為堆 。 當然 ， 也可以將該定義中的 “ 小于 ” 改為“ 大于 ” （ 成為另為一種次序的堆 ） 。 那么 ， 如何存儲堆結構 （ 順序二叉樹 ） 呢 ？ 根據(jù)我們在 “ 樹形結構 ” 一章中的介紹 ， 最簡單的方法是 ， 按順序二叉樹的順序存儲 ， 即將樹中各元素 ， 按從上到下 （ 從根的方向到葉子方向 ） ， 同層中從左到右的次序 ， 存儲在一維數(shù)組中 。 據(jù)此 ， 我們很容易由樹結構寫出對應的數(shù)組存儲 ， 或反過來由數(shù)組畫出對應的堆結構 。 圖 111給出一個堆和它的數(shù)組存儲的例子 。 在這種存儲方法中 ， 父子關系不存儲 ， 隱含在元素的序號中 。 父子關系的確定方法為：若各元素在數(shù)組中的序號為 1~n， 則對序號為 i的結點 ， 它的父親的序號為 [i/2]， 它的左兒的序號為 2i（ 當 2in時無左兒 ） ， 它的右兒的序號為 2i+1（ 當 2i+1n時無右兒 ） 。 堆排序的基本方法可描述為： 1 [建堆 ] 將原始數(shù)據(jù)調整為堆； 2 [輸出 ] 輸出堆頂元素 3 [堆調整 ] 將堆結構中剩余元素重新調整為堆 4 [判斷 ] 若全部元素均已輸出 ， 則結束 ， 輸出次序即為排序次序 。 否則 ， 轉2。 10 20 18 29 32 19 22 40 50 38 10 20 18 29 32 19 22 40 50 38 圖 11 1堆示例 (二 ) 堆調整 由上面的討論知 ， 堆調整是堆排序的關鍵 。 堆調整是針對這樣的堆結構：堆頂 （ 根 ） 的左右子樹都是堆 ，但考慮堆頂后 ， 就可能不滿足堆的定義了 。 堆調整就是要將這樣一種堆結構調整為堆 。 具體的調整方法是 ， 首先將堆頂元素取出 ， 放到臨時存儲器 x中 ，然后 ， 將 x和堆頂?shù)男鹤?（ 值較小的兒子 ） 比較 ， 如果 x比小兒子大 ， 則將小兒子放到堆頂 ， 而將 x放到小兒子的位置 ， 然后 ， 按類似的方法調整以小兒子為根的新堆結構；如果 x不比小兒子小 ，則不需要繼續(xù)調整 ， 將 x放到堆頂即可 。如果某次的 （ 新 ） 堆頂為葉子 ， 則調整也終止 。 該過程顯然是個遞歸過程 ， 采用遞歸程序很自然 。 具體的堆調整遞歸程序如下 。 A 在程序中要注意數(shù)組下標和樹結點編號間的轉換 。 樹結點編號是從 1起的連續(xù)自然數(shù) （ 父子關系的計算公式是基于這個假定的 !） ， 而數(shù)組下標為從 0起的連續(xù)自然數(shù) ， 故需要換算 。 圖 111通過一個例子說明了堆調整過程 。 void HeapShift2(int a[], long p1, long p2) {//將 a[p1]~a[p2]調整為堆 。 a[p1]~a[p2]對應的堆結構中 ， 除去堆頂 a[p1]外 ， //其他子樹都是堆 ， 堆結構的根的編號為 1。 //每個堆元素占一個數(shù)組元素 。 數(shù)組下標從 0起 。 long j。 int x。 if (p1=p2) return。 //只有一個元素 (葉子 )或無元素 j=2*(p1+1)。//求 p1的左兒子 。 注意數(shù)組下標和結點編號的換算 j。 //將編號換算為下標 if (jp2) return 。 //p1無左兒子 （ 即 p1為葉子 ） 時不需要調整 if (j+1=p2) if (a[j]a[j+1]) j++。//令 j為 p1的值最小的兒子 if (a[p1]a[j]) return 。//堆頂比它的小兒子還小時 ， 不需要繼續(xù)調整 x=a[p1]。 //堆頂元素與小兒子交換 a[p1]=a[j]。 a[j]=x。 HeapShift2(a, j, p2)。 //繼續(xù)對以小兒子為頂?shù)男露呀Y構調整 } 現(xiàn)在考慮堆調整的非遞歸實現(xiàn)。調整的過程，實質上是讓根結x（不滿足堆定義的結點）逐步下滑的過程。每次都是向小兒子方向下滑（同時小兒子上升，即換位）。當 x到達這樣的位置后停止下滑： x到達葉子位置，或 x比它的當前小兒子還要小。這個過程可用一個循環(huán)實現(xiàn)，具體程序如下。 void HeapShift(int a[], long p1, long p2) {//將 a[p1]~a[p2]調整為堆 。 a[p1]~a[p2]對應的堆結構中 ， 除去堆頂a[p1]外 ， //其他子樹都是堆 ,堆結構的根的編號為 1。 //每個堆元素占一個數(shù)組元素 。 數(shù)組下標從 0起 。 long i, j。 int x。 if (p1=p2) return。 //只有一個元素或無元素 i= p1+1。 j=2*i。 i。 j。 //將編號換算為下標 if (j+1=p2) //令 j為 i的值最小的兒子 if (a[j]a[j+1]) j++。 x=a[i]。 while (j=p2 amp。amp。 xa[j]) { a[i]=a[j]。 i =j。 j = 2*(i+1)。 j。 //將編號換算為下標 if (j+1=p2) if (a[j]a[j+1]) j++。 //令 j為 i的值最小的兒子 } a[i] = x。 return 。 } 30 20 21 29 32 19 22 40 50 38 (a) 堆結構 根的兩個兒子都是堆 ， 但根不滿足堆 20 30 21 29 32 19 22 40 50 38 (b) 調整 30與小兒子 20換位 圖 堆調整示例 20 29 21 30 32 19 22 40 50 38 (b) 調整 30與小兒子 29換位 。 在新位置 ， 30比小兒子小 ， 調整完畢 (一 ) 建堆 我們現(xiàn)在考慮如何將初始數(shù)據(jù) （ 初始堆結構 ） 調整為堆 。 顯然 ，對初始的堆結構 ， 它不滿足我們上面介紹的堆調整算法HeapShift()的條件 ， 所以不能直接使用該算法創(chuàng)建堆 。 但我們可以自底向上逐步調用 HeapShift()。 首先 ， 對以葉子為根的順序二叉樹 ， 由于其只含一個結點 ， 故可認為是堆 ， 因此 ， 以葉子為子樹的樹 ， 都滿足 HeapShift()的條件 。 我們從最后一個葉子的父親結點開始 ， 按從下到上 、 從右到左的次序 ， 對各結點 (k, k1, … , 1)逐步調用 HeapShift()（ 即對以結點 x為根的子樹調用 , x=k, k1, … 1） 。 顯然 ， 用根結點調用 HeapShift()后 ， 整棵樹就成了堆 。該過程的程序實現(xiàn)為： for (i=F1。 i=0。 i) HeapShift(a, i, F2)。 這里， F1為最后一個結點的父親的（在數(shù)組中的）序號， F2為以 i為根的子樹中的（層序下）最后一個結點的序號。如果最后結點的編號為 H，則它的父親的編號為 H/2，因此，若堆結構在數(shù)組 a[0]~a[n1]中，則 F1=(n1+1)/2 – 1，注意，在該計算式中，進行了數(shù)組序號與結點編號間的轉換。至于 F2，由于不同的 i，F(xiàn)2也不同，計算比較復雜，我們這里只簡單地令它等于整棵樹中的最后結點的編號，即 F2=n。盡管 n不是準確的結束點，但由HeapShift()的算法知，這樣處理是沒有問題的。 36 60 18 50 32 19 22 40 29 38 36 60 18 50 32 19 22 40 29 38 (a) 一個堆 36 60 18 50 32 19 22 40 29 38 36 60 18 50 32 19 22 40 29