排序概念、種類和方法講解

1、排序概念、種類和方法講解第8章 排 序學習目的要求:掌握排序的概念和排序的種類。熟練掌握五類基本排序:插入排序、交換排序、選擇排序、歸并排序和基數排序的算法思想、算法實現和性能分析。8.1 排序的基本概念8.2 插入排序8.3 選擇排序8.4 交換排序8.5 歸并排序8.6 基數排序8.7 幾種排序方法的比較第8章 排 序8.1 排序的基本概念假設含有n個記錄的序列為R1，R2，Rn其相應的關鍵字序列為K1，K2，Kn一種排列P1，P2， ，Pn，使其相應的關鍵字滿足如下非遞減關系（滿足非遞增關系時，將“”號改為“”號）Kp1Kp2Kpn使n個記錄的無序序列成為一個按關鍵字有序的序列Rp1 ，

2、Rp2 ，Rpn這樣一種操作過程稱為排序。排序：將一個數據元素（或記錄）的任意序列，重新排列成一個按關鍵字有序的序列。學生檔案表學號姓名年齡性別99001王曉佳18男99002林一鵬19男99003謝寧17女99004張麗娟18女99005周濤20男99006李小燕16女8.1 排序的基本概念8.1 排序的基本概念排序過程中依據的不同原則，內部排序方法可大致分為插入排序、交換排序、選擇排序、歸并排序和基數排序等五類。評價排序算法優(yōu)劣的標準：一是算法執(zhí)行時所需的時間二是執(zhí)行算法時所需要的附加空間執(zhí)行排序的時間復雜性是算法優(yōu)劣的重要的標志。影響時間復雜性的主要因素又可以用算法執(zhí)行中的比較次數和移動

3、次數來衡量。在排序的過程中常需進行兩種基本操作: 比較兩個關鍵字的大小; 將記錄從一個位置移動至另一個位置。8.1 排序的基本概念待排序的記錄序列存儲方式: 存放在地址連續(xù)的一組存儲單元上，類似于線性表。排序時必須移動記錄; 存放在靜態(tài)鏈表中，記錄之間的次序關系由指針指定，排序時不需要移動記錄，僅需修改指針; 記錄本身存儲在一組地址連續(xù)的存儲單元內，另設一個指示各個記錄存儲位置的地址向量，排序時僅需移動地址向量排序后再按照地址向量中的值調整記錄的存儲位置。8.1 排序的基本概念8.1 排序的基本概念若在排序期間具有相同鍵值的記錄的相對位置不變，則稱此排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。8.2

4、插入排序插入排序（Insertion Sort）的基本思想:每次將一個待排序的記錄，按其關鍵字的大小插入到前面已經排好序的有序序列中的適當位置上，直到全部記錄插入完成為止。直接插入排序折半插入排序2路插入排序希爾排序8.2.1 直接插入排序直接插入排序（Straight Insertion Sort）是一種最簡單的排序方法?；静僮鳎阂来螌⒂涗浶蛄兄械拿恳粋€記錄插入到有序序列中，使有序序列的長度不斷地擴大。8.2 插入排序有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n一共需要經過n-1趟就可以將初始序列的n個記錄重新排列成按關鍵字值

5、大小排列的有序序列。過程如下:先將待排序記錄序列中的第一個記錄作為一個有序序列，將記錄序列中的第二個記錄插入到上述有序序列中形成由兩個記錄組成的有序序列，再將記錄序列中的第三個記錄插入到這個有序序列中，形成由三個記錄組成的有序序列，如此進行下去，直到最后一個記錄也插入完成。8.2 插入排序 初始關鍵字： (49) 38 65 97 76 13 27 49 i=2 (38) (38 49) 65 97 76 13 27 49 i=3 (65) (38 49 65) 97 76 13 27 49 i=4 (97) (38 49 65 97) 76 13 27 49 i=5 (76) (38 49

6、65 76 97) 13 27 49 i=6 (13) (13 38 49 65 76 97) 27 49 i=7 (27) (13 27 38 49 65 76 97) 49 i=8 (49) (13 27 38 49 49 65 76 97) 監(jiān)視哨L.r0直接插入排序是穩(wěn)定的。注意:第二條記錄和第八條記錄的相對位置在排序后沒有發(fā)生變化，此排序算法是穩(wěn)定的。8.2 插入排序直接插入排序算法簡單、易實現，其算法的時間復雜度是O（n2）。從空間復雜度來看，只需要一個記錄大小的輔助空間用于暫存待插入的記錄。當待排序記錄較少時，排序速度較快，反之，當待排序的記錄數量較大時，大量的比較和移動操作將使

