【經(jīng)濟學(xué)】 排序模版課件

1、第9章 排序1第9章 排序根本概念插入排序交換排序選擇排序歸并排序9.1 根本概念目的：實現(xiàn)快速查找定義：調(diào)整原文件中的記錄順序，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其形式化定義描述如下：輸入：n個記錄r1，r2，rn，其相應(yīng)的關(guān)鍵字分別為k1，k2，kn輸出：rl，r2，rn，使得k1k2kn。 (或k1k2kn) /有序升序或者降序9.1 根本概念默認(rèn)的排序數(shù)據(jù)結(jié)構(gòu)：#define MAXSIZE 100 typedef int KeyType；/* 假定關(guān)鍵字類型為整數(shù)類型 */typedef struct KeyType key；/* 關(guān)鍵字項 */ OtherType other

2、；/* 其他項 */DataType；/* 數(shù)據(jù)元素類型 */typedef struct DataType rMAXSIZE +1；/* r0閑置或充當(dāng)前哨站*/ int length；/* 順序表長度 */ SqList；/* 順序表類型 */9.1 根本概念分類內(nèi)排序外排序穩(wěn)定性穩(wěn)定排序不穩(wěn)定排序根本操作比較兩個關(guān)鍵字大小將記錄從一個位置移動到另一個位置9.2 插入排序根本思想通過構(gòu)建有序序列，將待排序的數(shù)據(jù)，在已排好序的序列中從后向前掃描，找到其相應(yīng)位置并進行插入操作。常見的插入排序算法直接插入排序折半插入排序希爾排序 9.2.1 直接插入排序void StraightInsertSo

3、rt(SqList *S)int i，j；for(i=2；ilength；i+) S-r0=S-ri； /*復(fù)制為哨兵*/ j= i-1; while (S-r0.key rj.key) S-rj+1=S-rj； j- ; /*記錄后移*/ S-rj+1=S-r0； /*插入到正確位置*/ 2/89.2.1 直接插入排序空間效率： O(1)一個輔助單元r0時間效率：最好情況：O(n)最壞情況: O(n2)總的比較次數(shù)= 次總的移動次數(shù)= 次一般情況: O(n2)9.2.3 希爾排序舉例: 8194119612351795285841751596281258813541941775119515步

4、長=596419411285835759512811715步長=3步長=1964194112858357595128117159.2.3 希爾排序希爾排序算法描述：1選擇一個步長序列t1，t2，ti，tk，其中titi+1，tk=1；2按步長序列個數(shù)k，對序列進行k趟排序；3每趟排序，根據(jù)對應(yīng)的步長ti，將待排序列分割成假設(shè)干個子序列，分別對各子序列進行直接插入排序。僅當(dāng)步長為1時，整個序列作為一個表來處理，表長度即為整個序列的長度。9.2.3 希爾排序Shell排序算法描述如下：void ShellInsert(SqList *s，int gap) /*一趟增量為gap的插入排序，gap為步

5、長*/int i,j；for(i=gap+1；ilength；i+) if(S-ri.keyri-gap.key) /*小于時，需將ri插入有序表*/ S-r0=S-ri； /*為統(tǒng)一算法設(shè)置監(jiān)視哨*/ for(j=i-gap；j0 & S-r0.keyrj.key；j=j-gap) S-rj+gap=S-rj； /*記錄后移*/ S-rj+gap=S-r0； /*插入到正確位置*/ /* if */9.2.3 希爾排序Shell排序算法描述如下：void ShellSort(SqList *s，int gaps，int t) /*按增量序列g(shù)aps0，1，t-1對順序表S作希爾排序*/int

