第八章-排序要點

第八章排序[內(nèi)容提要]：五類內(nèi)部排序方法（插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序）的基本思想、排序過程、實現(xiàn)的算法、算法的效率分析及排序的特點；各種排序方法的比較和選擇；最終簡潔介紹外部排序。

1排序的功能是將一個數(shù)據(jù)元素(記錄)的隨意序列，重新排列成一個按關鍵字有序的序列。排序的定義2排序的分類按待排序記錄所在位置內(nèi)部排序：待排序記錄存放在內(nèi)存外部排序：排序過程中需對外存進行訪問的排序按排序依據(jù)原則插入排序：干脆插入排序、折半插入排序、希爾排序交換排序：冒泡排序、快速排序選擇排序：簡潔選擇排序、堆排序歸并排序：2-路歸并排序3排序的基本操作比較兩個關鍵字大小將記錄從一個位置移動到另一個位置4定義待排序的記錄的數(shù)據(jù)類型為：typedefstruct{intkey;elemtypedata;}redtype;redtyper[n];排序?qū)ο蟮臄?shù)據(jù)類型5基本思想：每步將一個待排序的記錄，按其關鍵字值的大小插入到前面已經(jīng)排序的文件中適當?shù)奈恢蒙希钡饺坎逋隇橹埂２迦肱判?基本思路是依次把待排序的記錄逐一按其關鍵字的大小插入到一個已經(jīng)排好序的有序序列中去，直到全部的記錄插完為止。得到一個新的有序序列。插入排序——干脆插入排序7例49386597761327i=238(3849)6597761327i=365(384965)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序結(jié)果：比較次數(shù)移動次數(shù)211021.106565插入排序——干脆插入排序8（1）設置監(jiān)視哨r[0]，將待插入記錄的值賦給r[0];（2）設置起先查找的位置j；（3）在數(shù)組中進行搜尋，搜尋中將第j個記錄后移，直至r[0].key≥r[j].key為止（4）將r[0]插入在r[j+1]的位置上干脆插入排序算法9按平均比較次數(shù)計算，將n個記錄進行干脆插入排序所需的平均比較次數(shù)為：干脆插入排序算法分析干脆插入排序的時間困難度為O(n2)?？臻g困難度為O（1）干脆插入排序是一種穩(wěn)定的排序方法。10插入排序——希爾排序希爾排序的作法是：選定第一個增量d1<n，把全部記錄按此值從第一個記錄起進行分組，全部相距為d1的記錄作為一組，先在各組內(nèi)進行插入排序，然后減小間隔，取其次個增量d2<d1，重復上述分組和排序過程，直至增量值di=1為止，即全部的記錄放在同一組內(nèi)排序。11取d3=1三趟分組：1327485544938659776三趟排序：4132738484955657697例初始：4938659776132748554一趟排序：13

27

48

55

4

49

38

65

97

76二趟排序：13

4

48

38

27

49

55

65

97

76取d1=5一趟分組：49

38

65

97

76

13

27

48

55

4取d2=3二趟分組：13

27

48

55

4

49

38

65

97

