數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序課件

《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序課件（68頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 12022-6-20q 學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)v理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。理解排序的定義和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用。排序排序方法有不同的分類方法，基于方法有不同的分類方法，基于“關(guān)鍵字間的比較關(guān)鍵字間的比較”進(jìn)行排序的方法進(jìn)行排序的方法可以按排序過(guò)程所依據(jù)的不同原則分為插入排序、交換排序、選擇可以按排序過(guò)程所依據(jù)的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計(jì)數(shù)排序等五類。排序、歸并排序和計(jì)數(shù)排序等五類。v掌握各種排序方法的時(shí)間復(fù)雜度的分析方法。掌握各種排序方法的

2、時(shí)間復(fù)雜度的分析方法。能從能從“關(guān)鍵字間的比關(guān)鍵字間的比較次數(shù)較次數(shù)”分析排序算法的平均情況和最壞情況的時(shí)間性能。按平均分析排序算法的平均情況和最壞情況的時(shí)間性能。按平均時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類：時(shí)間復(fù)雜度劃分，內(nèi)部排序可分為三類：O O (n(n2 2) ) 的簡(jiǎn)單排序方法，的簡(jiǎn)單排序方法，O O (nlogn) (nlogn) 的高效排序方法和的高效排序方法和O O (dn)(dn)的基數(shù)排序方法。的基數(shù)排序方法。v理解排序方法理解排序方法 穩(wěn)定穩(wěn)定 或或 不穩(wěn)定不穩(wěn)定 的含義，弄清楚在什么情況下要求的含義，弄清楚在什么情況下要求應(yīng)用的排序方法必須是穩(wěn)定的。應(yīng)用的排序方法必須是穩(wěn)

3、定的。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 22022-6-20q 重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn)v重點(diǎn)重點(diǎn)：希爾排序、快速排序、堆排序和歸并排序等高效方法：希爾排序、快速排序、堆排序和歸并排序等高效方法v難點(diǎn)難點(diǎn)：希爾排序、快速排序、堆排序和歸并排序等高效方法：希爾排序、快速排序、堆排序和歸并排序等高效方法q 知識(shí)點(diǎn)知識(shí)點(diǎn)v排序、直接插入排序、折半插入排序、表插入排序、希爾排序、排序、直接插入排序、折半插入排序、表插入排序、希爾排序、起泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、起泡排序、快速排序、簡(jiǎn)單選擇排序、堆排序、2-2-路歸并排序、路歸并排序、基

4、數(shù)排序、排序方法的綜合比較。基數(shù)排序、排序方法的綜合比較。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 32022-6-20q 排序排序v假設(shè)含有假設(shè)含有n n個(gè)記錄的序列為：個(gè)記錄的序列為：RR1 1，R R2 2，R Rn n ， 它們的關(guān)鍵字相應(yīng)為它們的關(guān)鍵字相應(yīng)為KK1 1，K K2 2，K Kn n ， 對(duì)記錄序列進(jìn)行對(duì)記錄序列進(jìn)行排序排序就是要確定序號(hào)就是要確定序號(hào)1 1，2 2，n n的一種排列的一種排列 P P1 1，P P2 2，P Pn n，使其相應(yīng)的關(guān)鍵字滿足如下的使其相應(yīng)的關(guān)鍵字滿足如下的非遞減（或非遞增）非遞減（或非遞增）的

5、關(guān)系：的關(guān)系： K Kp1p1=K=Kp2p2=K=Kpnpn 使序列成為一個(gè)按關(guān)鍵字有序的序列使序列成為一個(gè)按關(guān)鍵字有序的序列 RRp p1 1，R Rp p2 2，R Rp pn n v目的目的利用高效的查找方法，以提高查找效率。利用高效的查找方法，以提高查找效率。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 42022-6-20q 排序分類排序分類v按待排序記錄所在位置按待排序記錄所在位置內(nèi)部排序內(nèi)部排序：待排序記錄存放在內(nèi)存。：待排序記錄存放在內(nèi)存。外部排序外部排序：排序過(guò)程中需對(duì)外存進(jìn)行訪問(wèn)的排序。：排序過(guò)程中需對(duì)外存進(jìn)行訪問(wèn)的排序。v按排

6、序依據(jù)原則按排序依據(jù)原則插入排序插入排序：直接插入排序、折半插入排序、希爾排序。：直接插入排序、折半插入排序、希爾排序。交換排序交換排序：冒泡排序、快速排序。：冒泡排序、快速排序。選擇排序選擇排序：簡(jiǎn)單選擇排序、堆排序。：簡(jiǎn)單選擇排序、堆排序。歸并排序歸并排序：2-2-路歸并排序。路歸并排序?；鶖?shù)排序基數(shù)排序Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 52022-6-20q 穩(wěn)定穩(wěn)定v若待排序文件中有若待排序文件中有關(guān)鍵字相等的記錄，排序后，其前后相對(duì)次序關(guān)鍵字相等的記錄，排序后，其前后相對(duì)次序與排序前未發(fā)生變化與排序前未發(fā)生變化，這種排序稱為，這

7、種排序稱為“穩(wěn)定穩(wěn)定”排序；否則是排序；否則是“不不穩(wěn)定穩(wěn)定”排序。排序。v穩(wěn)定排序與不穩(wěn)定排序穩(wěn)定排序與不穩(wěn)定排序只是表示所用的排序方法，只是表示所用的排序方法，并不說(shuō)明哪種并不說(shuō)明哪種方法好與差。方法好與差。q 排序基本操作排序基本操作v比較比較兩個(gè)關(guān)鍵字大??；兩個(gè)關(guān)鍵字大??；v將記錄從一個(gè)位置將記錄從一個(gè)位置移動(dòng)移動(dòng)到另一個(gè)位置；到另一個(gè)位置；q 就全面性能而言，就全面性能而言，很難提出一種被認(rèn)為最好的方法很難提出一種被認(rèn)為最好的方法，每種，每種方法均有優(yōu)點(diǎn)和適用環(huán)境。方法均有優(yōu)點(diǎn)和適用環(huán)境。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 620

