[理學(xué)]大學(xué)教程零起點(diǎn)數(shù)據(jù)結(jié)構(gòu)--排序ppt課件

1、6/28/20221直接插入排序基于順序查找直接插入排序基于順序查找表插入排序基于鏈表存儲(chǔ)表插入排序基于鏈表存儲(chǔ)折半插入排序基于折半查找折半插入排序基于折半查找希爾排序基于逐趟減少增量希爾排序基于逐趟減少增量直接插入排序基于順序查找直接插入排序基于順序查找直接插入排序思想：直接插入排序思想：依次將待排序記錄中的第依次將待排序記錄中的第i個(gè)記錄插入到有序序列中個(gè)記錄插入到有序序列中.初始情況：將初始情況：將r1作為有序序列，將作為有序序列，將r2-rn逐個(gè)插入逐個(gè)插入,經(jīng)過順序查找方式找到經(jīng)過順序查找方式找到ri在有序表中的位置在有序表中的位置,找位置的同時(shí)挪動(dòng)有序序列中元素的位置找位置的同時(shí)挪

2、動(dòng)有序序列中元素的位置,找位置時(shí)從后向前找找位置時(shí)從后向前找.在一個(gè)已排好序的記錄子集的根底上，每一步將下一個(gè)待排序的記錄有序地插入到已排好序的記錄子集中，直到將一切待排記錄全部插入為止。直接插入排序基于順序查找直接插入排序基于順序查找初始關(guān)鍵字初始關(guān)鍵字35 48351845 12 68334835第一趟排序第一趟排序48351845 12 6833步驟：步驟：i=2i=2riri存入存入r0r0位置位置將將r0r0關(guān)鍵字與關(guān)鍵字與rjrj關(guān)鍵字比較關(guān)鍵字比較j j從從i-1i-1開場(chǎng)到開場(chǎng)到1 1 假設(shè)假設(shè)r0rjr0rj那么那么rjrj存入存入rj+1rj+1位置，位置，j j減減1 1

3、r0r0存入存入rj+1rj+1位置位置r0為監(jiān)視哨為監(jiān)視哨直接插入排序基于順序查找直接插入排序基于順序查找初始關(guān)鍵字初始關(guān)鍵字351845 12 6833484835第二趟排序第二趟排序48351845 12 6833步驟：步驟：i=3i=3riri存入存入r0r0位置位置將將r0r0關(guān)鍵字與關(guān)鍵字與rjrj關(guān)鍵字比較關(guān)鍵字比較j j從從i-1i-1開場(chǎng)到開場(chǎng)到1 1 假設(shè)假設(shè)r0rjr0rj那么那么rjrj存入存入ri+1ri+1位置，位置，j j減減1 1r0r0存入存入rj+1rj+1位置位置18483518r0為監(jiān)視哨為監(jiān)視哨直接插入排序基于順序查找直接插入排序基于順序查找初始關(guān)鍵字

4、初始關(guān)鍵字45 12 6833第三趟排序第三趟排序48351845 12 6833步驟：步驟：i=4i=4riri存入存入r0r0位置位置將將r0r0關(guān)鍵字與關(guān)鍵字與rjrj關(guān)鍵字比較關(guān)鍵字比較j j從從i-1i-1開場(chǎng)到開場(chǎng)到1 1 假設(shè)假設(shè)r0rjr0rj那么那么rjrj存入存入rj+1rj+1位置，位置，j j減減1 1r0r0存入存入rj+1rj+1位置位置18483518454845r0為監(jiān)視哨為監(jiān)視哨直接插入排序基于順序查找直接插入排序基于順序查找初始關(guān)鍵字初始關(guān)鍵字 12 6833第四趟排序第四趟排序48351845 12 6833步驟：步驟：i=5i=5riri存入存入r0r0

5、位置位置將將r0r0關(guān)鍵字與關(guān)鍵字與rjrj關(guān)鍵字比較關(guān)鍵字比較j j從從i-1i-1開場(chǎng)到開場(chǎng)到1 1 假設(shè)假設(shè)r0rjr0rj那么那么rjrj存入存入rj+1rj+1位置，位置，j j減減1 1r0r0存入存入rj+1rj+1位置位置3518454845 12 48453518 12 r0為監(jiān)視哨為監(jiān)視哨直接插入排序基于順序查找直接插入排序基于順序查找初始關(guān)鍵字初始關(guān)鍵字 48 35 18 45 12 68 3335 48 18 45 12 68 3318 35 48 45 12 68 3318 35 45 48 12 68 3312 18 35 45 48 68 3312 18 35 4