76121)外循環(huán)以各種不同的間隔距離d進行排序，直到d=1為止；2)其次重循環(huán)是在某一個d值下對各組進行排序，若在某個d值下發(fā)生了記錄的交換，則需接著第三重循環(huán)循環(huán)，直至各組內(nèi)均無記錄的交換為止。即各組內(nèi)已完成排序任務；3)第三重循環(huán)是從第一個記錄起先，按某個d值為間距進行組內(nèi)比較。若有逆序，則進行交換。插入排序——希爾排序算法13主要特點是每一趟以不同的增量進行插入排序。當d較大時，被移動的記錄是跳動式進行的。到最終一趟排序時(d=1)，很多記錄已經(jīng)有序，不須要多少移動，所以能提高了排序的速度。希爾排序是不穩(wěn)定的排序方法。希爾排序算法分析14交換排序交換排序是通過兩兩比較待排序記錄的關鍵值，交換不滿足依次的那些偶對，直到全部滿足為止。15交換排序——冒泡排序?qū)⒌谝粋€記錄的關鍵字與其次個記錄的關鍵字進行比較，若為逆序r[1].key>r[2].key，則交換；然后比較其次個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結(jié)果關鍵字最大的記錄被安置在最終一個記錄上。對前n-1個記錄進行其次趟冒泡排序，結(jié)果使關鍵字次大的記錄被安置在第n-1個記錄位置。重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止。16例4938659776132730初始關鍵字3849657613273097第一趟38496513273076第二趟384913273065第三趟3813273049第四趟13273038第五趟132730第六趟38497697139727973097137676762730136527653065131349493049273827383038交換排序——冒泡排序17由上述算法可見，當時始序列中記錄已按關鍵字次序排好序，則只須要進行一趟排序，在排序過程中只須要進行n-1次比較，記錄移動次數(shù)為0；反之，若初始序列中記錄按逆序排列，若待排序的序列有n個記錄，最多進行n-1趟排序，最大比較次數(shù)為交換記錄時移動記錄的次數(shù)也約為3n2/2次，故總的時間困難度為O(n2)。冒泡排序是穩(wěn)定的。冒泡排序算法分析18交換排序——快速排序基本思想：通過一趟排序，將待排序記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄進行排序，以達到整個序列有序19對r[s……t]中記錄進行一趟快速排序，附設兩個指針i和j，設樞軸記錄rp=r[s]，x=rp.key初始時令i=s,j=t首先從j所指位置向前搜尋第一個關鍵字小于x的記錄，并和rp交換再從i所指位置起向后搜尋，找到第一個關鍵字大于x的記錄，和rp交換重復上述兩步，直至i==j為止再分別對兩個子序列進行快速排序，直到每個子序列只含有一個記錄為止快速排序的排序過程20例初始關鍵字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分別進行快速排序：(13)27(38)49(5065)76(97)快速排序結(jié)束：13273849

506576974927ijijij4965ji1349ij4997ij快速排序的排序過程211）確定第一個記錄為基準記錄r[t]，先從j所指示的位置起向前掃描，當r[t].key>r[j].key時，交換r[t].key和r[j].key，使關鍵字值比基準記錄的關鍵字值小的記錄交換到前面；2）從i所指示的位置起向后掃描，直到r[t].key<r[i].key,交換r[t].key和r[i].key，使關鍵字值比基準記錄的關鍵字值大的記錄交換到后面；3）重復（1）和（2），直至i=j為止完成一趟排序；4）只要t<w，重復（1）至（3）分別對基準記錄兩邊的部分進行排序?？焖倥判虻呐判蛩惴?2快速排序平均時間困難度為O(nlog2n)。最壞狀況下時間困難度為O(n2)，快速排序所需的比較次數(shù)反而最多?？焖倥判蚍ú环€(wěn)定?？焖倥判蝽氁粋€?？臻g來實現(xiàn)遞歸。棧的最大深度為log2n」＋1，所需棧空間為O(log2n)。最壞狀況下，遞歸深度為n，所需棧空間為O(n)。快速排序的排序算法分析23

選擇排序選擇排序是指每次從待排序的記錄中選出關鍵字值最?。ɑ蜃畲螅┑挠涗洠来畏旁谝雅判虻挠行蛐蛄兄?，直到全部排完。選擇排序主要包括簡潔選擇排序和堆排序兩種。24選擇排序——簡潔選擇排序首先通過n-1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換再通過n-2次比較，從剩余的n-1個記錄中找出關鍵字次小的記錄，將它與其次個記錄交換重復上述操作，共進行n-1趟排序后，排序結(jié)束25例初始：[49386597761327]kjjjjjjkki=11349一趟：13[386597764927]i=2kkjjjjj2738二趟：13

27[6597764938]三趟：13