8、22-6-20q 本章討論中，待排記錄如下結(jié)構(gòu)。本章討論中，待排記錄如下結(jié)構(gòu)。#define MAXSIZE 20; #define MAXSIZE 20; / / 假設(shè)的順序表最大長(zhǎng)度假設(shè)的順序表最大長(zhǎng)度type int KeyType; type int KeyType; / / 定義關(guān)鍵字類型為整數(shù)類型定義關(guān)鍵字類型為整數(shù)類型typedef struct typedef struct KeyType key; KeyType key; / / 關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng)InfoType otherinfo;InfoType otherinfo; / / 其它數(shù)據(jù)項(xiàng)其它數(shù)據(jù)項(xiàng) RcdType; Rc

9、dType; / / 記錄類型記錄類型typedef struct typedef struct RcdType rMAXSIZE+1;RcdType rMAXSIZE+1; / r0/ r0閑置或作為判別標(biāo)志的閑置或作為判別標(biāo)志的“哨兵哨兵”單元單元 int length; int length; / / 順序表長(zhǎng)度順序表長(zhǎng)度 SqList SqList；/ / 順序表類型順序表類型Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 72022-6-2010.2.1 10.2.1 直接插入排序直接插入排序q 基本思想基本思想v整個(gè)排序過(guò)程為整個(gè)排序過(guò)程為