6、5 48 68 3312 18 33 35 45 48 68【例】打撲克牌時(shí)的抓牌就是插入排序一個(gè)很好的例子，每抓一張牌，插入到適宜位置，直到抓完牌為止，即可得到一個(gè)有序序列。知一組鍵值序列知一組鍵值序列2222，2424，2626，2525，2727，2929，2121，2828，試給出采用直接插入排序法對(duì)該組序列試給出采用直接插入排序法對(duì)該組序列作升序排序的每一趟結(jié)果作升序排序的每一趟結(jié)果 試寫出直接插入排序算法試寫出直接插入排序算法 設(shè)順序表設(shè)順序表vava中的數(shù)據(jù)元素遞增有序。試編寫算法實(shí)中的數(shù)據(jù)元素遞增有序。試編寫算法實(shí)現(xiàn)將現(xiàn)將x x插入到順序表的適當(dāng)位置上，以堅(jiān)持該表的有插入到順序

7、表的適當(dāng)位置上，以堅(jiān)持該表的有序性序性 用插入排序算法對(duì)數(shù)據(jù)序列用插入排序算法對(duì)數(shù)據(jù)序列4747，3333，6161，8282，7272，1111，2525，5757進(jìn)展排序，寫出整個(gè)插入排序的每一趟過程。進(jìn)展排序，寫出整個(gè)插入排序的每一趟過程。直接插入排序基于順序查找直接插入排序基于順序查找Void StraightSort list r, int n fori=2； i=n; i+ r0 = ri; j = i-1; while ( r0.key rj.key ) rj+1 = rj; j-; rj+1 = r0; r0為監(jiān)視哨為監(jiān)視哨該算法時(shí)間復(fù)雜度為該算法時(shí)間復(fù)雜度為On2該算法空間復(fù)

8、雜度為該算法空間復(fù)雜度為O1該算法是穩(wěn)定的排序算法該算法是穩(wěn)定的排序算法設(shè)順序表設(shè)順序表vava中的數(shù)據(jù)元素遞增有序。試編寫算法實(shí)現(xiàn)將中的數(shù)據(jù)元素遞增有序。試編寫算法實(shí)現(xiàn)將x x插入到順序表的適當(dāng)位置上，以堅(jiān)持該表的有序性插入到順序表的適當(dāng)位置上，以堅(jiān)持該表的有序性Va類型定義類型定義typedef struct int key； anytype others； record；define maxsize 100typedef struct record itemmaxsize+1; /記錄數(shù)組，從記錄數(shù)組，從1到到n int n; /記錄條數(shù)記錄條數(shù)list；Void Sort list v

9、a，record x i= va.n ； while ( ) ri+1 = ri; i-; ri+1 = x; x.key =1實(shí)現(xiàn)排序的根本操作有兩個(gè)：1“比較序列中兩個(gè)關(guān)鍵字的大?。?“挪動(dòng)記錄。最好的情況關(guān)鍵字在記錄序列中順序有序：最壞的情況關(guān)鍵字在記錄序列中逆序有序：時(shí)間復(fù)雜度為O(n2)6/28/202218折半插入排序基于折半查找折半插入排序基于折半查找折半插入排序思想：折半插入排序思想：依次將待排序記錄中的第依次將待排序記錄中的第i個(gè)記錄插入到有序序列中個(gè)記錄插入到有序序列中初始情況：將初始情況：將r1作為有序序列，將作為有序序列，將r2-rn逐個(gè)插入逐個(gè)插入經(jīng)過折半查找方式找到

10、經(jīng)過折半查找方式找到ri在有序表中的位置在有序表中的位置找位置后，挪動(dòng)有序序列中元素的位置找位置后，挪動(dòng)有序序列中元素的位置希爾排序分組插入排序希爾排序分組插入排序希爾排序運(yùn)用實(shí)例6/28/202221取取d3=1三趟分組：三趟分組：13 27 48 55 4 49 38 65 97 76三趟排序結(jié)果：三趟排序結(jié)果： 4 13 27 38 48 49 55 65 76 97 初始：49 38 65 97 76 13 27 48 55 4一趟排序結(jié)果：一趟排序結(jié)果：13 27 48 55 4 49 38 65 97 76二趟排序結(jié)果：二趟排序結(jié)果：13 4 48 38 27 49 55 65 9