27

38[97764965]四趟：13

27

38

49[769765]五趟：13

27

38

49

65[9776]六趟：13

27

38

49

65

76[97]排序結(jié)束：13

27

38

49

65

76

9726(1)查找待排序序列中最小的記錄，并將它和該區(qū)間第一個記錄交換；(2)重復（1）到第n-1次排序后結(jié)束簡潔選擇排序算法27簡潔選擇排序所須要的總的比較次數(shù)為O(n2)。當時始文件是有序時，最小移動記錄次數(shù)等于0，而當時始文件是逆序時，每次都要交換記錄。干脆選擇排序是不穩(wěn)定的.簡潔選擇排序算法分析28選擇排序——堆排序的引入堆排序是簡潔選擇排序的改進。用干脆選擇排序從n個記錄中選出關鍵字值最小的記錄要做n-1次比較，然后從其余n-1個記錄中選出最小者要作n-2次比較。明顯，相鄰兩趟中某些比較是重復的。為了避開重復比較，可以接受樹形選擇排序比較。29(a)求出最小關鍵字3(b)求出次小關鍵字11圖8.8樹形選擇排序30樹形選擇排序總的比較次數(shù)為O(nlog2n)，與干脆選擇排序比較，削減了比較次數(shù)，但須要增加額外的存儲空間存放中間比較結(jié)果和排序結(jié)果。選擇排序——堆排序的引入31n個元素的序列(k1,k2,……kn)，當且僅當滿足下列關系時，稱之為堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1例（96，83，27，38，11，9）例（13，38，27，50，76，65，49，97）962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個元素的最小值或最大值堆的定義32

堆排序的基本思路：對一組待排序的記錄序列，先將其關鍵字按堆的定義排列－個序列（稱初建堆），找到了最?。ㄗ畲螅╆P鍵字，將其取出。用剩余的n-1個元素再重建堆，便可得到次?。ù未螅┲?。如此反復執(zhí)行，直到全部關鍵字排好序為止。

堆排序的基本思路33例13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：132738344965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：132738495065357665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：132738495065769736堆排序的關鍵問題堆排序需解決的兩個問題：如何由一個無序序列建成一個堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個新的堆？37堆排序的關鍵問題其次個問題解決方法——篩選方法：輸出堆頂元素之后，以堆中最終一個元素替代之；然后將根結(jié)點值與左、右子樹的根結(jié)點值進行比較，并與其中小者進行交換；重復上述操作，直至葉子結(jié)點，將得到新的堆，稱這個從堆頂至葉子的調(diào)整過程為“篩選”。第一個問題解決方法——建堆方法：從無序序列的第n/2個元素（即此無序序列對應的完全二叉樹的最終一個非終端結(jié)點）起，至第一個元素止，進行反復篩選。38例：含8個元素的無序序列（49，38，65，97，76，13，27，50），建堆過程：4965382713769750496538271376509749133827657650974913382765765097132738496576509739堆排序只須要一個記錄大小的協(xié)助空間。堆排序算法的時間困難度為O(nlogn)。堆排序是一種不穩(wěn)定的排序方法。堆排序的算法及分析40歸并排序

歸并排序：把兩個或多個有序表進行合并，得到一個新的有序表。將兩個有序子文件合并成一個有序文件，稱為二路歸并。41設初始序列含有n個記錄，則可看成n個有序的子序列，每個子序列長度為1兩兩合并，得到n/2個長度為2或1的有序子序列再兩兩合并，……如此重復，直至得到一個長度為n的有序序列為止

2-路歸并排序過程42例初始關鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：132738496576972-路歸并排序過程432-路歸并排序的關鍵問題

合并是歸并排序的核心，即將兩個首尾相連的有序子表合并成一個有序子表。在合并的基礎上進行一趟排序，在一趟排序的基礎上完成多趟排序。

