【正文】 第 9章 排 序 第 9章 排 序 排序基本概念 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序 內(nèi)部排序總結(jié) 有關(guān)排序算法的 C語言源程序 習(xí)題九 第 9章 排 序 排序基本概念 排序 (sorting)又稱分類，意指把一批雜亂無章的數(shù)據(jù)序列重新排列成有序序列。排序是程序設(shè)計中一種重要運算。在很多領(lǐng)域中有廣泛的應(yīng)用。譬如，在查找時，若文件的記錄按關(guān)鍵字預(yù)先排好順序，可以采用折半查找方法提高查找效率。折半查找的平均查找長度數(shù)量級為 O(lbn)，而順序查找的平均查找長度數(shù)量級為 O(n)。又如，建立二叉排序樹的過程本身就是一個排序過程。日常生活中的各類競賽活動，如歌唱大獎賽等，還有各種升學(xué)考試錄取工作均離不開排序。 第 9章 排 序 按待排序的記錄的數(shù)量多少，排序過程中涉及的存儲介質(zhì)不同，排序方法分為兩大類：內(nèi)部排序和外部排序。內(nèi)部排序是指待排序的記錄存放在計算機內(nèi)存之中；外部排序是指待排序的記錄數(shù)量很大，以至于內(nèi)存容納不下而存放在外存儲器之中，排序過程需要訪問外存。本章主要討論內(nèi)部排序。外部排序在。 排序的依據(jù)可以是記錄的主關(guān)鍵字，也可以是次關(guān)鍵字，甚至是若干數(shù)據(jù)項的組合。為了討論方便把排序所依據(jù)的數(shù)據(jù)項統(tǒng)稱排序關(guān)鍵字，簡稱關(guān)鍵字。假設(shè)含有 n個記錄的序列為｛ R1， R2， … ， Rn｝，其相應(yīng)的關(guān)鍵字序列為｛ K1， K2， … ，Kn｝，所謂排序就是將記錄按關(guān)鍵字非遞減 (或非遞增 )的順序重新排列起來。 第 9章 排 序 在待排序的記錄中若有多個相同的關(guān)鍵字 ， 在用某種方法排序之后 ， 這些關(guān)鍵字相同的記錄相對先后次序不變 ， 則稱這種排序方法是穩(wěn)定的；否則是不穩(wěn)定的 。 本章所介紹的內(nèi)部排序方法包括插入排序 、 交換排序 、 選擇排序 、 歸并排序和基數(shù)排序 。 前四類排序是通過比較關(guān)鍵字的大小決定記錄先后次序 ， 也稱為比較排序 。 基數(shù)排序是不經(jīng)關(guān)鍵字比較的排序方法 。 第 9章 排 序 為了討論方便 ， 在此把排序關(guān)鍵字假設(shè)為整型 。 記錄的結(jié)構(gòu)定義： typedef struct /*記錄結(jié)構(gòu) */ {int key。 /*排序關(guān)鍵字域 */ int oth。 /*其他域 ， 根據(jù)需要自己設(shè)定 */ }node。 進行排序的向量結(jié)構(gòu)如下： node r[MAXSIZE] 其中 MAXSIZE是一常量，應(yīng)該足夠大。若記錄總數(shù)為 n，則MAXSIZEn。在本章各排序方法中，約定第一個記錄存放在r[1]之中。 第 9章 排 序 插 入 排 序 直接插入排序 直接插入排序 (straight insertion sort)是一種最簡單的排序方法 。它的基本操作是將一個記錄插入到一個長度為 m(假設(shè) )的有序表中 ， 使之仍保持有序 ， 從而得到一個新的長度為 m＋ 1的有序表 。 算法思路：設(shè)有一組關(guān)鍵字｛ K1， K2 ， … ， Kn ｝；排序開始就認為 K1是一個有序序列；讓 K2插入上述表長為 1的有序序列，使之成為一個表長為 2的有序序列；然后讓 K3插入上述表長為 2的有序序列，使之成為一個表長為 3的有序序列；依次類推，最后讓 Kn插入上述表長為 n1的有序序列，得一個表長為 n的有序序列。 第 9章 排 序 例 設(shè)有一組關(guān)鍵字序列｛ 55， 22， 44， 11， 33｝，這里 n=5，即有 5個記錄。如圖 。請將其按由小到大的順序排序。 第一趟 [ 5 5 ] 22 44 11 33第二趟 [ 2 2 5 5 ] 44 11 33第三趟 [ 2 2 44 5 5 ] 11 33第四趟 [ 1 1 22 44 5 5 ] 33結(jié) 果 [ 1 1 22 33 44 5 5 ]圖 直接插入排序示例 第 9章 排 序 在具體實現(xiàn) Ki 向前邊插入時 ， 有兩種方法 。 一種方法是讓Ki 與 K1， K2， … 順序比較；另一方法是 Ki 與 Ki1 ， Ki2， … 倒著比較 。 這里選用后一種方法 。 用一維數(shù)組 r做存儲結(jié)構(gòu)， n表示記錄個數(shù)。則算法如下： 第 9章 排 序 算法 void stinsort ( node r[?]， int n) ｛ for (i=2； i=n； i++) /*共進行 n1趟插入 */ ｛ r[0]=r[i]； /*r[0]為監(jiān)視哨，也可做下邊循環(huán)結(jié)束標志 */ j=i1； while (r[j].key r[0].key) ｛ r[j+1]=r[j]； j；｝ r[j+1]=r[0]； /*將 r[0]即原 r[i]記錄內(nèi)容，插到 r[j]后一位置 */ ｝ ｝ /*sinsort*/ 第 9章 排 序 此算法外循環(huán) n1次 ， 在一般情況下內(nèi)循環(huán)平均比較次數(shù)的數(shù)量級為 O(n)， 所以算法總時間復(fù)雜度為 O(n2)。 由于比較過程中 ， 當 Kj 與 K0 相等時并不移動記錄 ， 因此直接插入排序方法是穩(wěn)定的 。 直接插入排序也可用單鏈表做存儲結(jié)構(gòu) ， 當某結(jié)點 i的關(guān)鍵字 Ki 與前邊有序表比較時 ， 顯然先與 K1 比較 ， 再與 K2 比較 …… 即從鏈表表頭結(jié)點開始向后逐一比較更合適 。 另外 ， 直接插入排序在原關(guān)鍵字序列基本有序或 n值較小時 ， 它是一種最常用的排序方法 ， 它的時間復(fù)雜度接近于 O(n)。 但是 ， 當待排序的關(guān)鍵字無序 、 n值又較大時 ， 此方法就不再適用 。 第 9章 排 序 折半插入排序 當直接插入排序進行到某一趟時 ， 對于 r[i].key來講 ， 前邊 i1個記錄已經(jīng)按關(guān)鍵字有序 。 此時不用直接插入排序的方法 ，而改為折半查找 ， 找出 r[i].key應(yīng)插的位置 ， 然后插入 。 這種方法就是折半插入排序 (binary insertion sort)。 算法如下： 算法 void binasort(node r[?]， int n) ｛ for (i=2； i=n； i++) ｛ r[0]=r[i]； l=1； h=i1； whil (l=h) 第 9章 排 序 ｛ mid= (l+h)/2； if(r[0].keyr[mid].key) h=mid1； else l=mid+1； ｝ for(j=i1； j=l； j) r[j+1]=r[j]； r[l]=r[0]； ｝ ｝ /*binasort*/ 折半插入排序，關(guān)鍵字的比較次數(shù)由于采用了折半查找而減少，數(shù)量級為 O(nlog2n)，但是元素移動次數(shù)仍為 O(n2)。故折半插入排序時間復(fù)雜度仍為 O(n2)。折半插入排序方法是穩(wěn)定的。 第 9章 排 序 希爾排序 希爾排序 (shell sort)是 ()提出的 “ 縮小增量 ”的排序方法 。 它的作法不是每次一個元素挨一個元素的比較 。而是初期選用大跨步 (增量較大 )間隔比較 ， 使記錄跳躍式接近它的排序位置；然后增量縮??；最后增量為 1， 這樣記錄移動次數(shù)大大減少 ， 提高了排序效率 。 希爾排序?qū)υ隽啃蛄械倪x擇沒有嚴格規(guī)定 。 算法思路：先取一個正整數(shù) d1(d1n)，把全部記錄分成 d1 個組，所有距離為 d1 的倍數(shù)的記錄看成一組，然后在各組內(nèi)進行插入排序；然后取 d2 (d2 d1 )，重復(fù)上述分組和排序操作；直到取 di=1(i≥1)，即所有記錄成為一個組為止。一般選 d1 約為n/2， d2 為 d1 /2， d3為 d2 /2， … ， di=1。 第 9章 排 序 例 有一組關(guān)鍵字｛ 76， 81， 60， 22， 98， 33， 12，79｝，將其按由小到大的順序排序。這里 n=8，取 d1 =4， d2=2，d3 =1，其排序過程如圖 。算法如下： d1＝ 4 76 81 60 22 98 33 12 79d2＝ 2 76 33 12 22 98 81 60 79d3＝ 4 12 22 60 33 76 79 98 81結(jié)果 12 22 33 66 76 79 81 98圖 希爾排序示例 第 9章 排 序 算法 void shellsort(node r[?]， int n) ｛ k=n/2； /*k值代表前文中的 d值 */ while(k=1) ｛ for(i=k+1； i=n； i++) ｛ r[0]=r[i]； j=ik； while((r[j].keyr[0].key)amp。amp。 (j=0)) ｛ r[j+k]=r[j]； j=jk；｝ r[j+k]=r[0]； ｝ k=k/2； ｝ }/*shellsort*/ 第 9章 排 序 此算法外層循環(huán)是增量由 n/2逐步縮小到 1的循環(huán) 。 for所構(gòu)成的循環(huán)是針對某一特定的增量 k， 進行大跨步跳躍式的插入排序 。例如 k=2時 ， 關(guān)鍵字分成二組 ， 見圖 2行 ， 其中第 1組是[76,12,98,60]， 排序后的結(jié)果為 [12,60,76,98]， 插入操作如下： i=3 [K1=76]有序 ， K3 =12向前插； i=5 [12,76]有序 ， K5 =98不移動； i=7 [12,76,98]有序 ， K7 =60向前插 。 第 2組是 [33,22,81,79]， 排序后的結(jié)果為 [22,33,79,81]， 插入操作如下： i=4 [K2=33]有序 ， K4 =22向前插； i=6 [22,33]有序 ， K6 =81不移動； i=8 [22,33,81]有序， K8 =79向前插。 第 9章 排 序 對整個文件來說，排序結(jié)果實際上為：[12,22,60,33,76,79,98,81]。 當 K=1時 ， 此算法就等同于直接插入排序方法 。 由于前邊大增量的處理 ， 使關(guān)鍵字大體有序 ， 因此最后一趟排序移動的記錄少 ， 處理速度快 。 希爾排序的分析是一個復(fù)雜的問題，因為它的時間是所選定的“增量序列”的函數(shù)，這涉及到數(shù)學(xué)上一些尚未解決的難題。到目前為止沒有人找到一種最好的增量序列。有人在大量實驗基礎(chǔ)上推出，它的時間復(fù)雜度為 O()。如果對關(guān)鍵字序列 {6,7,51,2,52,8}進行希爾排序，可以看出希爾排序是不穩(wěn)定的。 第 9章 排 序 交 換 排 序 冒泡排序 冒泡排序 (bubble sort)是一種人們熟知的、最簡單的交換排序方法。在排序過程中，關(guān)鍵字較小的記錄經(jīng)過與其他記錄的對比交換，像水中的氣泡向上冒出一樣，移到序列的首部，故稱此方法為冒泡排序法。 第 9章 排 序 排序的算法思路是： (1) 讓 j取 n至 2， 將 r[j].key與 r[j1].key比較 ， 如果 r[j].keyr[j1].key， 則把記錄 r[j]與 r[j1]交換位置 ， 否則不進行交換 。 最后是 r[2].key與 r[1].key對比 ， 關(guān)鍵字較小的記錄就換到 r[1]的位置上 ， 到此第一趟結(jié)束 。 最小關(guān)鍵字的記錄就像最輕的氣泡冒到頂部一樣換到了文件的前邊 。 (2) 讓 j取 n至 3，重復(fù)上述的比較對換操作，最終 r[2]之中存放的是剩余 n1個記錄 (r[1]除外 )中關(guān)鍵字最小的記錄。 (3) 讓 j取 n至 i+1， 經(jīng)過一系列對比交換之后 ， r[i]之中是剩余若 干 記 錄 中 關(guān) 鍵 字 最 小 的 記 錄 。 (4) 讓 j取 n至 n1， 將 r[n].key與 r[n1].key對比 ， 把關(guān)鍵字較小的記錄交換到 r[n1]之中 。 第