11、7 76取取d1=5一趟分組：一趟分組： 49 38 65 97 76 13 27 48 55 4取取d2=3二趟分組：二趟分組：13 27 48 55 4 49 38 65 97 76所謂交換排序所謂交換排序就是將待排序序列中的兩個(gè)鍵值比較，就是將待排序序列中的兩個(gè)鍵值比較，根據(jù)比較結(jié)果，交換兩個(gè)記錄的位置根據(jù)比較結(jié)果，交換兩個(gè)記錄的位置冒泡排序冒泡排序快速排序快速排序冒泡排序冒泡排序冒泡排序是最簡單的交換排序算法冒泡排序是最簡單的交換排序算法算法思想：算法思想： 將第一個(gè)記錄鍵值與第二個(gè)比較，假設(shè)符合條件那么將第一個(gè)記錄鍵值與第二個(gè)比較，假設(shè)符合條件那么交換交換將第二個(gè)記錄鍵值與第三個(gè)比較

12、，假設(shè)符合條件那么將第二個(gè)記錄鍵值與第三個(gè)比較，假設(shè)符合條件那么交換交換將第三個(gè)記錄鍵值與第四個(gè)比較，假設(shè)符合條件那么將第三個(gè)記錄鍵值與第四個(gè)比較，假設(shè)符合條件那么交換交換冒泡排序需求進(jìn)展多少趟排序？冒泡排序需求進(jìn)展多少趟排序？假設(shè)某趟排序未進(jìn)展交換，那么算法停頓假設(shè)某趟排序未進(jìn)展交換，那么算法停頓 j從從1開場(chǎng)到開場(chǎng)到n將第將第j個(gè)記錄鍵值與個(gè)記錄鍵值與第第j+1個(gè)比較個(gè)比較假設(shè)符合條件那么假設(shè)符合條件那么交換交換這這是是第第一一趟趟排排序序過過程程交換條件是：第交換條件是：第j個(gè)大于第個(gè)大于第j+1個(gè)記錄那么交換個(gè)記錄那么交換第一趟排序后第一趟排序后最后一個(gè)記錄最后一個(gè)記錄已排至適宜位已排

13、至適宜位置，第二趟排置，第二趟排序?qū)π驅(qū)?到到n-1條條記錄排序即可記錄排序即可第第二二趟趟排排序序后后交換條件是：第交換條件是：第j個(gè)大于第個(gè)大于第j+1個(gè)記錄那么交換個(gè)記錄那么交換j從從1開場(chǎng)到開場(chǎng)到n-1將第將第j個(gè)記錄鍵值與個(gè)記錄鍵值與第第j+1個(gè)比較個(gè)比較假設(shè)符合條件那么假設(shè)符合條件那么交換交換要進(jìn)展多少趟排序？要進(jìn)展多少趟排序？6/28/20222749 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 4

14、9第四趟第四趟13 27 30 38第五趟第五趟13 27 30第六趟第六趟38497697139727973097137676762730136527653065131349493049273827383038void BubbleSort(int a, int n) /* 將將a中整數(shù)序列重新陳列成自小至大中整數(shù)序列重新陳列成自小至大有序的整數(shù)序列有序的整數(shù)序列 */ for (i=n-1, change=TRUE; i=1&change; -i) change = FALSE; for (j=0; jaj+1) swap(aj, aj+1); change = TRUE; 反復(fù)上

15、述過程，直到“在一趟排序過程中沒有進(jìn)展過交換記錄的操作為止1 1設(shè)置兩個(gè)搜索指針，設(shè)置兩個(gè)搜索指針， i i是向后搜索指針初值為是向后搜索指針初值為1 1 j j是向前搜索指針初值為是向前搜索指針初值為n n 且把且把r1r1存入存入r0r0中中r1r1為基準(zhǔn)記錄為基準(zhǔn)記錄2 2j j逐漸減小，進(jìn)展逐漸減小，進(jìn)展rj.key rj.key 和和r0.keyr0.key比較比較 直到滿足直到滿足rj.key r0.keyrj.key r0.keyri.key r0.key時(shí)時(shí) 將將riri挪動(dòng)至挪動(dòng)至rjrj位置位置4 4反復(fù)反復(fù)2 2，3 3步驟直至步驟直至i=ji=j為止，一趟快速排序完成為

