1、1 、交換式排序2、選擇式排序3、插入式排序4、歸并排序5、各種內(nèi)排方法比較第十一章 排序排序：將一個(gè)數(shù)據(jù)元素的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。 數(shù)據(jù)表: 它是待排序數(shù)據(jù)對象的有限集合。主關(guān)鍵字: 數(shù)據(jù)對象有多個(gè)屬性域, 即多個(gè)數(shù)據(jù)成員組成, 其中有一個(gè)屬性域可用來區(qū)分對象, 作為排序依據(jù)，稱為關(guān)鍵字。也稱為排序碼。排序方法的穩(wěn)定性: 如果在對象序列中有兩 個(gè)對象ri和rj, 它們的關(guān)鍵字ki = kj , 且在排序之前, 對象ri排在rj前面。如果在排序之后, 對象ri仍在對象rj的前面, 則稱這個(gè)排序方法是穩(wěn)定的, 否則稱這個(gè)排序方法是不穩(wěn)定的。如記錄對應(yīng)關(guān)鍵字序列為：8，7，

2、24，8，19使用某排序算法得到的序列：7，8，8，19，24則這種排序方法是穩(wěn)定的使用某排序算法得到的序列：7，8，8，19，24則這種排序方法是不穩(wěn)定的內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象數(shù)量太大，不能同時(shí)存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動(dòng)的排序。排序的時(shí)間開銷: 排序的時(shí)間開銷是衡量算法好壞的最重要的標(biāo)志。排序的時(shí)間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動(dòng)次數(shù)來衡量。通常，在排序的過程中需進(jìn)行下列兩種基本操作： (1)比較兩個(gè)關(guān)鍵字的大?。?(2)將記錄從一個(gè)位置移動(dòng)至另一個(gè)位置。待排序的記錄序列可有下

3、列三種存儲方式： (1)待排序的一組記錄存放在地址連續(xù)的一組存儲單元上。 (2)一組待排序記錄存放在靜態(tài)鏈表中，記錄之間的次序關(guān)系由指針指示，則實(shí)現(xiàn)排序不需要移動(dòng)記錄，僅需修改指針即可； (3)待排序記錄本身存儲在一組地址連續(xù)的存儲單元內(nèi)，同時(shí)另設(shè)一個(gè)指示各個(gè)記錄存儲位置的地址向量，在排序過程中不移動(dòng)記錄本身，而移動(dòng)地址向量中這些記錄的“地址”，在排序結(jié)束之后再按照地址向量中的值調(diào)整記錄的存儲位置。內(nèi)排序分類依不同原則交換式排序、選擇式排序、插入式排序、歸并排序、基數(shù)排序。依所須工作量簡單排序-時(shí)間復(fù)雜度O(n2)先進(jìn)排序方法-時(shí)間復(fù)雜度O(n logn)基數(shù)排序-時(shí)間復(fù)雜度O(d*n)11.

4、2 交換式排序 基本思想:兩兩比較待排序?qū)ο蟮年P(guān)鍵字,如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之,直到所有對象都排好序?yàn)橹?。一、起泡排?(Bubble Sort) 基本方法： 先將第一個(gè)記錄的關(guān)鍵字和第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，如果前者比后者大，則將兩個(gè)記錄交換。然后比較第二個(gè)和第三個(gè)記錄的關(guān)鍵字，依次類推直到第n-1個(gè)記錄和第n個(gè)記錄進(jìn)行比較交換完，這稱為第一趟冒泡。經(jīng)過一趟冒泡后，關(guān)鍵字最大的記錄就被交換到了第n個(gè)位置。然后，對前n-1個(gè)記錄進(jìn)行同樣的操作，則關(guān)鍵字是第二大的記錄就被交換到了第n-1個(gè)位置上。重復(fù)以上過程，每趟負(fù)責(zé)排好一個(gè)記錄，經(jīng)過n-1趟后n個(gè)記錄中有n-