7、直接插入排序算法的效率降低;另外，若當待排序的數據元素基本有序時，排序過程中的記錄移動次數會大大減少，從而效率會有所提高。直接插入排序是一種穩(wěn)定的排序方法。8.2.2 折半插入排序折半插入排序是對直接插入排序的改進算法，它是利用折半查找來實現插入位置的定位，可減少排序過程中的比較次數。適用于待排序的記錄數量較大的情況。8.2 插入排序一趟折半插入排序的步驟為: （1）初始化 將待插入的記錄存入r0中:r0ri; 給指定查找區(qū)間上下界指針賦值:low1，high i-1; （2）折半查找插入位置; （3）將插入位置后面的記錄依次后移一個位置; （4）將暫存在r0中的待插入記錄放入找到的位置上。8

8、.2 插入排序14 36 49 52 8058 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置折半插入排序只減少關鍵字間的比較次數，而記錄的移動次數不變。故折半插入排序的時間復雜度仍為 O（n2）。從空間復雜度來看，折半插入排序只需要一個記錄大小的輔助空間用于暫存待插入的記錄，這與直接插入排序相同。折半插入排序是一種穩(wěn)定的排序方法。8.2 插入排序8.2.3 2-路插入排序2-路插入排序是對折半插入排序的改進算法，它是利用增加輔助空間來減少排序過程

9、中移動記錄的次數，即“以空間換時間”。8.2 插入排序具體做法是:建立一個和待排序序列rn同類型的數組dn作為輔助空間。先將r0的值賦給d0，將d0看成是處于最后有序序列中處于中間位置的記錄，再從r1開始依次將記錄插入到d0之前或之后的有序序列中。將數組d看成是一循環(huán)向量（既首尾相連的環(huán)狀空間），并設置兩個指針first和final分別指向有序序列的第一條和最后一條記錄，將當前待插入記錄ri與d0比較，若riri+1），則交換其位置，經過多趟排序，最終使整個序列有序。假設在排序過程中,記錄序列R1.n的狀態(tài)為:第 i 趟起泡排序無序序列R1.n-i+1有序序列 Rn-i+2.nn-i+1無序序

10、列R1.n-i有序序列 Rn-i+1.n比較相鄰記錄，將關鍵字最大的記錄交換到 n-i+1 的位置上8.4 交換排序處理過程為:第一趟:從第一條記錄r1開始，直到最后一條記錄rn，對兩兩相鄰的記錄依此比較，若發(fā)現為逆序，則立即交換其位置，最后使這n條記錄中關鍵字最大的記錄“下沉”到最底部，既被交換到第n個位置上，它不參與下一趟排序; 第二趟:從第一條記錄r1開始，直到第n-1條記錄rn-1，對兩兩相鄰的記錄依此比較，若發(fā)現為逆序，則立即交換其位置，最后使這n-1條記錄中關鍵字最大的記錄“下沉”到次底部，既被交換到第n-1個位置上，它不參與下一趟排序;如此反復，最多經過（n-1）趟冒泡排序，就可

11、以使整個序列成為有序序列。49 38 65 97 76 13 27 30 初始關鍵字38 49 65 76 13 27 30 97 第一趟38 49 65 13 27 30 76 第二趟38 49 13 27 30 65 第三趟38 13 27 30 49 第四趟13 27 30 38 第五趟13 27 30 第六趟38497697139727979730137676761365273065276530134949492730133827383038例如，一組待排序的記錄的關鍵字如下，要求按照關鍵字由小到大進行排序。 42 36 56 78 67 11 27 368.4 交換排序初始狀態(tài)423