10、n-1n-1趟插入趟插入，即，即先將先將序列中第序列中第1 1個(gè)記錄看成是一個(gè)個(gè)記錄看成是一個(gè)有序子序列有序子序列，然后，然后從第從第2 2個(gè)記錄開(kāi)始個(gè)記錄開(kāi)始，逐個(gè)進(jìn)行插入逐個(gè)進(jìn)行插入，直至整個(gè)直至整個(gè)序列有序序列有序。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 82022-6-2049 38 65 97 76 13 2749 38 65 97 76 13 27i=2 ( 49 ) 38 65 97 76 13 27i=2 ( 49 ) 38 65 97 76 13 27i=3 ( 38 49 ) 65 97 76 13 27i=3 ( 38 4

11、9 ) 65 97 76 13 27i=4 i=4 ( 38 49 65 ) 97 76 13 27 ( 38 49 65 ) 97 76 13 27i=5 i=5 ( 38 49 65 97 ) 76 13 27 ( 38 49 65 97 ) 76 13 27i=6 i=6 ( 38 49 65 76 97 )13 27 ( 38 49 65 76 97 )13 27i=1 ( )i=1 ( )i=7 ( 13 38 49 65 76 97 ) 27i=7 ( 13 38 49 65 76 97 ) 272727979776766565494938382727 ( 13 27 38 49

12、65 76 97 ) ( 13 27 38 49 65 76 97 )排序結(jié)果：排序結(jié)果：383838384949656597979797767697977676131376766565494938381313) ) ) ) ) ) ) ) ) ) ) ) )監(jiān)視哨監(jiān)視哨r0r0 r1r1 r2r2 r3r3 r4r4 r5r5 r6r6 r7r7Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 92022-6-20q直接插入排序的算法直接插入排序的算法1 12 23 34 45 56 67 78 8時(shí)間復(fù)雜度時(shí)間復(fù)雜度T(n)=O(nT(n)=O(n)

13、 )Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 102022-6-20q 算法評(píng)價(jià)算法評(píng)價(jià)v時(shí)間復(fù)雜度時(shí)間復(fù)雜度 若待排序記錄按關(guān)鍵字從小到大排列若待排序記錄按關(guān)鍵字從小到大排列( (正序正序) ) 關(guān)鍵字比較次數(shù)：關(guān)鍵字比較次數(shù)：112nni記錄移動(dòng)次數(shù)：記錄移動(dòng)次數(shù)：21(1)nin 若待排序記錄按關(guān)鍵字從大到小排列若待排序記錄按關(guān)鍵字從大到小排列( (逆序逆序) ) 關(guān)鍵字比較次數(shù)：關(guān)鍵字比較次數(shù)：2)1)(2(2nnini記錄移動(dòng)次數(shù)：記錄移動(dòng)次數(shù)：2)1)(4()1(2nniniData StructureData Structure數(shù)據(jù)

14、結(jié)構(gòu)(C語(yǔ)言) 排序Page 112022-6-20 若待排序記錄是若待排序記錄是隨機(jī)隨機(jī)的，取平均值。的，取平均值。關(guān)鍵字比較次數(shù)：關(guān)鍵字比較次數(shù)：42n記錄移動(dòng)次數(shù)：記錄移動(dòng)次數(shù)：42nv空間復(fù)雜度空間復(fù)雜度S(n)=O(1)S(n)=O(1)Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 122022-6-20q 折半插入排序折半插入排序v基本思想基本思想 用折半查找方法確定插入位置的排序。用折半查找方法確定插入位置的排序。i=1 (30) 13 70 85 39 42 6 20i=1 (30) 13 70 85 39 42 6 20i=2 i=

15、2 1313 (13 30) 70 85 39 42 6 20 (13 30) 70 85 39 42 6 20i=7 i=7 6 6 (6 13 30 39 42 70 85 ) 20 (6 13 30 39 42 70 85 ) 20i=8 i=8 2020 (6 13 30 39 42 70 85 ) 20 (6 13 30 39 42 70 85 ) 20i ih hi=8 i=8 2020 (6 13 (6 13 2020 30 39 42 70 85 ) 30 39 42 70 85 )h hm mi im mh hm m插入位置插入位置Data StructureData Str

16、ucture數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 132022-6-20void BInsertSort (SqList &L)void BInsertSort (SqList &L)/ / 對(duì)順序表對(duì)順序表L L作折半插入排序作折半插入排序 for ( i=2; i=L.length; +i )for ( i=2; i=L.length; +i ) L.r0 = L.ri;L.r0 = L.ri;/ / 將將L.riL.ri暫存到暫存到L.r0L.r0 low = 1; high = i-1;low = 1; high = i-1; while (low=high) while (low=hig

17、h+1; -j ) L.rj+1 = L.rj; for ( j=i-1; j=high+1; -j ) L.rj+1 = L.rj; / / 記錄后移記錄后移L.rhigh+1 = L.r0;L.rhigh+1 = L.r0; / / 插入插入 / BInsertSort/ BInsertSort時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(n)=O(nT(n)=O(n) )Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 142022-6-20v算法評(píng)價(jià)算法評(píng)價(jià)時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(n)=O(nT(n)=O(n) )空間復(fù)雜度：空間復(fù)雜度：S(n)=O(1)S(

18、n)=O(1) 折半插入排序只能折半插入排序只能減少排序過(guò)程中關(guān)鍵字比減少排序過(guò)程中關(guān)鍵字比較的時(shí)間，并不能減少記錄移動(dòng)的時(shí)間較的時(shí)間，并不能減少記錄移動(dòng)的時(shí)間。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 152022-6-20q 2-2-路插入排序路插入排序v基本思想基本思想 另設(shè)一個(gè)另設(shè)一個(gè)和和L.rL.r同類型的同類型的數(shù)組數(shù)組d d，首先，首先將將L.r1L.r1賦給賦給d1d1，并將，并將d1d1看成是看成是在排好序的序列中處于在排好序的序列中處于中間位置的記錄中間位置的記錄，然后，然后從從L.rL.r中第中第2 2個(gè)記錄起依次插入到個(gè)記

19、錄起依次插入到d1d1之前或之后的有序序列中之前或之后的有序序列中。v目的目的 對(duì)折半插入排序的改進(jìn)，減少記錄的移動(dòng)次數(shù)。對(duì)折半插入排序的改進(jìn)，減少記錄的移動(dòng)次數(shù)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 162022-6-20初始關(guān)鍵字初始關(guān)鍵字49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49i=1i=1(49)(49)firstfirstfinalfinali=2i=2(49) (38)(49) (38)firstfirstfinalfinali=3i=3(49 65) (38)(49 65) (3

20、8)firstfirstfinalfinali=4i=4(49 65 97) (38)(49 65 97) (38)firstfirstfinalfinalData StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 172022-6-20初始關(guān)鍵字初始關(guān)鍵字49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49i=4i=4(49 65 97) (38)(49 65 97) (38)firstfirstfinalfinali=5i=5(49 65 76 97) (38)(49 65 76 97) (38)firstfirstfi

21、nalfinali=6i=6(49 65 76 97) (13 38)(49 65 76 97) (13 38)firstfirstfinalfinali=7i=7(49 65 76 97) (13 27 38)(49 65 76 97) (13 27 38)firstfirstfinalfinalData StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 182022-6-20初始關(guān)鍵字初始關(guān)鍵字49 38 65 97 76 13 27 4949 38 65 97 76 13 27 49i=7i=7(49 65 76 97) (13 27 38)(49 65 7

22、6 97) (13 27 38)firstfirstfinalfinali=8i=8firstfirstfinalfinal(49 49 65 76 97) (13 27 38)(49 49 65 76 97) (13 27 38) 2 2路插入排序的路插入排序的移動(dòng)記錄次數(shù)減少了移動(dòng)記錄次數(shù)減少了，約為約為n n2 2/8/8，但不能避免移動(dòng)但不能避免移動(dòng)。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 192022-6-20q 基本思想基本思想v是是對(duì)插入排序的一個(gè)改進(jìn)對(duì)插入排序的一個(gè)改進(jìn)，也稱縮小增量排序。，也稱縮小增量排序。v先將整個(gè)先將整個(gè)待

23、排序記錄序列分割成若干個(gè)子序列待排序記錄序列分割成若干個(gè)子序列，分別對(duì)這些，分別對(duì)這些子序子序列進(jìn)行直接插入排序列進(jìn)行直接插入排序；待整個(gè)序列中的記錄；待整個(gè)序列中的記錄“基本有序基本有序”時(shí)，再時(shí)，再對(duì)對(duì)全體記錄進(jìn)行一次直接插入排序全體記錄進(jìn)行一次直接插入排序。q 排序過(guò)程排序過(guò)程v取一個(gè)取一個(gè)正整數(shù)正整數(shù)d1nd1n，把所有，把所有相隔相隔d1d1的記錄放一組的記錄放一組，組內(nèi)組內(nèi)進(jìn)行進(jìn)行直接直接插入排序插入排序；v然后然后取取d2d1d2d1，重復(fù)上述重復(fù)上述分組和排序分組和排序操作操作；v直至直至di=1di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹?。，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹?。Dat

24、a StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 202022-6-20取取d3=1d3=1三趟分組：三趟分組：三趟排序結(jié)果：三趟排序結(jié)果：一趟排序結(jié)果：一趟排序結(jié)果：二趟排序結(jié)果：二趟排序結(jié)果：取取d1=5d1=5一趟分組：一趟分組：取取d2=3d2=3二趟分組：二趟分組：49 38 65 97 76 13 27 49 55 449 38 65 97 76 13 27 49 55 413 27 49 55 4 49 38 65 97 7613 27 49 55 4 49 38 65 97 7613 27 49 55 4 49 38 65 97 7613 27

25、 49 55 4 49 38 65 97 7613 4 49 38 27 49 55 65 97 7613 4 49 38 27 49 55 65 97 7613 4 49 38 27 49 55 65 97 7613 4 49 38 27 49 55 65 97 764 13 27 38 49 49 55 65 76 974 13 27 38 49 49 55 65 76 97Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 212022-6-20void ShellInsert ( SqList &Lvoid ShellInsert ( SqList

26、 &L，int dk)int dk)/ / 對(duì)順序表對(duì)順序表L L作一趟希爾插入排序。本算法是和一趟直接插入排序作一趟希爾插入排序。本算法是和一趟直接插入排序/ / 相比，作了如下修改：相比，作了如下修改：1.1.前后記錄位置的增量是前后記錄位置的增量是dkdk，不是，不是1 1；/ 2.r0/ 2.r0只是暫存單元，不是哨兵。當(dāng)只是暫存單元，不是哨兵。當(dāng)j=0j=0時(shí)，插入位置已找到。時(shí)，插入位置已找到。for ( i=dk+1; i=L.length; +i )for ( i=dk+1; i0<(L.r0.key,L.rj.key); j-=dk ) for(j=i-dk; j0<

27、(L.r0.key,L.rj.key); j-=dk ) L.rj+dk = L.rj; L.rj+dk = L.rj; / / 記錄后移，查找插入位置記錄后移，查找插入位置 L.rj+dk = L.r0; L.rj+dk = L.r0; / / 插入插入 / if / if / ShellInsert / ShellInsertData StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 222022-6-20void ShellSort (SqList &L, int dlta, int t)void ShellSort (SqList &L, int dlta

28、, int t)/ / 按增量序列按增量序列 dlta0.t-1 dlta0.t-1 對(duì)順序表對(duì)順序表L L作希爾排序作希爾排序for (k=0; kt; +t) for (k=0; kr2.keyr1.keyr2.key，則交換則交換；然后比較；然后比較第二個(gè)記錄與第二個(gè)記錄與第三個(gè)記錄第三個(gè)記錄；依次類推，；依次類推，直至第直至第n-1n-1個(gè)記錄和第個(gè)記錄和第n n個(gè)記錄個(gè)記錄比較比較為止為止第一趟冒泡排序第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上最后一個(gè)記錄上。對(duì)前對(duì)前n-1n-1個(gè)記錄進(jìn)行第二趟冒泡排序個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字

29、次大的記，結(jié)果使關(guān)鍵字次大的記錄被安置在第錄被安置在第n-1n-1個(gè)記錄位置個(gè)記錄位置重復(fù)上述過(guò)程，重復(fù)上述過(guò)程，直到直到“在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記在一趟排序過(guò)程中沒(méi)有進(jìn)行過(guò)交換記錄的操作錄的操作”為止。為止。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 252022-6-2038 13 2738 13 27 49 49 4949第四趟后第四趟后494938 49 13 27 30 38 49 13 27 30 6565第三趟后第三趟后494938 49 65 13 27 30 38 49 65 13 27 30 7676第二趟后第二趟后49

30、4938 49 65 76 13 27 30 38 49 65 76 13 27 30 9797第一趟后第一趟后494949 38 65 97 76 13 27 4949 38 65 97 76 13 27 49初始關(guān)鍵字初始關(guān)鍵字13 27 3813 27 38 4949第五趟后第五趟后49497676979713139797272797979797131376767676272713136565272765656565131313134949494927273838272738383838494949497676494913 27 13 27 3838第六趟后第六趟后q 時(shí)間復(fù)雜度時(shí)間復(fù)雜

31、度v最好情況（正序）最好情況（正序） 比較次數(shù)：比較次數(shù)：n-1n-1 移動(dòng)次數(shù)：移動(dòng)次數(shù)：0 0v最壞情況（逆序）最壞情況（逆序） 比較次數(shù)：比較次數(shù)：q 空間復(fù)雜度空間復(fù)雜度：S(n)=O(1)S(n)=O(1)(21)(211nninni)(23)(321nninni移動(dòng)次數(shù)：移動(dòng)次數(shù)：Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 262022-6-20q快速排序快速排序v對(duì)起泡法的一種改進(jìn)。對(duì)起泡法的一種改進(jìn)。v基本思想基本思想通過(guò)通過(guò)一趟排序一趟排序，將，將待排序記錄分割成獨(dú)立的兩部分待排序記錄分割成獨(dú)立的兩部分，其中，其中一部一部分記錄的

32、關(guān)鍵字均比另一部分記錄的關(guān)鍵字小分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可，則可分別對(duì)這分別對(duì)這兩部分記錄進(jìn)行排序兩部分記錄進(jìn)行排序，以達(dá)到整個(gè)序列有序。，以達(dá)到整個(gè)序列有序。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 272022-6-20v排序過(guò)程排序過(guò)程 對(duì)對(duì)rstrst中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i i和和j j，設(shè)樞軸記錄設(shè)樞軸記錄rp=rsrp=rs，x=rp.keyx=rp.key，初始時(shí)，初始時(shí)令令i=s,j=ti=s,j=t；首先，首先，從從j j所指位置向前搜索第一個(gè)關(guān)鍵字小于所指

33、位置向前搜索第一個(gè)關(guān)鍵字小于x x的記錄，并的記錄，并和和rprp交換交換；再再?gòu)膹膇 i所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x x的記錄，的記錄，和和rprp交換交換；重復(fù)上述兩步，重復(fù)上述兩步，直至直至i=ji=j為止為止；再再分別對(duì)兩個(gè)子序列進(jìn)行快速排序分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有直到每個(gè)子序列只含有一個(gè)記錄為止一個(gè)記錄為止。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 282022-6-2049 38 65 97 76 13 27 4949 38 65 97 76 13 27

34、492727i i初始關(guān)鍵字：初始關(guān)鍵字：j jx x 4949j ji ii i6565j j1313i i9797j jj j494949 38 65 97 76 13 27 4949 38 65 97 76 13 27 49初始關(guān)鍵字：初始關(guān)鍵字： 完成一趟排序：完成一趟排序： 27 38 13 27 38 13 4949 76 97 65 49 76 97 65 49 一次劃分后：一次劃分后：( 27 38 13 ) ( 27 38 13 ) 4949 ( 76 97 65 49 ) ( 76 97 65 49 ) 分別進(jìn)行快速排序：分別進(jìn)行快速排序：( 13 )( 13 ) 2727

35、 ( 38 )( 38 ) 4949 ( 49 65 ) ( 49 65 ) 76 76 ( 97 )( 97 ) ( 13 ) ( 13 ) 2727 ( 38 )( 38 ) 4949 4949 (65) (65) 76 76 ( 97 )( 97 )快速排序結(jié)束：快速排序結(jié)束： 1313 27 27 38 38 4949 4949 65 65 76 76 97 97Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 292022-6-20int Partition ( SqList &L, int low, int high)int Partitio

36、n ( SqList &L, int low, int high)/ / 交換順序表交換順序表L L中子表中子表rlow.highrlow.high中的記錄，樞軸記錄到位，并返回中的記錄，樞軸記錄到位，并返回/ / 其所在位置，此時(shí)，在它之前（后）的記錄均不大（小）于它。其所在位置，此時(shí)，在它之前（后）的記錄均不大（?。┯谒?。L.r0 = L.rlow;L.r0 = L.rlow;/用子表的第一個(gè)記錄作樞軸記錄用子表的第一個(gè)記錄作樞軸記錄pivotkey = L.rlow.key; pivotkey = L.rlow.key; / / 樞軸記錄關(guān)鍵字樞軸記錄關(guān)鍵字while (low high

37、) while (low high) / / 從表的兩端交替地向中間掃描從表的兩端交替地向中間掃描while (low = pivotkey) -high;while (low = pivotkey) -high;L.rlow+ = L.rhigh;L.rlow+ = L.rhigh;/ / 將比樞軸記錄小的記錄移到低端將比樞軸記錄小的記錄移到低端while (low high & L.rlow.key = pivotkey)while (low high & L.rlow.key = pivotkey)+low;+low;L.rhigh = L.rlow;L.rhigh = L.rlow;/

38、 / 將比樞軸記錄大的記錄移到高端將比樞軸記錄大的記錄移到高端 / while/ while L.rlow = L.r0; L.rlow = L.r0;/ / 樞軸記錄到位樞軸記錄到位return low; return low; / / 返回樞軸位置返回樞軸位置 / Partition / PartitionData StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 302022-6-20void Qsort(SqList &L, int low, int high)void Qsort(SqList &L, int low, int high)/對(duì)順序表對(duì)順序

39、表L L中的子序列中的子序列L.rlowhighL.rlowhigh作快速排序作快速排序if (low high) if (low high) /長(zhǎng)度大于長(zhǎng)度大于1 1pivotloc= pivotloc= Partition(L,low,high)Partition(L,low,high); ; /將將L.rlowhighL.rlowhigh劃分劃分Qsort(L,low,pivotloc-1); Qsort(L,low,pivotloc-1); /對(duì)低子表排序?qū)Φ妥颖砼判騋sort(L, pivotloc+1,high); Qsort(L, pivotloc+1,high); /對(duì)高子表排

40、序?qū)Ω咦颖砼判?/ Qsort/ Qsortvoid QuickSort(SqList &L)void QuickSort(SqList &L)/對(duì)順序表對(duì)順序表L L作快速排序作快速排序Qsort(L,1,L.length); Qsort(L,1,L.length); / QuickSort/ QuickSort時(shí)間復(fù)雜度時(shí)間復(fù)雜度T(n)=O(nT(n)=O(n) )Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 312022-6-20q 算法分析算法分析v時(shí)間復(fù)雜度時(shí)間復(fù)雜度最好情況（每次總是選到中間值作樞軸）最好情況（每次總是選到中間值作樞軸）

41、T(n)=O(nlogT(n)=O(nlog2 2n)n)最壞情況（每次總是選到最小或最大元素作樞軸）最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(nT(n)=O(n) )為防止最差情況的出現(xiàn)，為防止最差情況的出現(xiàn)，一般采取一般采取“三者取中三者取中”法來(lái)確定樞軸。法來(lái)確定樞軸。即在第一個(gè)記錄和最后一個(gè)記錄，以及中間位置的記錄中，選取即在第一個(gè)記錄和最后一個(gè)記錄，以及中間位置的記錄中，選取值為中間的那個(gè)來(lái)作樞軸，這樣就能防止最差情況的出現(xiàn)。值為中間的那個(gè)來(lái)作樞軸，這樣就能防止最差情況的出現(xiàn)。v空間復(fù)雜度空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸：需棧空間以實(shí)現(xiàn)遞歸最壞情況：最壞情況：S(n)=

42、O(n)S(n)=O(n)一般情況：一般情況：S(n)=O(logS(n)=O(log2 2n)n)v對(duì)隨機(jī)的關(guān)鍵字序列，快速排序是對(duì)隨機(jī)的關(guān)鍵字序列，快速排序是目前被認(rèn)為是最好的排序方法目前被認(rèn)為是最好的排序方法。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 322022-6-20q 基本思想基本思想v每一趟在每一趟在n-i+1n-i+1（i=1,2,n-1i=1,2,n-1）個(gè)記錄中選取關(guān)鍵字最小的記）個(gè)記錄中選取關(guān)鍵字最小的記錄，錄，并將它和第并將它和第i i個(gè)記錄進(jìn)行互換，從而個(gè)記錄進(jìn)行互換，從而使其成為有序序列中第使其成為有序序列中第i i

43、個(gè)記錄。個(gè)記錄。10.4.1 10.4.1 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序q 排序過(guò)程排序過(guò)程v首先，通過(guò)首先，通過(guò)n-1n-1次關(guān)鍵字比較次關(guān)鍵字比較，從從n n個(gè)記錄中找出關(guān)鍵字最小的記個(gè)記錄中找出關(guān)鍵字最小的記錄錄，將它，將它與第一個(gè)記錄交換與第一個(gè)記錄交換；v再通過(guò)再通過(guò)n-2n-2次比較次比較，從剩余的，從剩余的n-1n-1個(gè)記錄中個(gè)記錄中找出關(guān)鍵字次小的記錄找出關(guān)鍵字次小的記錄，將它將它與第二個(gè)記錄交換與第二個(gè)記錄交換；v重復(fù)上述操作，重復(fù)上述操作，共進(jìn)行共進(jìn)行n-1n-1趟排序后，排序結(jié)束趟排序后，排序結(jié)束。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排

44、序Page 332022-6-20 1313 ( 38 65 97 76 49 27 49 ) ( 38 65 97 76 49 27 49 )初始：初始： ( 49 38 65 97 76 13 27 49 )( 49 38 65 97 76 13 27 49 )i=1i=113134949i=2i=227273838i=3i=3i=4i=4i=5i=5i=6i=613 2713 27 ( 65 97 76 49 38 49 ) ( 65 97 76 49 38 49 )3838656513 27 3813 27 38 ( 97 76 49 65 49 ) ( 97 76 49 65 49

45、)4949979713 27 38 4913 27 38 49 ( 76 97 65 49 ) ( 76 97 65 49 )4949767613 27 38 4913 27 38 49 76 ( 97 65 ) 76 ( 97 65 )494976766565979713 27 38 4913 27 38 49 76 97 ( 97 ) 76 97 ( 97 )494976766565767676769797排序結(jié)束排序結(jié)束13 27 38 4913 27 38 49 76 97 65 ( ) 76 97 65 ( )494976767676979765657676Data Structur

46、eData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 342022-6-20void SelectSort (SqList &L)void SelectSort (SqList &L)/ / 對(duì)順序表對(duì)順序表L L作簡(jiǎn)單選擇排序作簡(jiǎn)單選擇排序for (i=1; iL.length; +i) for (i=1; iL.length; +i) / / 選擇第選擇第 i i 小的記錄，并交換到位小的記錄，并交換到位j = i;j = i;for ( k=i+1; k=L.length; k+ )for ( k=i+1; k=L.length; k+ )/ / 在在L.ri.L.length

47、L.ri.L.length中選擇關(guān)鍵字最小的記錄中選擇關(guān)鍵字最小的記錄if ( LT( L.rk.key , L.rj.key ) j =k ;if ( LT( L.rk.key , L.rj.key ) j =k ;if ( i!=j ) L.rj if ( i!=j ) L.rj L.ri; L.ri; / / 與第與第 i i 個(gè)記錄互換個(gè)記錄互換 / for/ for / SelectSort / SelectSort時(shí)間復(fù)雜度時(shí)間復(fù)雜度T(n)=O(nT(n)=O(n) )Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 352022-6-20

48、q 算法評(píng)價(jià)算法評(píng)價(jià)v時(shí)間復(fù)雜度時(shí)間復(fù)雜度記錄移動(dòng)次數(shù)記錄移動(dòng)次數(shù)最好情況：最好情況：0 0最壞情況：最壞情況：3(n-1)3(n-1)比較次數(shù)：比較次數(shù)：)(21)(211nninniv空間復(fù)雜度空間復(fù)雜度：S(n)=O(1)S(n)=O(1)Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 362022-6-20q 堆的定義堆的定義vn n個(gè)元素的序列個(gè)元素的序列(k1,k2,kn)(k1,k2,kn)，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)，稱之為堆。稱之為堆。221iiiikkkk或或221iiiikkkk1,2,2ni v若將若將此序列

49、此序列對(duì)應(yīng)的一維數(shù)組對(duì)應(yīng)的一維數(shù)組看成是一個(gè)完全二叉樹(shù)看成是一個(gè)完全二叉樹(shù)，則，則k ki i為二為二叉樹(shù)的根結(jié)點(diǎn)，叉樹(shù)的根結(jié)點(diǎn)，k k2i2i和和k k2i+12i+1分別為分別為k ki i的的“左子樹(shù)根左子樹(shù)根”和和“右子樹(shù)右子樹(shù)根根”。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 372022-6-20（9696，8383，2727，3838，1111，9 9）（1313，3838，2727，5050，7676，6565，4949，9797）969627279 91111383883831313272738384949656576765050

50、9797大頂堆大頂堆小頂堆小頂堆Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 382022-6-20q 堆排序堆排序v將無(wú)序序列建成一個(gè)堆，得到關(guān)鍵字最?。ɑ蜃畲螅┑挠涗洠惠攲o(wú)序序列建成一個(gè)堆，得到關(guān)鍵字最小（或最大）的記錄；輸出堆頂?shù)淖钚。ù螅┲岛?，使剩余的出堆頂?shù)淖钚。ù螅┲岛?，使剩余的n-1n-1個(gè)元素重又建成一個(gè)堆，個(gè)元素重又建成一個(gè)堆，則可得到則可得到n n個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列個(gè)元素的次小值；重復(fù)執(zhí)行，得到一個(gè)有序序列的過(guò)的過(guò)程。程。q 堆排序需解決的兩個(gè)問(wèn)題堆排序需解決的兩個(gè)問(wèn)題：v如何由一個(gè)如何由一個(gè)無(wú)序序列建成