5、1個(gè)記錄被排好，剩下的一個(gè)記錄不必再排了，至此n個(gè)記錄全部排好。 210825492516初始關(guān)鍵字214925251608第一趟排序214925251608第四趟排序214925251608第二趟排序214925251608第三趟排序214925251608第五趟排序起泡排序的過程最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1 i n) 做 n- i 次關(guān)鍵字比較, 執(zhí)行 n-i 次對象交換。這樣在最壞情形下總的關(guān)鍵字比較次數(shù)KCN和交換次數(shù)RMN為：起泡排序是一個(gè)穩(wěn)定的排序方法。時(shí)間復(fù)雜度為O(n2)。二、快速排序 (Quick Sort)基本思想:是任取待排序?qū)ο笮蛄兄械哪硞€(gè)對象 (例如

6、取第一個(gè)對象) 作為基準(zhǔn), 按照該對象的關(guān)鍵字大小,將整個(gè)對象序列劃分為左右兩個(gè)子序列： 左側(cè)子序列中所有對象的關(guān)鍵字都小于基準(zhǔn)對象的關(guān)鍵字右側(cè)子序列中所有對象的關(guān)鍵字都大于基準(zhǔn)對象的關(guān)鍵字基準(zhǔn)對象則排在這兩個(gè)子序列中間(這也是該對象最終應(yīng)安放的位置)。然后分別對這兩個(gè)子序列重復(fù)施行上述方法，直到所有的對象都排在相應(yīng)位置上為止?；鶞?zhǔn)對象也稱為樞軸（或支點(diǎn)）記錄。一趟快速排序的具體做法是： 設(shè)兩個(gè)指針low和high，設(shè)樞軸記錄的關(guān)鍵字為key。 首先從high所指位置起向前搜索找到第一個(gè)關(guān)鍵字小于key的記錄，使high和key的值交換。 再移動(dòng)到low所在位置，然后從low所指位置起向后搜索

7、，找到第一個(gè)關(guān)鍵字大于key的記錄移動(dòng)到high所指位置，使low和key的值交換。 重復(fù)這兩步直至low=high為止?？焖倥判虻倪^程21key2108254925*16初始關(guān)鍵字lowhigh08254925*1621一次交換lowhigh08254925*1621二次交換highlow08254925*1621三次交換lowhigh08254925*1621四次交換highlow08254925*1621完成一趟排序lowhigh08254925*1621完成一趟排序分別進(jìn)行快速排序08254925*1621有序序列08254925*1621 算法實(shí)現(xiàn)過程中，先將基準(zhǔn)記錄保存在r0位置上

8、，排序過程中只作rlow或rhigh記錄的移動(dòng)，待一趟排序結(jié)束后再將基準(zhǔn)記錄移至正確位置上。 void quick_sort(int num ,int s,int t)int i,j; i=s;j=t; num0=nums; while(ii&num0numj) j-; if(ij) numi=numj; i+; while(ij&numi=num0) i+; if(ij) numj=numi; j-; numi=num0; if(si) quick_sort(num,s,j-1); if(it) quick_sort(num,j+1,t);可以證明, 函數(shù)quick_sort的平均時(shí)間復(fù)雜度

9、是O(nlog2n)。實(shí)驗(yàn)結(jié)果表明: 就平均計(jì)算時(shí)間而言, 快速排序是所有內(nèi)排序方法中最好的一個(gè)?？焖倥判蚴沁f歸的?？焖倥判蚴且环N不穩(wěn)定的排序方法。最佳狀況時(shí)間復(fù)雜度是O(nlog2n)最壞狀況時(shí)間復(fù)雜度是O(n2) 基本思想:每一趟 (例如第 i 趟, i = 0, 1, , n-2) 在后面 n-i 個(gè)待排序記錄中選出關(guān)鍵字最小的記錄, 作為有序序列中的第 i 個(gè)記錄。待到第n-2 趟做完, 待排序記錄只剩下1個(gè),就不用再選了。11.3 選擇排序 直接選擇排序是一種簡單的排序方法, 它的基本步驟是：在一組對象 ViVn-1 中選擇具有最小關(guān)鍵字的對象；若它不是這組對象中的第一個(gè)對象, 則將

10、它與這組對象中的第一個(gè)對象對調(diào);在剩下的對象Vi+1Vn-1中重復(fù)執(zhí)行第、步, 直到剩余對象只有一個(gè)為止。一、選擇排序直接選擇排序21254925*16080 1 2 3 4 5初始2125*i = 025164908最小者 08交換21,0825160825*4921i = 1最小者 16交換25,1649i = 2081625*2521最小者 21交換49,21 直接選擇排序的過程最小者 25*無交換4925*0 1 2 3 4 5i = 30816252125*i = 449最小者 25無交換2521160825160825*4921結(jié)果各趟排序后的結(jié)果直接選擇排序的排序比較次數(shù)與對象的