16、止，一趟快速排序完成初始關(guān)鍵字初始關(guān)鍵字48351849 12 6833ij48333 3，i+1i+1開場(chǎng)逐漸增大，比較開場(chǎng)逐漸增大，比較ri.key ri.key 和和r0.keyr0.key， ri.key r0.key ri.key r0.key時(shí)將時(shí)將riri挪動(dòng)至挪動(dòng)至rjrj位置位置4 4，j=j+1j=j+1，反復(fù)，反復(fù)2 2，3 3步驟，步驟， 直到直到i=ji=j時(shí)將時(shí)將r0r0存入存入riri位置位置49 12 48第一趟排序完成第一趟排序完成一趟排序后一趟排序后關(guān)鍵字關(guān)鍵字351868i483349 12 48j33 12 351833知序列知序列503503，8787

17、，512512，6161，908908，170170，897897，275275，653653，462462請(qǐng)給出采用快速排序法作升序排序時(shí)的每一趟的結(jié)果。請(qǐng)給出采用快速排序法作升序排序時(shí)的每一趟的結(jié)果。503503，8787，512512，6161，908908，170170，897897，275275，653653，462462503503ij50350387875125126161908908170170897897275275653653462462462462512512275275908908170170503503第一趟排序結(jié)果第一趟排序結(jié)果lowlow到到highhigh之間記

18、錄進(jìn)展快速排序之間記錄進(jìn)展快速排序Void quick Void quick list rlist r， int low int low，int highint high i=low i=low；j=highj=high； r0=ri; r0=ri; if(i =j) return; if(i =j) return; while( ij ) while( ij ) while( i=r0.key ) j-; while( i=r0.key ) j-; if( ij ) ri=rj; i+; if( ij ) ri=rj; i+; while( ij & ri.key=r0.key )

19、i+; while( ij & ri.key=r0.key ) i+; if( ij ) rj=ri; j-; if( ij ) rj=ri; j-; ri=r0 ri=r0 quick ( r,low,i-1 ); quick ( r,i+1,high) quick ( r,low,i-1 ); quick ( r,i+1,high) 用快速排序法對(duì)數(shù)據(jù)序列用快速排序法對(duì)數(shù)據(jù)序列(49(49，3838，6565，9797，1616，5353，134134，2727，39)39)進(jìn)展排序，寫出其第一趟排序的全過程進(jìn)展排序，寫出其第一趟排序的全過程 4949，3838，6565，9797

20、，1616，5353，134134，2727，39394949ij快速排序快速排序時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O Onlognnlogn該算法不穩(wěn)定該算法不穩(wěn)定 假設(shè)數(shù)據(jù)序列本身有序，假設(shè)數(shù)據(jù)序列本身有序，那么算法執(zhí)行效率最低，近似那么算法執(zhí)行效率最低，近似O On2n27.4 7.4 選擇排序選擇排序直接簡單選擇排序算法思想直接簡單選擇排序算法思想首先從待排序序列中選取最小記錄，把它與第一個(gè)首先從待排序序列中選取最小記錄，把它與第一個(gè)記錄交換，然后在剩余的記錄中選擇最小記錄與第記錄交換，然后在剩余的記錄中選擇最小記錄與第二個(gè)記錄進(jìn)展交換，直至排序完成二個(gè)記錄進(jìn)展交換，直至排序完成直接簡單選擇排序

21、直接簡單選擇排序堆排序堆排序初始關(guān)鍵字：初始關(guān)鍵字：51 33 62 96 87 17 28 51 51 33 62 96 87 17 28 51 第一趟排序：第一趟排序：1733 62 96 87 51 28 511733 62 96 87 51 28 51第二趟排序：第二趟排序：17 28 62 96 87 51 33 5117 28 62 96 87 51 33 51第三趟排序：第三趟排序：17 28 33 96 87 51 62 5117 28 33 96 87 51 62 51第四趟排序：第四趟排序：17 28 33 51 87 96 62 5117 28 33 51 87 96 6

