【文章內(nèi)容簡介】 R[2] R[3] R[4] R[5] R[ 6] R[7] R[ 8] [25 36 48 65 25 12 43 57] （初始狀態(tài)） 12 [36 48 65 25 25 43 57] （第 1趟排序的結(jié)果） 12 25 [48 65 36 25 43 57] (第 2趟排序的結(jié)果） 12 25 25 [65 36 48 43 57] (第 3趟排序的結(jié)果） 12 25 25 36 [65 48 43 57] (第 4趟排序的結(jié)果） 12 25 25 36 43 [48 65 57] (第 5趟排序的結(jié)果） 12 25 25 36 43 48 [65 57] (第 6趟排序的結(jié)果） 12 25 25 36 43 48 57 [65] (第 7趟排序的結(jié)果） 直接選擇排序過程圖示 直接選擇排序算法的 C函數(shù)： void selectSort(RecType R[]) /*用直接選擇排序?qū)?shù)組 R中的記錄進(jìn)行排序 */ { RecType x。 int i,j,k。 for (i=1。iN。i++) /*共進(jìn)行 n1趟排序 */ { k=i。 /*k保存當(dāng)前排序碼最小記錄的下標(biāo)，初值是 i*/ for (j=i+1。j=N。j++) if(R[j].keyR[k].key) k=j。 /*從當(dāng)前的子區(qū)間里選擇排序碼最小的記錄 */ if (k!=i) /*將排序碼最小的記錄放到子區(qū)間的第一個位置 */ { x=R[i]。 R[i]=R[k]。 R[k]=x。 } } } 直接選擇排序的性能分析 167。 時間效率：直接選擇排序主要時間消耗在比較操作上，其平均時間復(fù)雜度為 O(n2)。 167。 空間效率：在整個算法中，只需要一個用于交換記錄的輔助空間，所以直接選擇排序的空間復(fù)雜度為 O(1)。 167。 穩(wěn)定性直接選擇排序是不穩(wěn)定的。 7． 4． 2 堆排序 一、堆的定義：設(shè) n個元素的序列為（ K1， K2， … ，Kn），當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為 堆 。 （ 1） Ki≤K2i且 Ki≤K2i+1， 1≤i≤ ?n/2? （ 2） Ki≥K2i且 Ki≥K2i+1， 1≤i≤ ?n/2? 滿足第（ 1）個條件的稱作 小根堆 ， 滿足第（ 2）個條件的稱作 大根堆 。 例：（ 12， 36， 24， 85， 47， 30， 53， 91），它滿足堆定義的第一個條件，因此是小根堆。 （ 91， 47， 85， 24， 36， 53， 30， 16），它滿足堆定義的第二個條件，因此是大根堆。 二、堆與二叉樹 如果把存儲堆的一維數(shù)組看作是完全二叉樹的順序存儲結(jié)構(gòu)，就可以把堆轉(zhuǎn)換為完全二叉樹來表示 。 9147 8524 36 53 301212 36 24 85 47 30 53 91 91 47 85 24 36 53 30 12 三、堆排序的基本思想：利用大（或小）根堆的性質(zhì)不斷地選擇排序碼最大（或?。┑挠涗泚韺?shí)現(xiàn)排序的，利用大根堆來實(shí)現(xiàn)升序排列。 （ 1）首先將 R[1]~R[n]這 n個記錄按排序碼建成大根堆。 （ 2）然后 R[1]與 R[n]交換位置，即把排序碼最大的記錄放到待排序區(qū)間的最后；接著，再把 R[1]~R[n1]中的 n1個記錄建成大根堆，仍然將堆頂 R[1]與R[n1]交換位置。如此反復(fù) n1次，每次選一個排序碼最大的記錄與本次排序區(qū)間的最后一個記錄交換位置，最終得到一個有序序列。 堆排序需解決兩個問題： （ 1） 如何將 n個待排序記錄按排序碼建成堆？ （ 2） 交換堆頂記錄后，對剩余的 n1個記錄重新建堆的過程和前面的建堆過程是否相同？ （ a） 初始大根堆 （ b） 91與 12對換之后 （ c） 12與 85對換之后 （ d） 12與 53對換之后 交換堆頂元素之后 調(diào)整堆的過程圖示 舉例：對 (49， 38， 65， 97， 76， 13， 27， 49) 堆排序。 （ a） 8個結(jié)點(diǎn)的初始狀態(tài) （ b） 篩選 97之后的狀態(tài) （ c） 篩選 65之后的狀態(tài) （ d） 篩選 38之后的狀態(tài) （ e） 篩選 49之后的狀態(tài) 建堆過程圖示 6 54 93 8 4 9 1 32 77 69 76 5 4 9 2 7 3 8 4 9 1 3 [ 7 6 9 7 ]（ c ） 第 二 趟 排 序 結(jié) 果4 94 93 8 1 3 6 52 77 69 74 9 4 9 2 7 3 8 1 3 [ 6 5 7 6 9 7 ]（ d ） 第 三 趟 排 序 結(jié) 果9 77 64 9 4 9 1 36 52 73 89 7 7 6 6 5 4 9 4 9 1 3 2 7 3 8（ a ） 初 始 堆7 64 93 8 4 9 1 36 52 79 77 6 4 9 6 5 3 8 4 9 1 3 2 7 [ 9 7 ]（ b ） 第 一 趟 排 序 后 調(diào) 整 為 堆4 93 81 3 4 9 6 52 77 69 74 9 3 8 2 7 1 3 [ 4 9 6 5 7 6 9 7 ]（ e ） 第 四 趟 排 序 結(jié) 果3 81 34 9 4 9 6 52 77 69 73 8 1 3 2 7 [ 4 9 4 9 6 5 7 6 9 7 ]（ f ） 第 五 趟 排 序 結(jié) 果2 71 34 9 4 9 6 53 87 69 72 7 1 3 [ 3 8 4 9 4 9 6 5 7 6 9 7 ]（ g ） 第 六 趟 排 序 結(jié) 果1 32 74 9 4 9 6 53 87 69 71 3 [ 2 7 3 8 4 9 4 9 6 5 7 6 9 7 ]（ h ） 第 七 趟 排 序 結(jié) 果“篩選法” 算法的 C函數(shù)如下： void heapSift(RecType R[],int i, int n) /*R[i]為根結(jié)點(diǎn)，調(diào)整 R[i]~R[n]為大根堆 */ { RecType rc。 int j。 rc=R[i]。 j=2*i。 while(j=n) /*沿排序碼較大的孩子結(jié)點(diǎn)向下篩選 */ { if(jn amp。amp。 R[j].keyR[j+1].key) /*j為排序碼較大的記錄下標(biāo) */ j=j+1。 if(R[j].key) break； R[i]=R[j]。 /*記錄移動到 R[i] */ i=j。 j=j*2。} /*調(diào)整進(jìn)入下一層 */ R[i]=rc。 /*找到了根結(jié)點(diǎn)最后應(yīng)插入的位置 */ } 堆排序算法 heapSort()的 C函數(shù)： void heapSort(RecType R[],int n) /*對 n個記錄進(jìn)行堆排序 */ { int i。 RecType x。 for(i=n/2。i=1。i) /*將 R[i]~R[n]建成堆 */ heapSift(R， i， n)； for(i=n。i1。i) /*進(jìn)行 n1趟排序 */ { x=R[i]。 /*堆頂與最后一個記錄交換位置 */ R[i]=R[1]。 R[1]=x。 heapSift(R， 1， i1)。 /*將 R[1]~R[i1]重新調(diào)整為堆 */ } } 堆排序的性能分析如下： 167。 時間效率：堆排序的時間主要消耗在篩選算法中，一共調(diào)用了 ?n/2?+n1（約 3n/2）次的篩選算法，在每次篩選算法中，排序碼之間的比較次數(shù)都不會超過完全二叉樹的高度，即 ?log2n? +1，所以整個堆排序過程的最壞時間復(fù)雜度為 O(nlog2n)，也是其平均時間復(fù)雜度。 167。 空間效率：在整個堆排序過程中，需要 1個與記錄大小相同的輔助空間用于交換記錄，故其空間復(fù)雜度為 O(1)。 167。 堆排序是一種不穩(wěn)定的排序方法。 7． 5 歸并排序 歸并排序 （ Merge Sort）是利用“歸并”技術(shù)實(shí)現(xiàn)的排序方法。所謂 歸并 就是將兩個或多個有序表合并成一個有序表的過程。如果是將兩個有序表合并成一個有序表稱為 二路歸并 ；同理，將三個有序表合并成一個有序表稱為三路歸并，以此類推可以有 n路歸并等。本節(jié)主要講二路歸并技術(shù)實(shí)現(xiàn)的歸并排序。 二路歸并方法：設(shè)數(shù)組 R由兩個有序子表 R[u]~R[v]和R[v+1]~R[t]組成（ u≤v,v+1≤t），將這兩個有序子表合并之后存于數(shù)組 A中，得到一個新的有序表A[u]~A[t]。設(shè) i=u， j=v+1， k=u，即 i， j， k分別指向三個有序表的起始下標(biāo)，歸并過程為：比較 R[i].key和 R[j].key的大小，如果 R[i].key≤R[j].key，則將第一個有序子表的記錄 R[i]復(fù)制到 A[k]中，并令 i和 k分別加 1，指向下一個位置，否則將第二個有序子表的記錄 R[j]復(fù)制到 A[k]中，并令 j和 k分別加 1，如此循環(huán)下去，直到其中一個有序子表已到表尾，然后將另一個有序子表中剩余的記錄復(fù)制到數(shù)組A[k]~A[t]中，至此二路歸并結(jié)束。 二路歸并排序：首先把存儲在數(shù)組 R中的每個記錄看成是長度為 1的有序表，則 n個記錄構(gòu)成 n個有序表，接下來依次進(jìn)行二路歸并，歸并成「 n/2?個長度為 2的有序表，當(dāng) n是奇數(shù)時，還會剩余一個長度為 1的有序表，通常把這個過程稱為一趟歸并排序。每完成一趟歸并排序，都會使有序表的長度變?yōu)樯弦惶说?2倍，但最后一個有序表的長度有可能小一些。 舉例： (45,53,18,36,73,45,93,15,30,48) [45] [53] [18] [36] [73] [45] [93] [15] [30] [48] (初始狀態(tài)） [45 53] [18 36] [45 73] [15 93] [30 48] (1趟歸并 ) [18 36 45 53] [15 45 73 93] [30 48] (2趟歸并 ) [15 18 36 45 45 53 73 93] [30 48] (3趟歸并 ) [15 18 30 36 45 45 48 53 73 93] (4趟歸并 ) 歸并排序過程圖示 一趟歸并排序算法需要多次調(diào)用二路歸并。設(shè)數(shù)組 R中每個有序表的長度為 len，（最后一個表長度可能小于 len） ,對其進(jìn)行一趟歸并排序，結(jié)果存于數(shù)組 A中。實(shí)際處理過程中，可能有以下三種情況：（ 1）數(shù)組 R中有偶數(shù)個長度都是 len的有序表的，這時只要連續(xù)調(diào)用二路歸并 merge(R， A， p， p+len1， p+len*21），即可完成一趟歸并，這里 p為有序表的起始下標(biāo)；（ 2