12、656786711273678i=13642566711273667i=23642561127365678i=33642112736426778i=43611273636566778i=51127363642566778i=61127273642566778i=711363642566778冒泡排序的時間復雜度為O（n2），由于它的記錄移動次數較多，故平均時間性能比直接插入排序要差得多。冒泡排序只需要一個記錄的輔助空間，用來作為記錄交換的中間暫存單元。冒泡排序是一種穩(wěn)定的排序方法。8.4 交換排序8.4.2 快速排序快速排序（Quick Sort）是對冒泡排序的一種改進。基本思想:通過一趟排序

13、將待排序記錄劃分成兩部分，使得其中一部分記錄的關鍵字比另一部分記錄的關鍵字小;然后再分別對這兩部分記錄進行這種排序，直到每個部分為空或只包含一個記錄時，整個快速排序結束。8.4 交換排序8.4 交換排序待排序的序列:（rs，rs-1，rt）先任意選取一個記錄（通?？蛇x第一個記錄rs作為基準記錄或稱為支點），然后重新排列這些記錄。將所有關鍵字較它小的記錄都排到它的位置之前，將所有關鍵字較它大的記錄都排到它的位置之后。由此可以將該基準記錄所在的位置i作為分界線，將待排序記錄序列劃分成兩個子序列（rs，ri-1）和（ri+1，rt）。這個過程稱為一趟快速排序。一趟快速排序完成后得到前后兩個子序列，可

14、再分別對分割后的兩個子序列進行快速排序。整個快速排序過程結束。stlowhigh設 Rs=52 為支點 將 Rhigh.key 和 支點的關鍵字進行比較，要求Rhigh.key 支點的關鍵字 將 Rlow.key 和 支點的關鍵字進行比較，要求Rlow.key 樞軸的關鍵字high23low80high14low52例如R052lowhighhighhighlow例如，待排序記錄的關鍵字為: 42 36 56 78 67 11 27 368.4 交換排序8.4 交換排序 首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。無 序 的 記 錄 序 列無序記錄子

15、序列(1)無序子序列(2)支點一次劃分分別進行快速排序例初始關鍵字： 49 38 65 97 76 13 27 50 ij支點ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分別進行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序結束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij快速排序的時間復雜度平均為 O（nlog2n），當n較大時， 這種算法是平均速度最快的排序算法，因此稱為快速排序?？焖倥判蚴且环N不穩(wěn)定的排序方法。8.4 交換排序8.5 歸并排序歸并排序（M

16、erging Sort）:“歸并”的含義是將兩個或兩個以上的有序序列合成一個新的有序序列。假設初始序列含有 n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到 n/2 個長度為2（最后一個序列長度可能小于2）的有序子序列;再兩兩歸并，得到 n/2 /2 個長度為4（最后一個序列長度可能小于4）的有序序列;如此重復，直至得到一個長度為n的有序序列為止，每一次合并過程稱為一趟歸并排序，這種排序方法稱為 2-路歸并排序。在內部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有 序 序 列 Rl.n有序子序列 Rl.m有序子序

17、列 Rm+1.n這個操作對順序表而言，是輕而易舉的。例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23例如，設待排序的記錄序列為: 42 36 56 78 67 11 27 36 2-路歸并排序中的核心操作是將一維數組中前后相鄰的兩個有序序列歸并為一個有序序列。8.5 歸并排序2-路歸并排序算法的時間復雜度為 O（nlog2n）。 在排序時需利用一個與待排序數組同樣大小的輔助數組，占用內存比前面介紹的算法多

18、。2-路歸并排序算法是穩(wěn)定的。8.5 歸并排序8.6 基數排序基數排序（Radix Sorting）是和前面所述各類排序方法完全不同的一種排序方法。前面討論的排序主要是通過關鍵字間的比較和移動記錄這兩種操作實現的，而基數排序不需要進行關鍵字間的比較?；鶖蹬判蚴墙柚嚓P鍵字排序的思想實現的。8.6.1 多關鍵字的排序8.6 基數排序例如，撲克牌中52張牌面的次序關系為: 2 3 A2 3 A 2 3 A 2 3 A 每一張牌有兩個“關鍵字”:花色（ ）和面值（23A），且“花色”的地位高于“面值”，在比較任意兩張牌面的大小時，必須先比較“花色”，若“花色”相同，則再比較面值。由此，將撲克牌整理成