51、一個(gè)堆無(wú)序序列建成一個(gè)堆？( (初始建堆初始建堆) )v如何在輸出堆頂元素之后，如何在輸出堆頂元素之后，調(diào)整調(diào)整剩余元素，使之剩余元素，使之成為一個(gè)新的堆成為一個(gè)新的堆？Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 392022-6-20q 第二個(gè)問(wèn)題解決方法第二個(gè)問(wèn)題解決方法篩選（以篩選（以小頂堆小頂堆為例）為例）v輸出堆頂元素輸出堆頂元素之后，之后，以堆中最后一個(gè)元素替代之以堆中最后一個(gè)元素替代之；v然后然后將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較將根結(jié)點(diǎn)值與左、右子樹(shù)的根結(jié)點(diǎn)值進(jìn)行比較，并與其中小并與其中小者進(jìn)行交換者進(jìn)行交換；v重復(fù)上述操作，

52、重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至稱這個(gè)從堆頂至葉子的調(diào)整過(guò)程為葉子的調(diào)整過(guò)程為“篩選篩選”。Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 402022-6-201313272738384949656576765050979797972727383849496565767650501313輸出：輸出：131327274949383897976565767650501313輸出：輸出：131397974949383827276565767650501313輸出：輸出：13,2713,2738384949

53、505027276565767697971313輸出：輸出：13,2713,2765654949505027273838767697971313輸出：輸出：13,27,3813,27,38Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 412022-6-2049496565505027273838767697971313輸出：輸出：13,27,3813,27,3876766565505027273838494997971313輸出：輸出：13,27,38,4913,27,38,4950506565767627273838494997971313輸出：輸

