【正文】 排序是指將一組數(shù)據(jù)元素按某個(gè)數(shù)據(jù)項(xiàng)值的大小排列成一個(gè)有序序列的過程 。 排序是計(jì)算機(jī)程序設(shè)計(jì)中經(jīng)常使用的一種重要操作 ， 是組織數(shù)據(jù)和處理數(shù)據(jù)的最基本最重要的運(yùn)算之一 。 排序被廣泛應(yīng)用于數(shù)據(jù)處理 、 情報(bào)檢索 、 商業(yè)金融等許多領(lǐng)域 。 第 9章 排序 基本概念 插入排序 交換排序 選擇排序 歸并排序 分配排序（基數(shù)排序） 1． 記錄 、 關(guān)鍵碼和排序表： 記錄： 數(shù)據(jù)元素 關(guān)鍵碼 （ 或排序碼 ） ：作為排序依據(jù)的數(shù)據(jù)項(xiàng)稱為數(shù)據(jù)元素的關(guān)鍵碼 。 排序表：若干個(gè) （ n個(gè) ） 排序紀(jì)錄組成的集合 。 排序表也稱成為文件 ， 主要操作是排序 。 2． 非遞減序列 、 遞減序列 、 非遞增序列 、 遞增有序 3． 穩(wěn)定排序和非穩(wěn)定排序 穩(wěn)定排序 ：記錄的相對(duì)位置在排序前后不發(fā)生變化 不穩(wěn)定排序： 4．內(nèi)部排序和外部排序 待排序的表完全放在內(nèi)存中 稱為 內(nèi)排序 5．對(duì)排序方法的評(píng)價(jià) 空間性能：除排序表以外的內(nèi)存占用情況。 時(shí)間性能： 比較關(guān)鍵碼的次數(shù) ， 數(shù)據(jù)移動(dòng)的次數(shù) 。 它們往往是排序表規(guī)模（ n）的函數(shù) 6. 記錄和排序表的數(shù)據(jù)結(jié)構(gòu) 在本章的討論中，除特殊聲明外，一般采用 順序結(jié)構(gòu) 存儲(chǔ)排序表。 記錄和排序表的類型定義如下： define MAXNUM … /* MAXNUM 為足夠大的數(shù) */ typedef struct { keytype key。 /*關(guān)鍵碼字段 */ …… /*其它信息 */ } datatype。 /*記錄類型 RecNode*/ datatype R[MAXNUM]。 /*定義排序表 的存儲(chǔ) */ 如不加特別說明，排序表中的記錄 R1… Rn存放在R[1]… R[n]分量中， R[0]分量閑置或做監(jiān)視哨 （ n是排序表中記錄的個(gè)數(shù)）。 第 9章 排序 基本概念 插入排序 交換排序 選擇排序 歸并排序 分配排序（基數(shù)排序） 1 直接插入排序 2 折半插入排序 3 *表插入排序 3 希爾排序 插入排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表的適當(dāng)位置，直到全部記錄插入完成，整個(gè)表有序?yàn)橹埂? 直接插入排序 直接插入排序是一種簡單的插入排序方法 ， 基本思想為：在 R[1]至 R[i1]長度為 i1的子表已經(jīng)有序的情況下 ， 將 R[i]插入 ， 得到 R[1]至 R[i]長度為 i 的子表有序 ， 這樣通過 n1趟 （ i=2..n） 之后 ， R[1]至 R[n]有序 。 例如 ，對(duì)于以下序列（為簡便起見， 每一個(gè)記錄只列出其排序碼 ，用排序碼代表記錄）： [ 10 18 20 36 60 ] 25 30 18 12 56 其中，前 5個(gè)記錄組成的子序列是有序的，這時(shí)要將第 6個(gè)記錄插入到前 5個(gè)記錄組成的有序子序列中去，得到一個(gè)含有 6個(gè)記錄的新有序序列。完成這個(gè)插入首先需要找到插入位置： 202536，因此 25應(yīng)插入到記錄 20和記錄 36之間，從而得到以下新序列： [ 10 18 20 25 36 60] 30 18 12 56 這就是一趟直接插入排序的過程。 直接插入排序：僅有一個(gè)記錄的表總是有序的 ， 因此 ， 對(duì) n個(gè)記錄的表 ， 可從第二個(gè)記錄開始直到第 n個(gè)記錄 ， 逐個(gè)向有序表中進(jìn)行插入操作 ， 從而得到 n個(gè)記錄按關(guān)鍵碼有序的表 。 R[0] R[1] R[2] R[3] R[4] R[5] R[6] R[7] R[8] R[9] R[10] 初始 : 36 20 18 10 60 25 30 18 12 56 i=2 ： (20) ( 20 36) 18 10 60 25 30 18 12 56 i=3 ： (18) ( 18 20 36) 10 60 25 30 18 12 56 i=4 ： (10) (10 18 20 36 ) 60 25 30 18 12 56 …… i=7 ： (30) (10 18 20 25 30 36 60) 18 12 56 i=8 ： (18) (10 18 18 20 25 30 36 60) 12 56 【 算法 91】 直接插入排序 void D_InsertSort(datatype R[ ], int n) { /*對(duì)排序表 R[1]..R[n]進(jìn)行直接插入排序， n是記錄的個(gè)數(shù) */ for(i=2。 i=n。 i++) if (R[i].keyR[i1].key) {R[0]=R[i]。 /*將 R[i]插入 R[1].. R[i1]中， R[0]為監(jiān)測(cè)哨 */ for(j=i1。 R[0].keyR[j].key。 j) R[j+1]=R[j]。 /*后移記錄 */ R[j+1]=R[0]。 /*插入到合適位置 */ } } 性能分析 空間性能 ：僅用了一個(gè)輔助單元 R[0]作為監(jiān)視哨，空間復(fù)雜度為 O(1)。 時(shí)間性能 ：向有序表中逐個(gè)插入記錄的操作，進(jìn)行了 n?1趟，每趟操作分為 比較 關(guān)鍵碼和 移動(dòng) 記錄，而比較的次數(shù)和移動(dòng)記錄的次數(shù)取決于初始序列的排列情況 。分三種情況討論： )1(2111??? ???nnjnjnnnjnj2)1(21)2(11????? ???總比較次數(shù) 總移動(dòng)次數(shù) (2) 最壞情況下 ： 即第 j趟操作，插入記錄需要同前面的 j個(gè)記錄進(jìn)行 j次關(guān)鍵碼比較，移動(dòng)記錄的次數(shù)為 j+2次。 (1) 最好情況下 ： 即待排序列已按關(guān)鍵碼有序，每趟操作只需 1次比較， 0次移動(dòng)。即： 總比較次數(shù) = n1次 總移動(dòng)次數(shù) = 0次 (3)平均情況下： 即第 j趟操作，插入記錄大約同前面的 j/2個(gè)記錄進(jìn)行關(guān)鍵碼比較，移動(dòng)記錄的次數(shù)為 j/2+2次。 總比較次數(shù) 總移動(dòng)次數(shù) 211 41)1(412 nnnjnj???? ???211 412)1(41)22( nnnnjnj?????? ??? 由此，直接插入排序的時(shí)間復(fù)雜度為 O(n2)。 直接插入排序是一個(gè)穩(wěn)定的排序方法。 直接插入排序也 可以在鏈?zhǔn)浇Y(jié) 構(gòu)上實(shí)現(xiàn)。 折半插入排序 直接插入排序的基本操作是向有序表中插入一個(gè)記錄 ， 在直接插入排序中 ， 插入位置的確定是通過對(duì)有序表中關(guān)鍵碼的順序比較得到的 。 既然是在有序表中確定插入位置 ， 因此在尋找 R[i]的插入位置時(shí) ， 就可以采用折半查找的方法 ， 用折半查找方法查找 R[i]的插入位置 ， 再將 R[i]插入進(jìn)去 ， 使得 R[i]到 R[i]有序 ， 這種方法就是折半插入排序 。 【 算法 92】 折半插入排序算法 void B_InsertSort(datatype R[ ], int n) { /* 對(duì)排序表 R[1]..R[n]作折半插入排序 , n是記錄的個(gè)數(shù) */ for(i=2。 i=n。 i++) { R[0]=R[i]。 /* 保存待插入元素 */ low=1。 high=i?1。 /* 設(shè)置初始區(qū)間 */ while(low=high) /* 該循環(huán)語句完成確定插入位置 */ { mid=(low+high)/2。 if(R[0].keyR[mid].key) low=mid+1。 /* 插入位置在高半?yún)^(qū)中 */ else high=mid1。 /* 插入位置在低半?yún)^(qū)中 */ } for(j=i1。j=high+1。j) /* high+1為插入位置 */ R[j+1]=R[j]。 /* 后移元素，留出插入空位 */ R[high+1]=R[0]。 /* 將元素插入 */ } } 時(shí)間效率 確定插入位置所進(jìn)行的折半查找 ， 定位一個(gè)關(guān)鍵碼的位置需要 比較次數(shù) 至多為 次 ， 所以比較次數(shù)時(shí)間復(fù)雜度為 O (nlog2n)。 相對(duì)直接插入排序 ， 折半插入排序只能減少關(guān)鍵字間的比較次數(shù) ， 而移動(dòng)記錄的次數(shù)和直接插入排序相同 ， 故時(shí)間復(fù)雜度仍為 O(n2)。 折半插入排序是一個(gè)穩(wěn)定的排序方法 。 折半插入排序只適合于順序存儲(chǔ)的排序表 。 ? ?)1(lo g 2 ?n 希爾排序 又稱為 “ 縮小增量排序 ” 。 是 1959年由 的 基本思想： 先選取一個(gè)小于 n的整數(shù) di（稱之為 步長 ），然后把排序表中的 n個(gè)記錄分為 di個(gè)組，從第一個(gè)記錄開始，間隔為 di的記錄為同一組 ，各組內(nèi)進(jìn)行直接插入排序，一趟之后，間隔 di的記錄有序，隨著有序性的改善，減小步長 di（排序子表變大），重復(fù)進(jìn)行， 直到 di=1（全部記錄成為一個(gè)排序表），使得間隔為 1的記錄有序，也就使整體達(dá)到了有序。 步長為 1時(shí)就是前面講的直接插入排序。 例： 排序列表為： 39,80,76,41,13,29,50,78,30,11,100,7,41,86 步長因子分別取 1， 則排序過程如下： 39 80 76 41 13 29 50 78 30 11 100 7 41 86 P=5 間隔為 5的子序列分別為： {39， 29， 100}， {80， 50， 7}，{76， 78， 41}， {41， 30， 86}， {13， 11}。 第一趟排序結(jié)果 ， 使得間隔為 5的字表有序： 29 7 41 30 11 39 50 76 41 13 100 80 78 86 P=3 子序列分別為 :{29,30,50,13,78}， {7,11,76,100,86}， {41,39,41,80}。 第二趟排序結(jié)果： 13 7 39 29 11 41 30 76 41 50 86 80 78 100 P=1 此時(shí) ， 序列 “ 基本有序 ” ， 對(duì)其進(jìn)行直接插入排序 ， 得到最終結(jié)果： 7 11 13 29 30 39 41 41 50 76 78 80 86 100 【 算法 94】 希爾排序的算法 void ShellSort(datatype R[ ], int n, int d[ ], int t) { /*按增量序列 d[0], d[1]… d[t ?1]對(duì)排序表 R[1]..R[n]進(jìn)行希爾排序 */ int i,j,k,h。 for(k=0。 kt。 k++) { h=d[k]。 /*本趟的增量 */ for(i=h+1。 i=n。 i++) if(R[i].keyR[ih].key) /*小于時(shí)，需插入有序表 */