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

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

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

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

4、插入排序插入排序（Insertion Sort）的基本思想:每次將一個待排序的記錄，按其關(guān)鍵字的大小插入到前面已經(jīng)排好序的有序序列中的適當(dāng)位置上，直到全部記錄插入完成為止。直接插入排序折半插入排序2路插入排序希爾排序8.2.1 直接插入排序直接插入排序（Straight Insertion Sort）是一種最簡單的排序方法。基本操作：依次將記錄序列中的每一個記錄插入到有序序列中，使有序序列的長度不斷地擴大。8.2 插入排序有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n一共需要經(jīng)過n-1趟就可以將初始序列的n個記錄重新排列成按關(guān)鍵字值

5、大小排列的有序序列。過程如下:先將待排序記錄序列中的第一個記錄作為一個有序序列，將記錄序列中的第二個記錄插入到上述有序序列中形成由兩個記錄組成的有序序列，再將記錄序列中的第三個記錄插入到這個有序序列中，形成由三個記錄組成的有序序列，如此進(jìn)行下去，直到最后一個記錄也插入完成。8.2 插入排序 初始關(guān)鍵字： (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 插入排序直接插入排序算法簡單、易實現(xiàn)，其算法的時間復(fù)雜度是O（n2）。從空間復(fù)雜度來看，只需要一個記錄大小的輔助空間用于暫存待插入的記錄。當(dāng)待排序記錄較少時，排序速度較快，反之，當(dāng)待排序的記錄數(shù)量較大時，大量的比較和移動操作將使

7、直接插入排序算法的效率降低;另外，若當(dāng)待排序的數(shù)據(jù)元素基本有序時，排序過程中的記錄移動次數(shù)會大大減少，從而效率會有所提高。直接插入排序是一種穩(wěn)定的排序方法。8.2.2 折半插入排序折半插入排序是對直接插入排序的改進(jìn)算法，它是利用折半查找來實現(xiàn)插入位置的定位，可減少排序過程中的比較次數(shù)。適用于待排序的記錄數(shù)量較大的情況。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例如:再如:插入位置插入位置折半插入排序只減少關(guān)鍵字間的比較次數(shù)，而記錄的移動次數(shù)不變。故折半插入排序的時間復(fù)雜度仍為 O（n2）。從空間復(fù)雜度來看，折半插入排序只需要一個記錄大小的輔助空間用于暫存待插入的記錄，這與直接插入排序相同。折半插入排序是一種穩(wěn)定的排序方法。8.2 插入排序8.2.3 2-路插入排序2-路插入排序是對折半插入排序的改進(jìn)算法，它是利用增加輔助空間來減少排序過程

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

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

11、以使整個序列成為有序序列。49 38 65 97 76 13 27 30 初始關(guān)鍵字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例如，一組待排序的記錄的關(guān)鍵字如下，要求按照關(guān)鍵字由小到大進(jìn)行排序。 42 36 56 78 67 11 27 368.4 交換排序初始狀態(tài)423

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

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

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

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

16、erging Sort）:“歸并”的含義是將兩個或兩個以上的有序序列合成一個新的有序序列。假設(shè)初始序列含有 n個記錄，則可看成是n個有序的子序列，每個子序列的長度為1，然后兩兩歸并，得到 n/2 個長度為2（最后一個序列長度可能小于2）的有序子序列;再兩兩歸并，得到 n/2 /2 個長度為4（最后一個序列長度可能小于4）的有序序列;如此重復(fù)，直至得到一個長度為n的有序序列為止，每一次合并過程稱為一趟歸并排序，這種排序方法稱為 2-路歸并排序。在內(nèi)部排序中，通常采用的是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例如，設(shè)待排序的記錄序列為: 42 36 56 78 67 11 27 36 2-路歸并排序中的核心操作是將一維數(shù)組中前后相鄰的兩個有序序列歸并為一個有序序列。8.5 歸并排序2-路歸并排序算法的時間復(fù)雜度為 O（nlog2n）。 在排序時需利用一個與待排序數(shù)組同樣大小的輔助數(shù)組，占用內(nèi)存比前面介紹的算法多

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

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

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

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

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