6、 k；for(k=0；kr2.key，那么將兩個記錄交換，緊接著依次比較r2和r3，直至rn-1與rn為止。這樣一趟將關(guān)鍵字值最大的記錄移至rn位置，第二趟：比較r1至讓rn-1，關(guān)鍵字值次大的記錄移動到第n-1位置，方法同第一趟依次完成第3趟，第4趟，n-1趟，直到所有記錄都完成排序9.3.1 冒泡排序舉例7587689288617796807275876892886177968072688792886192779292968096729687687587617788807292966875617787807288929668617577807287889296616875777280878

7、8929661687572778087889296616872757780878892966168727577808788929661687275778087889296616872757780878892969.3.1 冒泡排序算法描述：void BubbleSort(SqList *s) /* 對順序表S作冒泡排序 */int i,j;for (i=1；ilength-1；i+) /*進行n-1趟排序*/ for (j= 2; jlength-i; j+) if (S-rj.key rj-1.key) S-r0=S-rj；/* S-rj與S-rj-1交換 */ S-rj=S-rj-1; S

8、-rj-1=S-r0; n-1次ni次比較9.3.1 冒泡排序算法空間復(fù)雜度為O(1)總的比較次數(shù)為：總的交換次數(shù)最多為O(n2)，最少為0 平均交換次數(shù)為 : 起泡排序是穩(wěn)定的： S-rj.key rj-1.key交換改進的起泡排序9.3.1 冒泡排序改進后的冒泡排序算法void BubbleSort(SqList *s) /* 對順序表S作冒泡排序 */int i,j;int flag=0；for (i=1; !flag& ilength-1;i+,flag=0) /*進行n-1趟排序*/ for (j= 2; jlength-i; j+) if (S-rj.key rj-1.key) f

9、lag=1; S-r0=S-rj；/* S-rj與S-rj-1交換 */ S-rj=S-rj-1; S-rj-1=S-r0; 9.3.2 快速排序算法思想：將一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬删植浚渲幸痪植坑涗浀年P(guān)鍵字比另一局部記錄的關(guān)鍵字小，然后分別對這兩局部記錄繼續(xù)使用該方法排序，以到達整個序列有序。13 8192 43 6531 57 2675 013 43 31 57 26 0658192 750 13 26 31 43 576575 81 920 13 26 31 43 57 65 75 81 929.3.2 快速排序具體步驟：1. 待排序序列S中任意選擇一個記錄r作為軸值 設(shè)記錄

10、r的關(guān)鍵字為k)；2. 將剩余的記錄分割成兩個子序列L和R,子序列L中的關(guān)鍵字均小于或等于k，子序列R中所含記錄的關(guān)鍵字均大于或等于k；3. 將子序列L中所有記錄放在記錄r左邊，子序列R中所有記錄放在記錄r右邊；4. 對于子序列L和R遞歸進行快速排序，直到子序列中只含有0或1個元素，退出遞歸。9.3.2 快速排序舉例：491438749665849552749lowhigh27lowlowlow74highhigh=high96highhigh4912345678910027143884965964955749.3.2 快速排序一趟快速排序的算法描述int QuickSort1 (SqList

11、 *s, int low, int high) KeyType pivotkey; S-r0=S-rlow; /*以子表的第一個記錄作為軸值記錄*/pivotkey=S-rlow.key; /*取軸值記錄關(guān)鍵字*/while(lowhigh) /*從表的兩端交替地向中間掃描*/ while(lowrhigh.key=pivotkey) high-;S-rlow=S-rhigh; /*將比軸值記錄小的交換到低端*/ While (lowrlow.keyrhigh=S-rlow; /*將比軸值記錄大的交換到高端*/ S-rlow=S-r0; /*軸值支點記錄到位*/return low; /*返回

12、軸值支點記錄所在位置*/9.3.2 快速排序快速排序的遞歸算法描述void QuickSort(SqList *s,int low,int high) /*對順序表S中的子序列rlowhigh作快速排序*/int pivotloc;if(lowhigh) pivotloc= QuickSort1 (S,low,high); /*將待排序序列一分為二*/QuickSort (S,low,pivotloc-1); /*對小于軸值序列實現(xiàn)遞歸排序*/QuickSort (S,pivotloc+1,high); /*對大于軸值序列實現(xiàn)遞歸排序9.3.2 快速排序算法分析最壞情況：每次劃分選取的基準(zhǔn)都是

13、當(dāng)前無序區(qū)中關(guān)鍵字最小或最大的記錄，劃分的結(jié)果是基準(zhǔn)的左邊或右邊為空，劃分前后無序區(qū)的元素個數(shù)減少一個，因此，排序必須做n-1趟，每一趟中需做n-i次比較，所以最大比較次數(shù)如下：9.3.2 快速排序最好情況：每次所取的pivotkey是當(dāng)前無序區(qū)的“中值 ，劃分的結(jié)果是pivotkey的左右兩個無序子區(qū)的長度大致相等設(shè)C(n)表示長度為n的序列快速排序的比較次數(shù)，它等于長度為n的無序區(qū)進行比較次數(shù)n-1，加上對劃分所得的左右兩個無序子區(qū)進行快速排序所需的比較次數(shù)，假設(shè)文件長度n=2k ，k=log2n，有：9.4 選擇排序根本思想：一趟從待排序列中選取一個關(guān)鍵字最小的記錄，即第一趟從n個記錄中

14、選取關(guān)鍵字最小的記錄，第二趟從剩下的n-1個記錄中選取關(guān)鍵字次小的記錄，直到整個序列的記錄選完為止。這樣根據(jù)選取記錄的順序，可得到按關(guān)鍵字有序的序列 常見選擇排序算法簡單項選擇擇排序堆排序9.4.1 簡單項選擇擇排序算法步驟第1趟，從n個待排序記錄中找出關(guān)鍵字最小的記錄與第一個記錄交換； 第2趟，從第二個記錄開始的n-1個待排序記錄中再選出關(guān)鍵字最小的記錄與第二個記錄交換； 第i趟，那么從第i個記錄開始的n-i+1個待排序記錄中選出關(guān)鍵字最小的記錄與第i個記錄交換，直到整個序列有序。9.4.1 簡單項選擇擇排序舉例75876892886177968072t7587689288617796807

15、26175第趟12t6887i123456789103t72874t75925t77886t80927t87888t88969t109.4.1 簡單項選擇擇排序算法描述void SelectSort(SqList *s)for(i=1；ilength；i+) /* 作S-length-1趟選取 */for(j=i+1，t=i；jlength；j+) /* 在i開始的length-i+1條待排序記錄中選關(guān)鍵字最小的記錄 */if (S-rt.keyS-rj.key)t=j； /* t中存放關(guān)鍵字最小的記錄下標(biāo) */tmp=S-rt;S-rt=S-ri;S-ri=tmp; /* 關(guān)鍵字最小的記錄與

16、第i條記錄交換 */9.4.1 簡單項選擇擇排序算法分析：簡單項選擇擇排序第i趟排序中選出關(guān)鍵字最小的記錄，需做n-i次比較，因此總的比較次數(shù)為：輔助空間為O(1) ，簡單項選擇擇排序是不穩(wěn)定的。9.4.2 堆排序人物介紹威廉姆斯JWilliams羅伯特弗洛伊德1936.6.8-2001.9.25自學(xué)成才的計算機科學(xué)家(美國紐約)1978年圖靈獎得主1953年獲得文學(xué)士學(xué)位1958年獲得理科學(xué)士學(xué)位 1965年被卡內(nèi)基梅隆大學(xué)聘為副教授1970年被斯坦福大學(xué)聘為教授 算法，程序設(shè)計語言的邏輯和語義，自動程序綜合，自動程序驗證，編譯器的理論和實現(xiàn)等方面都作出創(chuàng)造性的奉獻。 9.4.2 堆排序算法

17、方面1964年創(chuàng)造了著名的堆排序算法(和J.Williams)以弗洛伊德命名的求最短路的算法 程序設(shè)計方面前后斷言法的創(chuàng)始人 Floyd-Evans Production Language (R0Evans )1962年，完成了Algol 60編譯器的開發(fā) 9.4.2 堆排序堆定義n個關(guān)鍵字序列Kl，K2，Kn稱為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡稱為堆性質(zhì))： (1) kiK2i且kiK2i+1 或(2)KiK2i且kiK2i+1(1i ) 。假設(shè)將此序列所存儲的向量R1.n看做是一棵完全二叉樹的存儲結(jié)構(gòu)，那么堆實質(zhì)上是滿足如下性質(zhì)的完全二叉樹：樹中任一非葉結(jié)點的關(guān)鍵字均不大于(或不小于)其