22、2 51第五趟排序：第五趟排序：17 28 33 51 51 96 62 8717 28 33 51 51 96 62 87第六趟排序：第六趟排序：17 28 33 51 51 62 96 8717 28 33 51 51 62 96 87第七趟排序：第七趟排序：17 28 33 51 51 62 87 9617 28 33 51 51 62 87 96N N個(gè)數(shù)據(jù)需求多少趟排序？個(gè)數(shù)據(jù)需求多少趟排序？直接選擇排序算法直接選擇排序算法Void select Void select list r list r，int nint n for( i=1; i=n-1; i+ ) for( i=1;

23、i=n-1; i+ ) k=i; k=i; for( j=i+1; j=n; j+ ) for( j=i+1; j=n; j+ ) if( rj.key rk.key ) k=j; if( rj.key rk.key ) k=j; if( k!=i ) swap( rk,ri ); if( k!=i ) swap( rk,ri ); 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O On2n2 直接選擇排序是不穩(wěn)定的直接選擇排序是不穩(wěn)定的7.4 7.4 選擇排序選擇排序根本思想：對(duì)根本思想：對(duì)n n個(gè)待排序記錄的關(guān)鍵字進(jìn)展兩兩比較，個(gè)待排序記錄的關(guān)鍵字進(jìn)展兩兩比較，從中選出從中選出n/2n/2個(gè)較小者再兩兩比較，直

24、到選出關(guān)鍵字最個(gè)較小者再兩兩比較，直到選出關(guān)鍵字最小的記錄為止，此為一趟排序。小的記錄為止，此為一趟排序。一趟選出的關(guān)鍵字最小的記錄稱為一趟選出的關(guān)鍵字最小的記錄稱為“冠軍，而冠軍，而“亞軍亞軍是從與是從與“冠軍比較失敗的記錄中找出。冠軍比較失敗的記錄中找出。輸出輸出“冠軍后，將冠軍葉子結(jié)點(diǎn)關(guān)鍵字改為最大，冠軍后，將冠軍葉子結(jié)點(diǎn)關(guān)鍵字改為最大，繼續(xù)進(jìn)展錦標(biāo)賽排序，直到選出關(guān)鍵字次小的記錄為繼續(xù)進(jìn)展錦標(biāo)賽排序，直到選出關(guān)鍵字次小的記錄為止，如此循環(huán)直到輸出全部有序序列。止，如此循環(huán)直到輸出全部有序序列。 對(duì)關(guān)鍵字序列對(duì)關(guān)鍵字序列 72,73, 71,23, 94,16, 05,6872,73,

25、71,23, 94,16, 05,68進(jìn)展樹形選擇排序進(jìn)展樹形選擇排序 05230572231605727371239416056872, 23, 16 0572, 23, 16 05 “亞軍是從與亞軍是從與“冠軍比較失敗的記錄中找出的冠軍比較失敗的記錄中找出的72,73, 71,23, 94,16, 6872,73, 71,23, 94,16, 68050516231672231668687273712394166816堆排序堆排序 是一種改良的樹形排序是一種改良的樹形排序堆是滿足以下性質(zhì)的數(shù)列堆是滿足以下性質(zhì)的數(shù)列r1, r2, ，rn：或或122iiiirrrr122iiiirrrr堆的

26、定義堆的定義:(小頂堆)(大頂堆)12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 4912, 36, 27, 65, 40, 14, 98, 81, 73, 55, 491 2 3 4 5 6 7 8 9 10 1112, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49是小頂堆是小頂堆1236276581735540984934122iiiirrrr12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆1236276581735540984914堆排序的根本思想是：堆排序的根本思想是： 首先

27、將待排序的記錄序列構(gòu)造一個(gè)堆，此時(shí)，選首先將待排序的記錄序列構(gòu)造一個(gè)堆，此時(shí)，選出了堆中一切記錄的最小者或最大者，然后將它從堆出了堆中一切記錄的最小者或最大者，然后將它從堆中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了中移走，并將剩余的記錄再調(diào)整成堆，這樣又找出了次小或次大的記錄，以此類推，直到堆中只需一次小或次大的記錄，以此類推，直到堆中只需一個(gè)記錄為止，每個(gè)記錄出堆的順序就是一個(gè)有序序列。個(gè)記錄為止，每個(gè)記錄出堆的順序就是一個(gè)有序序列。兩個(gè)問題：兩個(gè)問題：1 1，輸出堆頂后，如何調(diào)整堆，輸出堆頂后，如何調(diào)整堆2 2，如何建立一個(gè)堆，如何建立一個(gè)堆1480754618636184646146