11、初始排列無關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對象, 則第 i 趟選擇具有最小排序碼對象所需的比較次數(shù)總是 n-i-1 次?？偟呐判虼a比較次數(shù)為對象的移動(dòng)次數(shù)與對象序列的初始排列有關(guān)。當(dāng)這組對象的初始狀態(tài)是按其排序碼從小到大有序的時(shí)候, 對象的移動(dòng)次數(shù)為0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對象移動(dòng)次數(shù)為 3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。二、堆排序堆的定義：n個(gè)元素的序列(k1,k2,kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆或(i=1,2,.n/2)kik2ikik2i+1kik2ikik2i+1例 （96,83,27,38,11,9）例 （13,38,27,50,7

12、6,65,49,97）962791138831327384965765097可將堆序列看成完全二叉樹，則堆頂元素（完全二叉樹的根）必為序列中n個(gè)元素的最小值或最大值堆排序：將無序序列建成一個(gè)堆，得到關(guān)鍵字最小（或最大）的記錄；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1個(gè)元素重又建成一個(gè)堆，則可得到n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列，這個(gè)過程叫堆排序需解決的兩個(gè)問題：如何由一個(gè)無序序列建成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素，使之成為一個(gè)新的堆？第二個(gè)問題解決方法篩選 方法：輸出堆頂元素之后，以堆中最后一個(gè)元素替代之；然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小者進(jìn)行

13、交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13 273849502765769713輸出：13 276549502738769713輸出：13 27 384965502738769713輸出：13 27 387665502738499713輸出：13 27 38 495065762738499713輸出：13 27 38 499765762738495013輸出13 27 38 49 5065977

14、62738495013輸出13 27 38 49 509765762738495013輸出：13 27 38 49 50 657665972738495013輸出：13 27 38 49 50 659765762738495013輸出：13 27 38 49 50 65 769765762738495013輸出：13 27 38 49 50 65 76 97第一個(gè)問題解決方法方法：從無序序列的第n/2個(gè)元素（即此無序序列對應(yīng)的完全二叉樹的最后一個(gè)非葉子結(jié)點(diǎn)）起，至第一個(gè)元素止，進(jìn)行反復(fù)篩選含8個(gè)元素的無序序列（49，38，65，97，76，13，27，50）496538271376975049

15、65382713765097491338276576509749133827657650971327384965765097算法性能分析： 堆排序適用于記錄數(shù)較多的文件，它所需要的輔助空間比較少，空間復(fù)雜度為O（1）。 因?yàn)槎咽莻€(gè)樹形的結(jié)構(gòu)，所以時(shí)間復(fù)雜度與樹的高度有關(guān)系，在最壞的情況下時(shí)間復(fù)雜度為O（nlog2n)。 堆排序是一種不穩(wěn)定的排序方法。11.4 插入排序 (Insert Sorting)基本思想：每步將一個(gè)待排序的對象, 按其關(guān)鍵字大小, 插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上, 直到對象全部插入為止。排序過程：整個(gè)排序過程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序

16、子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序例如：打撲克時(shí)，邊抓牌，邊碼牌?；舅枷耄寒?dāng)插入第i (i 1) 個(gè)對象時(shí), 前面的V0, V1, , Vi-1已經(jīng)排好序。這時(shí), 用Vi的關(guān)鍵字與Vi-1, Vi-2, 的關(guān)鍵字順序進(jìn)行比較, 找到插入位置即將Vi插入, 原來位置上的對象向后順移。一、直接插入排序 (Insert Sort)直接插入排序過程0 1 2 3 4 5 62108254925*16i = 22125084925*1649 2125084925*16i = 32125084925*1625*2125084925*160 1 2 3 4 5 6 i = 121

17、25084925*16252125084925*16排序前排序后監(jiān)視哨i = 52125084925*162125084925*1608i = 42125084925*1616162125084925*160 1 2 3 4 5 6 49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38

18、49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序結(jié)果： void insert_sort(int r ,int n)int i,j; for(i=2;i=n;i+) r0=ri; j=i-1; while(r0rj) rj+1=rj; j-; rj+1=r0; 算法分析設(shè)待排序?qū)ο髠€(gè)數(shù)為 n, 則該算法的主程序執(zhí)行n-1趟。關(guān)鍵字比較次數(shù)和對象移動(dòng)次數(shù)與對象關(guān)鍵字的初始排列有關(guān)。最好情況下, 排序前對象已按關(guān)鍵字從小到大有序, 每趟只需與前面有序?qū)ο笮蛄械淖詈笠粋€(gè)對象比較1次, 總的關(guān)鍵字比較次數(shù)為 n-1, 不需移動(dòng)記錄