18、左右孩子(假設(shè)存在)結(jié)點的關(guān)鍵字。 9.4.2 堆排序堆示意圖36 24 85 47 53 30 12 98 47 85 24 36 30 53 98 16 大根堆小根堆9.4.2 堆排序根本思路：對一組待排序的鍵值，首先是把它們按堆的定義排列成一個序列稱為初鍵堆，這就找到了最小鍵值。然后將最小的鍵值取出，用剩下的鍵值再重建堆，便得到次小鍵值，如此反復(fù)進行，直到把全部鍵值排好序為止。堆排序的根本操作：1調(diào)整子樹為堆；2排序。9.4.2 堆排序舉例建堆47 241285 369130535336309147122485012345679185301230128591125312532453245

19、39.4.2 堆排序第n個元素進行篩選的算法描述：void HeapAdjust(SqList *s，int n，int m) int i, j; DataType rc; rc=S-rn；i=n;for(j=2*i；j=m；j=j*2) /* 沿關(guān)鍵字較大的孩子結(jié)點向下篩選 */if(jrj.keyrj+1.key) j=j+1； /* 為關(guān)鍵字較大的元素下標(biāo)*/if(rc.keyS-rj.key) break； /* rc應(yīng)插入在位置i上*/ S-ri=S-rj； i=j； /* 使i結(jié)點滿足堆定義 */S-ri=rc； /* 插入 */9.4.2 堆排序堆排序算法描述：void Heap

20、Sort(SqList *s)int i;for(i=S-length/2；i0；i-) /* 將r1.length建成堆 */HeapAdjust(S，i，S-length)；for(i=S-length；i1；i-)S-r1S-ri； /* 堆頂與堆底元素交換 ,將最大元素移到后面*/HeapAdjust(S，1，i-1) /*將r1.i-1重新調(diào)整為堆*/9.4.2 堆排序算法分析：堆排序適合記錄很多的情形，它的時間復(fù)雜度為O(nlog2n)。堆排序中初始建堆雖然時間復(fù)雜度為O(n)，但每次調(diào)整后面的花費時間很少。堆排序算法中增加了一個輔助空間，輔助空間為O(1)。堆排序時間效率根本與待排序記錄的初始狀態(tài)無關(guān)堆排序是不穩(wěn)定的9.5 歸并排序分治法快速排序快速排序?qū)⒋判蛐蛄蟹指畛蓛蓚€子序列，然后分別遞歸調(diào)用對兩個子序列進行快速排序，它側(cè)重于分割過程。 歸并排序歸并排序是將原始序列分成兩個子序列，然后分別對每個子序列執(zhí)行遞歸調(diào)用，最后再將已排好序的子序列合并，側(cè)重于歸并過程。 9.5 歸并排序歸并排序思路：歸并的含義是將