54、出：13,27,38,4913,27,38,4997976565767627273838494950501313輸出：輸出：13,27,38,49,5013,27,38,49,5065659797767627273838494950501313輸出：輸出：13,27,38,49,5013,27,38,49,5097976565767627273838494950501313輸出：輸出：13,27,38,49,50,6513,27,38,49,50,65Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 422022-6-207676656597972727

55、3838494950501313輸出：輸出：13,27,38,49,50,6513,27,38,49,50,6597976565767627273838494950501313輸出：輸出：13,27,38,49,50,65,7613,27,38,49,50,65,7697976565767627273838494950501313輸出：輸出：13,27,38,49,50,65,76,9713,27,38,49,50,65,76,97Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 432022-6-20void HeapAdjust (SqList &H

56、, int s, int m)void HeapAdjust (SqList &H, int s, int m)/ / 已知已知H.rs.mH.rs.m中記錄的關(guān)鍵字除中記錄的關(guān)鍵字除H.rs.keyH.rs.key之外均滿足堆的定義，之外均滿足堆的定義，/ / 本函數(shù)調(diào)整本函數(shù)調(diào)整H.rsH.rs的關(guān)鍵字，使的關(guān)鍵字，使H.rs.mH.rs.m成為一個(gè)大頂堆（對(duì)其中成為一個(gè)大頂堆（對(duì)其中/ / 記錄的關(guān)鍵字而言）記錄的關(guān)鍵字而言）rc = H.rs;rc = H.rs; / / 暫存根結(jié)點(diǎn)的記錄暫存根結(jié)點(diǎn)的記錄for(j=2for(j=2* *s;j=m;js;j=m;j* *=2 ) =2

57、 ) / / 沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下篩選沿關(guān)鍵字較大的孩子結(jié)點(diǎn)向下篩選if ( jm & LT(H.rj.key,H.rj+1.key ) +j; if ( jm & LT(H.rj.key,H.rj+1.key ) +j; / j / j 為關(guān)鍵字較大的孩子記錄的下標(biāo)為關(guān)鍵字較大的孩子記錄的下標(biāo)if (!LT(rc.key, H.rj.key ) break; if (!LT(rc.key, H.rj.key ) break; / / 不需要調(diào)整，跳出循環(huán)不需要調(diào)整，跳出循環(huán)H.rs = H.rj; s = j; H.rs = H.rj; s = j; / / 將大關(guān)鍵字記錄往上調(diào)將大關(guān)

58、鍵字記錄往上調(diào)/ for/ forH.rs = rc; H.rs = rc; / / 回移篩選下來(lái)的記錄回移篩選下來(lái)的記錄 / HeapAdjust / HeapAdjust若改為小頂堆，若改為小頂堆，該如何修改語(yǔ)句？該如何修改語(yǔ)句？jm & LT(H.rj+1.key,H.rj.key)j0; -i ) for ( i=H.length/2; i0; -i ) / / 將將 H.r1.H.length H.r1.H.length 建成大頂堆建成大頂堆HeapAdjust ( H, i, H.length );HeapAdjust ( H, i, H.length );for ( i=H.le

59、ngth; i1; -i ) for ( i=H.length; i1; -i ) H.r1 H.r1 H.ri; H.ri; / / 將堆頂記錄和當(dāng)前未經(jīng)排將堆頂記錄和當(dāng)前未經(jīng)排/ / 序的子序列序的子序列H.r1.iH.r1.i中最中最/ / 后一個(gè)記錄互相交換后一個(gè)記錄互相交換HeapAdjust(H, 1, i-1);HeapAdjust(H, 1, i-1);/ / 將將H.r1.i-1H.r1.i-1重新調(diào)整為重新調(diào)整為/ / 大頂堆大頂堆/for/for / HeapSort / HeapSortData StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Pa

60、ge 472022-6-20q 算法評(píng)價(jià)算法評(píng)價(jià)v時(shí)間復(fù)雜度時(shí)間復(fù)雜度：最壞情況下：最壞情況下T(n)=O(nlogn)T(n)=O(nlogn)篩選算法：最多從第篩選算法：最多從第1 1層篩到最底層，為完全二叉樹(shù)的深度層篩到最底層，為完全二叉樹(shù)的深度 loglog2 2n n +1;+1;初始建堆：調(diào)用篩選算法初始建堆：調(diào)用篩選算法 n/2n/2 次；次；重建堆：調(diào)用篩選算法重建堆：調(diào)用篩選算法 n-1 n-1 次。次。v空間復(fù)雜度空間復(fù)雜度：S(n)=O(1)S(n)=O(1)v記錄較少時(shí)，不提倡使用記錄較少時(shí)，不提倡使用。v不穩(wěn)定不穩(wěn)定的排序方法的排序方法Data StructureDa

61、ta Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 482022-6-20q 歸并歸并v將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。q 2-2-路歸并排序路歸并排序v排序過(guò)程排序過(guò)程設(shè)初始序列含有設(shè)初始序列含有n n個(gè)記錄，則可看成個(gè)記錄，則可看成n n個(gè)有序的子序列，每個(gè)個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為子序列長(zhǎng)度為1 1；兩兩合并兩兩合并，得到，得到 n/2n/2 個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為2 2或或1 1的有序子序列；的有序子序列；再兩兩合并，再兩兩合并，如此重復(fù)，如此重復(fù)，直至得到一個(gè)長(zhǎng)度為直至得到一個(gè)長(zhǎng)度為n n的有序序的有序序列為止列為止。D

62、ata StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 492022-6-20初始關(guān)鍵字：初始關(guān)鍵字： 49 38 65 97 76 13 2749 38 65 97 76 13 27一趟歸并后：一趟歸并后： 38 49 65 97 13 76 2738 49 65 97 13 76 27二趟歸并后：二趟歸并后： 38 49 65 97 13 27 7638 49 65 97 13 27 76三趟歸并后：三趟歸并后： 13 27 38 49 65 76 9713 27 38 49 65 76 97Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(

63、C語(yǔ)言) 排序Page 502022-6-20void Merge (RcdType SR, RcdType &TR, int i, int m, int n)void Merge (RcdType SR, RcdType &TR, int i, int m, int n)/ / 將有序的將有序的SRi.mSRi.m和和SRm+1.nSRm+1.n歸并為有序的歸并為有序的TRi.nTRi.nfor (j=m+1, k=i; i=m & j=n; +k) for (j=m+1, k=i; i=m & j=n; +k) / / 將將SRSR中記錄按關(guān)鍵字從小到大地復(fù)制到中記錄按關(guān)鍵字從小到大地復(fù)制

64、到TRTR中中if ( LQ(SRi.key, SRj.key) TRk = SRi+;if ( LQ(SRi.key, SRj.key) TRk = SRi+;else TRk = SRj+;else TRk = SRj+; while (i=m) TRk+ = SRi+; while (i=m) TRk+ = SRi+; / / 將剩余的將剩余的 SRi.m SRi.m 復(fù)制到復(fù)制到TRTRwhile (j=n) TRk+ = SRj+; while (j=n) TRk+ = SRj+; / / 將剩余的將剩余的 SRj.n SRj.n 復(fù)制到復(fù)制到TRTR / Merge / Merge

65、Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 512022-6-20q 算法評(píng)價(jià)算法評(píng)價(jià)v時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：T(n)=O(nlog2n)T(n)=O(nlog2n)每趟兩兩歸并需調(diào)用每趟兩兩歸并需調(diào)用mergemerge算法算法 n/2hn/2h 次（次（h h為有序段長(zhǎng)度）；為有序段長(zhǎng)度）；整個(gè)歸并要進(jìn)行整個(gè)歸并要進(jìn)行 loglog2 2n n 趟。趟。v空間復(fù)雜度：空間復(fù)雜度：S(n)=O(n)S(n)=O(n)Data StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 522022-6-2010.6.1 10

66、.6.1 多關(guān)鍵字的排序多關(guān)鍵字的排序q 多關(guān)鍵字排序多關(guān)鍵字排序例例 對(duì)對(duì)5252張撲克牌按以下次序排序：張撲克牌按以下次序排序：兩個(gè)關(guān)鍵字：花色（兩個(gè)關(guān)鍵字：花色（ ） 面值（面值（23A23A） 并且并且“花色花色”地位高于地位高于“面值面值” 2 3 A 2 3 A 2 3 A 2 3 AData StructureData Structure數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言) 排序Page 532022-6-20v多關(guān)鍵字排序方法多關(guān)鍵字排序方法最高位優(yōu)先法最高位優(yōu)先法（MSD)MSD)： 先對(duì)最高位關(guān)鍵字先對(duì)最高位關(guān)鍵字k1k1排序排序，將序列分成若干子序列將序列分成若干子序列，每，每個(gè)子序列有相同的個(gè)子序列有相同的k1k1值；值；然后然后讓每個(gè)子序列讓每個(gè)子序列對(duì)次關(guān)鍵字對(duì)次關(guān)鍵字k2k2（如面值）排序（如面值）排序，又分成若干更小的子序列；依次重復(fù)，又分成若干更小的子序列；依次重復(fù)，直直至就每個(gè)子序列對(duì)最低位關(guān)鍵字至就每個(gè)子序列對(duì)最低位關(guān)鍵字kdkd排序排序；最后將所有子序列；最后將所有子序列依次連接在一起成為一個(gè)有序序列。依次連接在一起成為一個(gè)有序序列。最低位優(yōu)先法最低位優(yōu)先法(LS