28、148075636184646146143618361875367536804680467536141880756466183663618知一組鍵值序列知一組鍵值序列3232，4444，3838，6565，5353，4242，2929，5757，試采用堆排序法對(duì)該組序列作升序排序，試采用堆排序法對(duì)該組序列作升序排序，給出建立的初始堆給出建立的初始堆以及第一次輸出堆元素后挑選調(diào)整的堆以及第一次輸出堆元素后挑選調(diào)整的堆32324444383865655353424229295757知一組鍵值序列知一組鍵值序列3232，4444，3838，6565，5353，4242，2929，5757，試采用堆排

29、序法對(duì)該組序列作升序排序，試采用堆排序法對(duì)該組序列作升序排序，給出建立的初始堆給出建立的初始堆以及第一次輸出堆元素后挑選調(diào)整的堆以及第一次輸出堆元素后挑選調(diào)整的堆32324444383865655353424229295757575765652929383829293232知一組鍵值序列知一組鍵值序列3232，4444，3838，6565，5353，4242，2929，5757，試采用堆排序法對(duì)該組序列作升序排序，試采用堆排序法對(duì)該組序列作升序排序，給出建立的初始堆給出建立的初始堆以及第一次輸出堆元素后挑選調(diào)整的堆以及第一次輸出堆元素后挑選調(diào)整的堆32324444383865655353424

30、229295757575765652929383829293232292965656565323238386565 知一組鍵值序列知一組鍵值序列3333，3737，2626，4343，5555，6767，4242，3838，試采用堆排序法對(duì)該組序列作升序排序，試采用堆排序法對(duì)該組序列作升序排序，給出建立的初始堆，給出建立的初始堆，以及第一次輸出堆元素后挑選調(diào)整的堆。以及第一次輸出堆元素后挑選調(diào)整的堆。畫出對(duì)應(yīng)于序列畫出對(duì)應(yīng)于序列1010，2020，7 7，7575，4141，6767，3 3，9 9，3030，4545的初始堆堆頂元素取最小值。的初始堆堆頂元素取最小值。設(shè)要將序列設(shè)要將序列Q

31、Q，H H，C C，Y Y，P P，A A，M M，S S，R R按字母升序排序，按字母升序排序，請(qǐng)分別畫出采用堆排序方法時(shí)建立的初始堆，請(qǐng)分別畫出采用堆排序方法時(shí)建立的初始堆，以及第一次輸出堆頂元素后經(jīng)過挑選調(diào)整的堆形狀。以及第一次輸出堆頂元素后經(jīng)過挑選調(diào)整的堆形狀。什么是堆什么是堆? ?寫出對(duì)應(yīng)于序列寫出對(duì)應(yīng)于序列(10(10，2020，7 7，7575，4141，6767，3 3，9 9，3030，45)45)的初始堆的初始堆( (堆頂元素取最小值堆頂元素取最小值) )。7.5 7.5 歸并排序歸并排序根本思想：根本思想： 將多個(gè)有序序列合并成一個(gè)有序序列將多個(gè)有序序列合并成一個(gè)有序序列

32、將兩個(gè)有序子序列合并為一個(gè)有序序列將兩個(gè)有序子序列合并為一個(gè)有序序列 稱為稱為2 2路歸并排序路歸并排序?qū)懗鲦I值寫出鍵值8383，4040，6363，1313，8484，3535，9696，5757，3939，7979，6161，1515運(yùn)用二路歸并排序算法從小到大排序后各趟的結(jié)果。運(yùn)用二路歸并排序算法從小到大排序后各趟的結(jié)果。838340406363131384843535 9696 5757 3939 7979 6161 1515404083831313636335358484 5757 9696 3939 7979 1515 6161131340406363838335355757 84

33、84 9696 1515 3939 6161 7979131335354040575763638383 8484 9696 1515 3939 6161 7979131315153535393940405757 6161 6363 7979 8383 8484 9696兩個(gè)有序序列兩個(gè)有序序列A A，B B如何合并成一個(gè)有序序列？如何合并成一個(gè)有序序列？131335354040575763638383 84841515 3939 6161 7979i ij j合并至合并至A A序列序列合并構(gòu)成新序列合并構(gòu)成新序列C Ck k兩個(gè)有序序列如何合并成一個(gè)有序序列？兩個(gè)有序序列如何合并成一個(gè)有序序列