19、。最壞情況下,待排記錄按關(guān)鍵字非遞增有序排列（逆序）時(shí)，第i趟時(shí)第i+1個(gè)對象必須與前面 i 個(gè)對象都做關(guān)鍵字比較, 并且每做1次比較就要做1次數(shù)據(jù)移動(dòng)?？偙容^次數(shù)為(n+2)(n-1)/2次，總移動(dòng)次數(shù)為(n+4)(n-1)/2。在平均情況下的關(guān)鍵字比較次數(shù)和對象移動(dòng)次數(shù)約為 n2/4。因此，直接插入排序的時(shí)間復(fù)雜度為 O(n2)。直接插入排序是一種穩(wěn)定的排序方法?；舅枷耄寒?dāng)待排記錄數(shù)n很小時(shí)，直接插入排序的效率較高。當(dāng)待排序列按關(guān)鍵字基本有序時(shí)直接插入排序的效率也較高。 所以從這兩點(diǎn)出發(fā)可對直接插入排序改進(jìn)，先將整個(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基

20、本有序時(shí)，再對全體記錄進(jìn)行一次直接插入排序。二、希爾排序 (Shell Sort)（縮小增量排序）設(shè)待排序?qū)ο笮蛄杏?n 個(gè)對象, 首先取一個(gè)整數(shù) gap =1) for(i=d+1;i0&r0rj) rj+d=rj; j=j-d; rj+d=r0; d=d/2;開始時(shí) gap 的值較大, 子序列中的對象較少, 排序速度較快; 隨著排序進(jìn)展, gap 值逐漸變小, 子序列中對象個(gè)數(shù)逐漸變多, 由于前面大多數(shù)對象已基本有序, 所以排序速度仍然很快。gap的取法有多種。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。對特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算排序碼

21、的比較次數(shù)和對象移動(dòng)次數(shù)。希爾排序所需的比較次數(shù)和移動(dòng)次數(shù)約為n 1.3一般認(rèn)為，希爾排序的時(shí)間復(fù)雜度是O(nlog2 n)希爾排序是一種不穩(wěn)定的排序方法11.5 歸并排序 (Merge Sort)歸并將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。兩路歸并 (2-way merging)原始序列initList 中兩個(gè)有序表 initListl initListm和initListm+1 initListn，它們可歸并成一個(gè)有序表, 存于另一對象序列mergedList的 l n 中。迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過程進(jìn)行排序的。其基本思想是： 假設(shè)初始對象序列有 n 個(gè)

22、對象，首先把它看成是 n 個(gè)長度為 1 的有序子序列 (歸并項(xiàng))，先做兩兩歸并，得到 n / 2 個(gè)長度為 2 的歸并項(xiàng) (如果 n 為奇數(shù)，則最后一個(gè)有序子序列的長度為1)；再做兩兩歸并，如此重復(fù)，最后得到一個(gè)長度為 n 的有序序列。迭代的歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=16在迭代的歸并排序算法中, 函數(shù)MergePass( ) 做一趟兩

23、路歸并排序, 要調(diào)用merge ( )函數(shù) n/(2*len) O(n/len) 次, 函數(shù)MergeSort( )調(diào)用MergePass( )正好log2n 次,而每次merge( )要執(zhí)行比較O(len)次, 所以算法總的時(shí)間復(fù)雜度為O(nlog2n)。歸并排序占用附加存儲較多, 需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個(gè)算法的缺點(diǎn)。歸并排序是一個(gè)穩(wěn)定的排序方法。各種內(nèi)部排序方法比較排序方法最好時(shí)間最壞時(shí)間平均時(shí)間輔助空間穩(wěn)定性直接插入O(n)O(n2)O(n2)O(1)穩(wěn)定直接選擇O(n2)O(n2)O(n2)O(1)不穩(wěn)定冒泡排序O(n2)O(n2)O(n2)O(1)穩(wěn)定希爾排序-O(1)不穩(wěn)定快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)不穩(wěn)定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不穩(wěn)定歸并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)穩(wěn)定本章小結(jié)1. 掌握排序的概念2. 掌握交換式排序算法及其性能分析3. 掌握選擇式排序算法及其性能分析4. 掌握插入式排序算法及其性能分析5. 掌握歸并排序算法。1、沒有任何一種通過比較元素重排序列的排序算法在最壞情形下，時(shí)間復(fù)雜度好于O（nlogn）( )2、快速排序的速度在所有排序方法中為最快，而且所需附加空間也最少。( )3、最大堆中的每個(gè)結(jié)