441）設數(shù)組r中第一個有序子表從第h個記錄起先至第m個記錄為止。即r[h]到r[m]，其次個有序子表從第m+1個記錄起先到第w個記錄為止，即r[m+1]到r[w]，最終形成的有序表為r[h]到r[w]；2）設置I,j,k分別指向（1）中所指的三個有序表的第一個單元。3）比較r[i]和r[j]的關鍵字值的大小，若r[i].key≤r[j].key，則將第一個有序子表的記錄r[i]復制到數(shù)組a[k]中，并使i++,k++;4）否則，將其次個有序子表的記錄r[j]復制到a[k]中，并使j++,k++。依次類推，直到全部記錄復制到r[h]到r[w]中。合并的算法45

把數(shù)組r中的長度為s的相鄰有序子表兩兩合并，歸并成一個長度為2s的有序子表，存于t數(shù)組中。一趟歸并的算法46思路是：第一趟有序子表長s為1，以后每趟s加倍。第一趟將r數(shù)組進行歸并后存于t數(shù)組；其次趟將t數(shù)組歸并后存于r數(shù)組；依次類推，若歸并的趟數(shù)為奇數(shù)，需從t數(shù)組復制到r數(shù)組。多趟合并的算法47歸并排序的總的時間困難度為O(nlog2n)。歸并排序須要的附加存儲空間為O(n)，所需協(xié)助空間較大。二路歸并排序是穩(wěn)定的。歸并排序算法分析48*基數(shù)排序基數(shù)排序是和前面所述的各種排序方法完全不同的一種排序方法。前面介紹的幾種排序方法，都是依據(jù)關鍵字之間的比較和移動記錄來實現(xiàn)的，基數(shù)排序不須要進行記錄關鍵字間的比較，而是依據(jù)組成關鍵字的各位值，即借助于多關鍵字排序的思想，用“安排”和“收集”的方法進行排序。49多關鍵字的排序

假設有n個記錄的序列{R1,R2,…，Rn}每個記錄Ri中含有d個關鍵字(Ki0,Ki1,…,Kid-1),則稱上述記錄序列對關鍵字(Ki0,Ki1,…,Kid-1)有序是指：對于序列中隨意兩個記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)其中K0被稱為“最主”位關鍵字，Kd-1被稱為“最次”位關鍵字。50實現(xiàn)多關鍵字排序通常有兩種作法:

最高位優(yōu)先MSD法：先對K0進行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對K1進行排序，…，依次類推，直至最終對最次位關鍵字排序完成為止。最低位優(yōu)先LSD法：先對Kd-1進行排序，然后對Kd-2進行排序，依次類推，直至對最主位關鍵字K0排序完成為止。排序過程中不須要依據(jù)“前一個”關鍵字的排序結(jié)果，將記錄序列分割成若干個(“前一個”關鍵字不同的)子序列。51例如:學生記錄含三個關鍵字:系別、班號和班內(nèi)的序列號，其中以系別為最主位關鍵字。LSD的排序過程如下:無序序列3,2,301,2,153,1,202,3,182,1,20對K2排序1,2,152,3,183,1,202,1,203,2,30對K1排序3,1,202,1,201,2,153,2,302,3,18對K0排序1,2,152,1,202,3,183,1,203,2,3052比較MSD法和LSD法，一般來講，LSD法要比MSD法來得簡潔，因為LSD法是從頭到尾進行若干次安排和收集，執(zhí)行的次數(shù)取決于構(gòu)成關鍵字值的成分為多少；而MSD法則要處理各序列與子序列的獨立排序問題，就可能困難一些。MSD法和LSD法的比較53鏈式基數(shù)排序

假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按LSD法進行排序時，可以接受“安排-收集”的方法，其好處是不須要進行關鍵字間的比較。對于數(shù)字型或字符型的單關鍵字，可以看成是由多個數(shù)位或多個字符構(gòu)成的多關鍵字，此時可以接受這種“安排-收集”的方法進行排序，稱作基數(shù)排序法。54鏈式基數(shù)排序