34、？設(shè)設(shè)i i，j j是兩個(gè)有序序列中的記錄下標(biāo)，是兩個(gè)有序序列中的記錄下標(biāo)，m m，n n是兩個(gè)是兩個(gè)序列長度，序列長度，RR是新的合并后的序列，下表從是新的合并后的序列，下表從k k開場(chǎng)開場(chǎng)1 1，imim且且jnjmim或或jnjn時(shí)，將對(duì)應(yīng)序列中的剩余部分存入時(shí)，將對(duì)應(yīng)序列中的剩余部分存入R R中中13133535 40405757636383838484 96961515393961617979i ij jk k13131515 35353939404057576161 63637979838384849696有序序列的合并算法有序序列的合并算法Void mergeVoid merge

35、list alist a，list blist b，list clist c i=1 i=1；j=1; k=1;j=1; k=1; while while ian & jbn ian & jbn if( ai.key bj.key ) if( ai.key bj.key ) ck=ai; i+; k+; ck=ai; i+; k+; else else ck=aj; j+; k+; ck=aj; j+; k+; / /循環(huán)終了后能否一切記錄已存入循環(huán)終了后能否一切記錄已存入c c中？中？ 有序序列的合并算法有序序列的合并算法Void mergeVoid mergelist al

36、ist a，list blist b，list clist c / /循環(huán)終了后能否一切記錄已存入循環(huán)終了后能否一切記錄已存入c c中？中？ while( ian ) while( ian ) ck=ai; i+; k+; ck=ai; i+; k+; while( jbn ) while( jbn ) ck=bj; j+; k+; ck=bj; j+; k+; 寫出鍵值寫出鍵值8383，4040，6363，1313，8484，3535，9696，5757，3939，7979，6161，1515運(yùn)用二路歸并排序算法從小到大排序后各趟的結(jié)果。運(yùn)用二路歸并排序算法從小到大排序后各趟的結(jié)果。知一組鍵

37、值序列知一組鍵值序列1313，1212，1616，1717，1515，1414，1111，試采用二路歸并排序法對(duì)該組序列作升序排序試采用二路歸并排序法對(duì)該組序列作升序排序并給出每一趟的排序結(jié)果并給出每一趟的排序結(jié)果知一組鍵值序列知一組鍵值序列(26(26，2121，3232，5656，7878，8989，90)90)，試采用二路歸并排序法對(duì)該組序列試采用二路歸并排序法對(duì)該組序列 作升序排序，作升序排序，并給出每一趟的排序結(jié)果。并給出每一趟的排序結(jié)果。7.6 7.6 分配排序分配排序 -箱桶排序箱桶排序箱排序也稱桶排序箱排序也稱桶排序算法思想：算法思想：設(shè)置假設(shè)干個(gè)箱子，依次掃描待排序記錄，把關(guān)

38、鍵字設(shè)置假設(shè)干個(gè)箱子，依次掃描待排序記錄，把關(guān)鍵字等于等于K K的記錄全部裝入第的記錄全部裝入第k k個(gè)箱子分配過程，然后個(gè)箱子分配過程，然后依次將各個(gè)非空的箱子首尾銜接起來搜集過程。依次將各個(gè)非空的箱子首尾銜接起來搜集過程。7.6 7.6 分配排序分配排序 -箱桶排序箱桶排序 78, 17, 39, 26, 72, 94, 21, 12 78, 17, 39, 26, 72, 94, 21, 12，23, 68 23, 68 B0B0B1B1B2B2B3B3B4B4B5B5B6B6 B7B7 B8B8 B9B926263994947878212172721717桶桶0-100-1020-30

39、20-3040-5040-5060-7060-7080-9080-90121223236868每個(gè)桶首尾相連，搜集即可得到有序序列每個(gè)桶首尾相連，搜集即可得到有序序列基數(shù)排序是一種借助基數(shù)排序是一種借助“多關(guān)鍵字排序的思想來實(shí)多關(guān)鍵字排序的思想來實(shí)現(xiàn)現(xiàn)“單關(guān)鍵字排序的內(nèi)部排序算法。單關(guān)鍵字排序的內(nèi)部排序算法。多關(guān)鍵字的排序多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序最低位優(yōu)先最低位優(yōu)先LSDLSD法法最高位優(yōu)先最高位優(yōu)先MSDMSD法法7.6 7.6 分配排序分配排序 -基數(shù)排序基數(shù)排序 無序序列對(duì)對(duì)K2排序排序?qū)?duì)K1排序排序?qū)?duì)K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,