19、如上所述次序關系時，通常采用的辦法是:先按不同“花色”分成有次序的四堆，每一堆的牌均有相同的“花色”，然后分別對每一堆按“面值”大小整理有序。也可采用另一種辦法:先按不同“面值”分成13堆，然后將這13堆牌自小至大疊在一起（“3”在“2”之上，“4”在“3”之上，最上面的是4張“A”）， 然后將這付牌整個顛倒過來再按不同“花色”分成4堆，最后將這4堆牌按自小至大的次序合在一起（ 在最下面，在最上面），此時同樣得到一付滿足如上次序的牌。這兩種整理撲克牌的方法便是兩種多關鍵字的排序方法。為了實現多關鍵字排序，通常有兩種方法:第一種方法是先對最高位關鍵字K0進行排序，將序列分成若干子序列，每個子序列

20、中的記錄都具有相同的K0值，然后分別對每個子序列按次高位關鍵字K1進行排序，按K1值不同再分成若干個更小的子序列，每個子序列中的記錄都具有相同的K1值，依次重復，直至完成對Kd-1進行排序，最后將所有子序列依次連接在一起成為一個有序序列，這種方法稱之為最高位優(yōu)先 （Most Significant Digit First）法，簡稱MSD法;第二種方法是從最低位關鍵字Kd-1起進行排序，然后再對高一位的關鍵字Kd-2進行排序，依次重復，直到對K0進行排序后便成為一個有序序列。這種方法稱之為最低位優(yōu)先（Least Siginificant Digit First）法，簡稱LSD法。 8.6 基數排

21、序8.6 基數排序MSD和LSD只規(guī)定按什么樣的“關鍵字次序”來進行排序，而未規(guī)定對每個關鍵字進行排序時所用的方法，比較這兩種方法，LSD要比MSD簡單，因為LSD是對每個關鍵字都是整個序列參加排序，通過若干次“分配”和“收集”來實現排序，執(zhí)行的次數取決于d的大小;而MSD需要處理各序列與子序列的獨立排序問題，通常是一個遞歸問題。8.6.2 鏈式基數排序基數排序是借助于多關鍵字排序思想進行排序的方法，其基本操作是按關鍵字位進行“分配”和“收集”。在基數排序的“分配”與“收集”操作過程中，為了避免數據元素的大量移動，通常采用鏈式存儲結構存儲待排序的記錄序列。8.6 基數排序通常將關鍵字取值的數目

22、稱為基數，用RADIX表示，按LSD進行排序，對待排序的記錄序列按照復合關鍵字從低位到高位的順序交替地“分配”到RADIX個隊列中后再“收集”，如此重復d次，最終得到有序的記錄序列。有些記錄的關鍵字可以看成是由若干個關鍵字組合而成。即K=K0K1 .Kd-1。每個關鍵字Ki表示關鍵字的一位，其中K0為最高位，Kd-1為最低位，d為關鍵字的位數。8.6 基數排序下面舉例說明基數排序過程。設待排序記錄的關鍵字為:387，456，592，625，076，471，050，396，557，5228.6 基數排序8.6 基數排序8.6 基數排序從基數排序的算法中容易看出，對于n個記錄（假設每個記錄含d個關鍵字，每個關鍵字的取值范圍為r），則采用基數排序需進行d趟關鍵字的分配和收集，每趟運算時間復雜度為O（n+r），所以基數排序的時間復雜度為O（d（n+r）。由于d、r是常數，當n較大時，基數排序的時間復雜度近似為O（n）。但n較小，d較大時，采用基數排序并不合 適;只有當n較大、d較小時，基數排序才最為有效。這種排序方法的缺點是占用的存儲空間較多，每個待排序的記錄都需要