在計算機上實現(xiàn)基數(shù)排序時，應接受鏈表作存儲結(jié)構(gòu)，即鏈式基數(shù)排序，具體作法為：待排序記錄以指針相鏈，構(gòu)成一個鏈表；“安排”時，按當前“關鍵字位”所取值，將記錄安排到不同的“鏈隊列”中，每個隊列中記錄的“關鍵字位”相同；“收集”時，按當前關鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;對每個關鍵字位均重復2)和3)兩步。55例如：p→369→367→167→239→237→138→230→139第一次安排得到f[0]→230←r[0]f[7]→367→167→237←r[7]f[8]→138←r[8]f[9]→369→239→139←r[9]第一次收集得到p→230→367→167→237→138→368→239→139鏈式基數(shù)排序

56其次次安排得到f[3]→230→237→138→239→139←r[3]f[6]→367→167→368←r[6]其次次收集得到p→230→237→138→239→139→367→167→368第三次安排得到f[1]→138→139→167←r[1]f[2]→230→237→239←r[2]f[3]→367→368←r[3]第三次收集之后便得到記錄的有序序列p→138→139→167→230→237→239→367→36857鏈式基數(shù)排序算法對數(shù)據(jù)進行d趟掃描，每趟需時間O(n+j)。因此總的計算時間為O(d(n+j))。對于不同的基數(shù)j所用的時間是不同的。當n較大或d較小時，這種方法較為節(jié)約時間?；鶖?shù)排序適用于鏈式存儲結(jié)構(gòu)的記錄的排序，它要求的附加存儲量是j個隊列的頭、尾指針。所以，須要O(n+j)協(xié)助空間?；鶖?shù)排序是一種穩(wěn)定的排序方法。

鏈式基數(shù)排序分析

58各種內(nèi)部排序方法性能比較方法平均時間最壞情況輔助存儲簡單排序O(n2)O(n2)O(1)快速排序O(nlog2n)O(n2)O(nlog2n)堆排序O(nlog2n)O(nlog2n)O(1)歸并排序O(nlog2n)O(nlog2n)O(n)基數(shù)排序O(d(n+j))O(d(n+j))O((n+j)591）從平均時間而言：快速排序最佳。但在最壞狀況下時間性能不如堆排序和歸并排序。2）從算法簡潔性看：由于干脆選擇排序、干脆插入排序和冒泡排序的算法比較簡潔，將其認為是簡潔算法，都包含在上圖中的“簡潔排序”中。對于希爾排序、堆排序、快速排序和歸并排序算法，其算法比較困難，認為是困難排序。3）從穩(wěn)定性看：干脆插入排序、冒泡排序和歸并排序是穩(wěn)定的；而希爾排序、干脆選擇排序、快速排序和堆排序是不穩(wěn)定排序。4）從待排序的記錄數(shù)n的大小看，n較小時，宜接受簡潔排序；而n較大時宜接受改進排序。各種內(nèi)部排序方法性能比較60（1）當待排序記錄數(shù)n較大時，若要求排序穩(wěn)定，則接受歸并排序。（2）當待排序記錄數(shù)n較大，關鍵字分布隨機，而且不要求穩(wěn)定時，可接受快速排序；（3）當待排序記錄數(shù)n較大，關鍵字會出現(xiàn)正、逆序情形，可接受堆排序（或歸并排序）。（4）當待排序記錄數(shù)n較小，記錄已接近有序或隨機分布時，又要求排序穩(wěn)定，可接受干脆插入排序。（5）當待排序記錄數(shù)n較小，且對穩(wěn)定性不作要求時，可接受干脆選擇排序。選擇排序的方法61*外部排序簡介在實際問題中，常常會遇到輸入文件中記錄的數(shù)量很大，計算機的內(nèi)存不能容納時，排序過程必需借助外部存儲器才能完成，這時的排序就稱為外部排序。62外存信息的存取——磁帶