【正文】 12 25 25 32 36 43 48 57 65 76 （三趟希爾排序結(jié)果） 希爾排序過程圖示 一趟希爾排序算法的 C函數(shù)： void shellInsert(RecType R[],int d) /*按步長(zhǎng) d進(jìn)行分組，每一組分別做直接插入排序 */ { int i,j。i=N。j=id。amp。 j=jd。 /*插入記錄 */ } } 整個(gè)希爾排序算法的 C函數(shù)： void shellSort(RecType R[]， int d[],int t) /*d[0]~d[t1]為每一趟分組的步長(zhǎng) */ { int k。kt。 } 希爾排序算法的性能分析 167。 167。 167。 7． 3 交換排序 交換排序的 基本思想 是：兩兩比較待排序記錄的排序碼，不符合排列順序則交換記錄，直到所有記錄的排序碼都符合排序要求。 7． 3． 1 起泡排序 起泡排序的 基本思想 是：首先將記錄 R[1]的排序碼與記錄R[2]的排序碼做比較（從上向下），若 R[1]的排序碼大于R[2]的排序碼，則交換兩個(gè)記錄的位置，使排序碼大的記錄（重者）往下“沉”（移到下標(biāo)大的位置），使排序碼小的記錄（輕者）往上“浮”（移到下標(biāo)小的位置）；然后比較R[2]和 R[3]的排序碼，同樣輕者上浮，重者下沉；依此類推，直到比較 R[n1]和 R[n]的排序碼，若不符合順序就交換位置，稱此過程為 一趟起泡排序 ，結(jié)果是 R[1]~R[n]中排序碼最大的記錄沉“底”，即放入 R[n]中。這樣重復(fù)進(jìn)行 n1趟排序后，對(duì)于 n個(gè)記錄的起泡排序就結(jié)束了，數(shù)組 R[1]~R[n]成為有序表。 int i,j,flag。iN。 /*flag表示每趟排序是否交換，比較之前置為 1 ，表示無(wú)交換 */ for (j=1。j++) /*進(jìn)行第 i趟排序 */ if (R[j].keyR[j+1].key) { x=R[j]。R[j+1]=x。 } if (flag) break。 時(shí)間效率：起泡排序的最好時(shí)間復(fù)雜度為O(n)，最壞時(shí)間復(fù)雜度為 O(n2)，可以證明它的平均時(shí)間復(fù)雜度也為 O(n2)。 空間效率：在整個(gè)算法中，需要一個(gè)用于交換記錄的輔助空間，所以起泡排序的空間復(fù)雜度為 O(1)。 穩(wěn)定性：起泡排序是穩(wěn)定的。 快速排序的 基本思想 是：在 R[1]~R[n]中，任意選取一個(gè)記錄作為“基準(zhǔn)記錄”，將整個(gè)數(shù)組劃分為兩個(gè)子區(qū)間： R[1]~R[i1]和 R[i+1]~R[n]，前一個(gè)區(qū)間中記錄的排序碼都小于或等于基準(zhǔn)記錄的排序碼，后一區(qū)間中記錄的排序碼都大于或等于基準(zhǔn)記錄的排序碼，基準(zhǔn)記錄落在排序的最終位置 R[i]上，我們稱該過程為一次劃分（或一趟快速排序）。 舉例：排序碼初始序列為（ 49， 14， 38， 74， 96， 65， 8， 49， 55， 27），對(duì)其進(jìn)行快速排序。 R[0] R[1] R[2] R[3] R[4] R[5] R[6] R[7] R[8] R[9] R[10] 49 {49 14 38 74 96 65 8 49 55 27} {□ 14 38 74 96 65 8 49 55 27} ↑ ↑ low=1 high=10 從 high向前搜索小于 R[0].key的記錄，找到 R[10]，將 R[10]移到 R[low] {27 14 38 74 96 65 8 49 55 □ } ↑ ↑ low=1 high=10 從 low向后搜索大于 R[0].key的記錄，找到 R[4]，將 R[4]移到 R[high] {27 14 38 □ 96 65 8 49 55 74} ↑ ↑ low=4 high=10 從 high向前搜索小于 R[0].key的記錄，找到 R[7]，將 R[7]移到 R[low] {27 14 38 8 96 65 □ 49 55 74} ↑ ↑ low=4 high=7 從 low向后搜索大于 R[0].key的記錄，找到 R[5]，將 R[5]移到 R[high] {27 14 38 8 □ 65 96 49 55 74} ↑ ↑ low=5 high=7 從 high向前搜索小于 R[0].key的記錄，兩指針相遇 low== high {27 14 38 8 □ 65 96 49 55 74} ↑↑ low high 一次劃分結(jié)束，填入基準(zhǔn)記錄： R[low]=R[0]，此時(shí)數(shù)組分成前后兩個(gè)子區(qū)間 {27 14 38 8} 49 {65 96 49 55 74} R[1] R[2] R[3] R[4] R[5] R[6] R[7] R[8] R[9] R[10] {49 14 38 74 96 65 8 49 55 27} 初始狀態(tài) {27 14 38 8} 49 {65 96 49 55 74} 第一層劃分結(jié)果 { 8 14} 27 38 49 {55 49} 65 {96 74}第二層劃分結(jié)果 8 14 27 38 49 49 55 65 74 96 第三層劃分結(jié)果 快速排序全過程圖示 一次劃分的 C函數(shù)如下： int partition(RecType R[] ,int low,int high) /*一趟快速排序 */ { int k。 /*以子表的第一個(gè)記錄作為基準(zhǔn)記錄 */ k=R[low].key。amp。 if(lowhigh) /*比基準(zhǔn)記錄小的交換到前端 */ R[low]=R[high]。amp。 if(lowhigh) /*比基準(zhǔn)記錄大的交換到后端 */ R[high]=R[low]。 /*基準(zhǔn)記錄到位 */ return low。 if(lowhigh) { part=partition(R,low,high)。 /*對(duì)前面的子區(qū)間快速排序 */ QSort(R,part+1,high)。 時(shí)間效率：最好的情況下，時(shí)間復(fù)雜度為O(nlog2n）；在最壞情況下， O(n2)；平均時(shí)間復(fù)雜度仍為 O(nlog2n)。 空間效率：最好空間復(fù)雜度為 O(log2n)；最壞空間復(fù)雜度為 O(n)；平均空間復(fù)雜度也為O(log2n)。 快速排序是一個(gè)不穩(wěn)定的排序方法。 本節(jié)介紹直接選擇排序和堆排序兩種方法。第 i（ 1≤i≤n1）趟直接選擇排序的結(jié)果是將 R[i]~R[n]中排序碼最小的記錄放到待排序子區(qū)間的最前面，即與 R[i]交換位置。 舉例：設(shè)有 8個(gè)待排序記錄的排序碼為（ 25， 36， 48， 65， 25， 12， 43， 57）。 int i,j,k。iN。 /*k保存當(dāng)前排序碼最小記錄的下標(biāo)，初值是 i*/ for (j=i+1。j++) if(R[j].keyR[k].key) k=j。 R[i]=R[k]。 } } } 直接選擇排序的性能分析 167。 167。 167。 7． 4． 2 堆排序 一、堆的定義：設(shè) n個(gè)元素的序列為（ K1， K2， … ，Kn），當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為 堆 。 例：（ 12， 36， 24， 85， 47， 30， 53， 91），它滿足堆定義的第一個(gè)條件，因此是小根堆。 二、堆與二叉樹 如果把存儲(chǔ)堆的一維數(shù)組看作是完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，就可以把堆轉(zhuǎn)換為完全二叉樹來表示 。 （ 1）首先將 R[1]~R[n]這 n個(gè)記錄按排序碼建成大根堆。如此反復(fù) n1次，每次選一個(gè)排序碼最大的記錄與本次排序區(qū)間的最后一個(gè)記錄交換位置，最終得到一個(gè)有序序列。 （ a） 8個(gè)結(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