大學(xué)數(shù)據(jù)結(jié)構(gòu)課件--第10章內(nèi)部排序

1、1 10.1 10.1 概述概述 10.2 10.2 插入排序插入排序 10.3 10.3 交換排序交換排序 10.4 10.4 選擇排序選擇排序 10.5 10.5 歸并排序歸并排序 10.6 10.6 基數(shù)排序基數(shù)排序（直接插入排序、希爾排序）（直接插入排序、希爾排序）（起泡排序、快速排序）（起泡排序、快速排序）（直接選擇排序、堆排序）（直接選擇排序、堆排序）第第10章章 內(nèi)部排序內(nèi)部排序21. 什么是排序？什么是排序？ 將一組雜亂無章的將一組雜亂無章的數(shù)據(jù)數(shù)據(jù)按一定的按一定的規(guī)律規(guī)律順次排列起來。順次排列起來。2. 排序的目的是什么？排序的目的是什么？存放在數(shù)據(jù)表中存放在數(shù)據(jù)表中按關(guān)鍵字

2、排序按關(guān)鍵字排序3. .排序算法的好壞如何衡量？排序算法的好壞如何衡量？ 時(shí)間效率時(shí)間效率排序速度（即排序所花費(fèi)的全部比較次數(shù)）排序速度（即排序所花費(fèi)的全部比較次數(shù)） 空間效率空間效率占內(nèi)存輔助空間的大小占內(nèi)存輔助空間的大小 穩(wěn)定性穩(wěn)定性若兩個(gè)記錄若兩個(gè)記錄A A和和B B的關(guān)鍵字值相等，但排序后的關(guān)鍵字值相等，但排序后A A、B B 的先后次序保持不變，則稱此排序算法是穩(wěn)定的。的先后次序保持不變，則稱此排序算法是穩(wěn)定的。 便于查找！便于查找！10.1 概述概述3若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序；若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。

3、若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。注：注：外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及外部排序時(shí)，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時(shí)放入外存，顯然外部排序要復(fù)雜得多。時(shí)放入外存，顯然外部排序要復(fù)雜得多。 5.待排序記錄在內(nèi)存中怎樣存儲(chǔ)和處理？大多數(shù)排序算法都有兩個(gè)基本的操作：大多數(shù)排序算法都有兩個(gè)基本的操作：（1）比較兩個(gè)關(guān)鍵字的大小）比較兩個(gè)關(guān)鍵字的大?。?）將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置）將記錄從一個(gè)位置移動(dòng)到另一個(gè)位置（1）順序存儲(chǔ)順序存儲(chǔ) （2）靜態(tài)鏈表）靜態(tài)鏈表 （3）地址）地址4. 什么叫內(nèi)部排序？什么叫外部排序？10.1 概述概述4注：

4、注：大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的大多數(shù)排序算法都是針對(duì)順序表結(jié)構(gòu)的( (便于直接移動(dòng)元素便于直接移動(dòng)元素) )Typedef struct /定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu)定義每個(gè)記錄（數(shù)據(jù)元素）的結(jié)構(gòu) KeyType key ; /關(guān)鍵字關(guān)鍵字 InfoType otherinfo; /其它數(shù)據(jù)項(xiàng)其它數(shù)據(jù)項(xiàng)RecordType ;Typedef struct /定義順序表的結(jié)構(gòu)定義順序表的結(jié)構(gòu) RecordType r MAXSIZE +1 ; /存儲(chǔ)順序表的向量存儲(chǔ)順序表的向量 /r0/r0一般作哨兵或緩沖區(qū)一般作哨兵或緩沖區(qū) int length ; /順序表的長(zhǎng)度順序表的長(zhǎng)度Sq

5、List ;# define MAXSIZE 20 /設(shè)記錄不超過設(shè)記錄不超過2020個(gè)個(gè)typedef int KeyType ; /設(shè)關(guān)鍵字為整型量（設(shè)關(guān)鍵字為整型量（intint型）型）6. 順序存儲(chǔ)（順序表）的抽象數(shù)據(jù)類型10.1 概述概述5插入排序的基本思想是：插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：插入排序有多種具體實(shí)現(xiàn)算法： （1）直接插入排序）直接插入排序 （2） 折半插入排序折半插入排序 （3） 表插入排序表插入排序 （4）希爾排序）希爾排序 每步將一個(gè)待排序的對(duì)象，每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，按其關(guān)鍵碼大小，插入到前面插入到前面已經(jīng)排好序的一組對(duì)象已經(jīng)

6、排好序的一組對(duì)象的適當(dāng)位置上的適當(dāng)位置上，直到對(duì)象全部插入為止。，直到對(duì)象全部插入為止。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。簡(jiǎn)言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的。10.2 插入排序插入排序6直接插入排序是直接插入排序是最簡(jiǎn)單的排序方法新元素插入到哪里？新元素插入到哪里？在已形成的在已形成的有序表中有序表中線性查找線性查找，并在適當(dāng)位置插入，并在適當(dāng)位置插入，把原來位置上的元素向后把原來位置上的元素向后順移順移。10.2.1 直接插入排序直接插入排序7例例1 1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11）， 請(qǐng)寫出直接插入排序的中間過程序列。 【13】

7、, 6, 3, 31, 9, 27, 5, 11第一趟直接插入排序第一趟直接插入排序【6, 13】, 3, 31, 9, 27, 5, 11第二趟直接插入排序第二趟直接插入排序【3, 6, 13】, 31, 9, 27, 5, 11第三趟直接插入排序第三趟直接插入排序【3, 6, 13，31】, 9, 27, 5, 11第四趟直接插入排序第四趟直接插入排序【3, 6, 9, 13，31】, 27, 5, 11第五趟直接插入排序第五趟直接插入排序【3, 6, 9, 13，27, 31】, 5, 11第六趟直接插入排序第六趟直接插入排序【3, 5, 6, 9, 13，27, 31】, 11第七趟直

8、接插入排序第七趟直接插入排序【3, 5, 6, 9, 11，13，27, 31】 10.2.1 直接插入排序直接插入排序8例例2 2：關(guān)鍵字序列關(guān)鍵字序列T= （21，25，49，25*，16，08），），請(qǐng)寫出直接插入排序的具體實(shí)現(xiàn)過程。請(qǐng)寫出直接插入排序的具體實(shí)現(xiàn)過程。0 1 2 3 4 5 6254925*1608解：解：假設(shè)該序列已存入一維數(shù)組假設(shè)該序列已存入一維數(shù)組V7V7中，將中，將V0V0作為緩沖或暫存單元作為緩沖或暫存單元（TempTemp）。則程序執(zhí)行過程為：）。則程序執(zhí)行過程為：初態(tài)：初態(tài)：時(shí)間效率：時(shí)間效率： 因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為因?yàn)樵谧顗那闆r下，所

9、有元素的比較次數(shù)總和為（0 01 1n-1)O(nn-1)O(n2 2) )。其他情況下還要加上移動(dòng)元素。其他情況下還要加上移動(dòng)元素的次數(shù)。的次數(shù)。 空間效率：空間效率：因?yàn)閮H占用因?yàn)閮H占用1 1個(gè)緩沖單元個(gè)緩沖單元算法的穩(wěn)定性：算法的穩(wěn)定性：因?yàn)橐驗(yàn)?525* *排序后仍然在排序后仍然在2525的后面。的后面。9void Insertsort() int i,j; for(i=2;i=N;i+) p0=pi; j=i-1; while(p0 pj) pj+1=pj; j-; pj+1=p0; i ij jj jj j直接插入排序算法直接插入排序算法10基本思想基本思想 先將整個(gè)待排記錄序列分

10、割成若干子序列先將整個(gè)待排記錄序列分割成若干子序列, ,分別進(jìn)行直分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄接插入排序，待整個(gè)序列中的記錄“基本有序基本有序”時(shí)，再對(duì)時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。全體記錄進(jìn)行一次直接插入排序。技巧技巧 子序列的構(gòu)成不是簡(jiǎn)單地子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割逐段分割”，而是將相隔某，而是將相隔某個(gè)增量個(gè)增量dkdk的記錄組成一個(gè)子序列的記錄組成一個(gè)子序列, ,讓增量讓增量dkdk逐趟縮短（例如逐趟縮短（例如依次取依次取5,3,15,3,1），直到），直到dkdk1 1為止。為止。10.2.3 希爾（希爾（shell）排序）排序（又稱縮小增量排序）（又稱縮小

11、增量排序）1138例：關(guān)鍵字序列例：關(guān)鍵字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），請(qǐng)寫），請(qǐng)寫出希爾排序的具體實(shí)現(xiàn)過程。出希爾排序的具體實(shí)現(xiàn)過程。0123456789104938659776132749*5504初態(tài)：初態(tài)：第第1趟趟 (dk=5)第第2趟趟 (dk=3)第第3趟趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 4

12、913382749* 6555970476算法分析：算法分析：開始時(shí)開始時(shí)dk 的值較大，子序列中的對(duì)象較少，排序速度較快；的值較大，子序列中的對(duì)象較少，排序速度較快； 隨著排序進(jìn)展，隨著排序進(jìn)展，dk 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多， 由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度 仍然很快。仍然很快。12 兩兩比較待排序記錄的關(guān)鍵碼，兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排

13、好序?yàn)橹?。則交換之，直到所有記錄都排好序?yàn)橹埂＝粨Q排序的主要算法有：交換排序的主要算法有： （1）冒泡排序）冒泡排序 （2）快速排序）快速排序交換排序的基本思想是：交換排序的基本思想是：10.3 交換排序交換排序13基本思路：基本思路：每趟不斷將記錄兩兩比較，并按每趟不斷將記錄兩兩比較，并按“前小后大前小后大” （或（或“前大后小前大后小”）規(guī)則交換。）規(guī)則交換。例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫出 冒泡排序的具體實(shí)現(xiàn)過程。21，25，49， 25*，16，0821，25， 25，49， 25* ,49， 16， 49， 08 ， 49第第1趟冒泡排序結(jié)果趟冒泡

14、排序結(jié)果21，25， 25* , 16， 08 ， 4910.3.1 冒泡排序冒泡排序14void bsort (int a , int n) int temp,i,j; int flag; /交換標(biāo)志交換標(biāo)志 for(j=1;j=n-1;j+) /最多做最多做n-1趟排序趟排序 flag=0; /本趟排序開始前，交換標(biāo)志應(yīng)為本趟排序開始前，交換標(biāo)志應(yīng)為0 for(i=1;iai+1) /交換記錄交換記錄 temp=ai; ai=ai+1; ai+1=temp; flag=1; /發(fā)生了交換，故將交換標(biāo)志置為真發(fā)生了交換，故將交換標(biāo)志置為真 if(flag= =0) break; /本趟排序未

15、發(fā)生交換，提前終止算法本趟排序未發(fā)生交換，提前終止算法 冒泡排序的算法冒泡排序的算法15 從待排序列中任取一個(gè)元素 (例如取第一個(gè)) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了。基本思想：基本思想：例1：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫出 快速排序的算法步驟。(設(shè)以首元素為樞軸中心)10.3.2 快速排序快速排序21， 25， 49， 25*，16， 08i ij j08， 25， 49， 25*，16， i ij j08， ， 49，

16、 25*，16， 25 j ji i08，16 ， 49， 25*， ， 25 j ji i08，16 ， ， 25*， 49 ， 25 j ji i08，16 ， ，25*， 49， 25 j ji i0821,0821,2521,所以交換，所以交換，j-j-1621,1621,4921,所以交換，所以交換，j-j-第第1趟快速排序結(jié)果趟快速排序結(jié)果08，16，21，25*， 49， 25第第1趟快速排序結(jié)果趟快速排序結(jié)果 08，16，21，25*， 49， 25，分別對(duì)分別對(duì) 08，16 和和 25*，49， 25進(jìn)行快速排序進(jìn)行快速排序?qū)?duì)08，16 進(jìn)行快速排序進(jìn)行快速排序 08， 1

17、6i ij j08， 16i i j j0816,0816,不需要交換，不需要交換，j-j- 08，16 快速排序結(jié)果快速排序結(jié)果08，16對(duì)對(duì)25*，49， 25進(jìn)行快速排序進(jìn)行快速排序 25*， 49，25i ij j25*， 49，25i ij j2525* *=25,=25,不需要交換，不需要交換，j-j- 25*，49，25 快速排序結(jié)果快速排序結(jié)果25*，49，2525*， 49，25i ij j2525* *49,49,不需要交換，不需要交換，j-j-第第2趟快速排序結(jié)果趟快速排序結(jié)果 08，16，21，25*， 49，2518pivotkey=pivotkey=ri.keyri

18、.key; ; /取支點(diǎn)的關(guān)鍵碼存入取支點(diǎn)的關(guān)鍵碼存入pivotkeypivotkey變量變量while(i j)while(i j) /從表的兩端交替地向中間掃描從表的兩端交替地向中間掃描while(i=pivotkey ) while(i=pivotkey ) ri=rj; ri=rj; /將比支點(diǎn)小的記錄交換到低端；將比支點(diǎn)小的記錄交換到低端；while(ij & ri.key=pivotkey) while(ij & ri.key=pivotkey) rj=ri; rj=ri; /將比支點(diǎn)大的記錄交換到高端；將比支點(diǎn)大的記錄交換到高端； ri=r0; ri=r0; /支

19、點(diǎn)記錄到位；支點(diǎn)記錄到位；return i; return i; /返回支點(diǎn)記錄所在位置。返回支點(diǎn)記錄所在位置。 /int int (SqList &L,int i,int(SqList &L,int i,int j j) ) /一趟快排一趟快排 r0=ri; r0=ri; /以子表的首記錄作為支點(diǎn)記錄，放入以子表的首記錄作為支點(diǎn)記錄，放入r0r0單元單元一趟快速排序算法（針對(duì)一個(gè)子表的操作）每一趟的子表的形成是采用從兩頭向中間交替式逼近法；每一趟的子表的形成是采用從兩頭向中間交替式逼近法；由于每趟中對(duì)各子表的操作都相似，主程序可采用遞歸算法。由于每趟中對(duì)各子表的操作都相似，主

20、程序可采用遞歸算法?？焖倥判蛩惴焖倥判蛩惴?9void QSort ( SqList &L, int i, int j ) if ( i 1/對(duì)順序表對(duì)順序表L中的子序列中的子序列r ij 作快速排序作快速排序/一趟快排，將一趟快排，將r 一分為二一分為二/在左子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為在左子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為1/在右子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為在右子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為1/QSort快速排序算法快速排序算法20選擇排序有多種具體實(shí)現(xiàn)算法選擇排序有多種具體實(shí)現(xiàn)算法 （1）簡(jiǎn)單選擇排序）簡(jiǎn)單選擇排序 （2）堆排序）堆排序每一趟在后面n-i個(gè)待排記錄中選取關(guān)鍵字最

21、小的記錄作為有序序列中的第i個(gè)記錄。10.4 選擇排序選擇排序21思路簡(jiǎn)單：思路簡(jiǎn)單：每經(jīng)過一趟比較就找出一個(gè)最小值，與待每經(jīng)過一趟比較就找出一個(gè)最小值，與待 排序列最前面的位置互換即可。排序列最前面的位置互換即可。首先，在n個(gè)記錄中選擇最小者放到r1位置；然后，從剩余的n-1個(gè)記錄中選擇最小者放到r2位置；如此進(jìn)行下去，直到全部有序?yàn)橹埂?0.4.1 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序22例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)給出 簡(jiǎn)單選擇排序的具體實(shí)現(xiàn)過程。原始序列：原始序列： 21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25

22、，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49最小值最小值 0808 與與r1r1交換位置交換位置10.4.1 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序23SELECTSORT( ) int i,j,k; for (i=1;in;i+) k=i; for (j=i+1;j=n;j+) if (p j p k ) k=j; if (k!=i) temp=p i ; p i =p k ; p k =temp; /在在ririnn中選擇中選擇keykey最小的記錄最小的記錄/與第與第i

23、 i個(gè)記錄交換個(gè)記錄交換簡(jiǎn)單選擇排序的算法簡(jiǎn)單選擇排序的算法241. 1. 什么是堆？什么是堆？堆的定義：堆的定義：設(shè)有設(shè)有n個(gè)元素的序列個(gè)元素的序列 k1，k2，kn，當(dāng)且僅，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。 ki k2iki k2i+1ki k2iki k2i+1或者或者i=1, 2, n/2解釋：解釋：如果讓滿足以上條件的元素序列如果讓滿足以上條件的元素序列 （k1，k2，kn） 順次排成一棵順次排成一棵完全二叉樹完全二叉樹，則此樹的特點(diǎn)是：，則此樹的特點(diǎn)是： 樹中所有根結(jié)點(diǎn)的值均大于（或小于）其左右孩子，樹中所有根結(jié)點(diǎn)的值均大于（或小于）其左右孩子

24、， 此樹的此樹的根結(jié)點(diǎn)（即堆頂）根結(jié)點(diǎn)（即堆頂）必最大（或最小）。必最大（或最?。?。2. 2. 怎樣建堆？怎樣建堆？3. 3. 怎樣堆排序？怎樣堆排序？10.4.2 堆排序堆排序25234561（大根堆）（大根堆）2345617例：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判斷它們是否 “堆”？（小根堆）（小根堆）（小頂堆）（小頂堆） （最小堆）（最小堆）（大頂堆）（大頂堆）（最大堆）（最大堆）10.4.2 堆排序堆排序26步驟：步驟：從從最后一個(gè)最后一個(gè)非終端結(jié)點(diǎn)非終端結(jié)點(diǎn)開始開始往前往前逐步調(diào)整，讓每個(gè)

25、逐步調(diào)整，讓每個(gè) 雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。雙親大于（或小于）子女，直到根結(jié)點(diǎn)為止。123456例：例：關(guān)鍵字序列關(guān)鍵字序列T= (21，25，49，25*，16，08），請(qǐng)建大根堆。），請(qǐng)建大根堆。解：為便于理解，先將原始序列畫成完全二叉樹的形式為便于理解，先將原始序列畫成完全二叉樹的形式完全二叉樹的最后一個(gè)非終端完全二叉樹的最后一個(gè)非終端結(jié)點(diǎn)編號(hào)必為結(jié)點(diǎn)編號(hào)必為 n/2n/2 ！注：注：終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(dú)調(diào)整。終端結(jié)點(diǎn)（即葉子）沒有任何子女，無需單獨(dú)調(diào)整。 49大于大于08，不必調(diào)整；，不必調(diào)整； 25大于大于25*和和16，也不必調(diào)整；，也不必調(diào)整；

26、21小于小于25和和49，要調(diào)整！，要調(diào)整！而且而且21還應(yīng)當(dāng)向下比較！還應(yīng)當(dāng)向下比較！2. 怎樣建堆？怎樣建堆？27關(guān)鍵：將堆的當(dāng)前頂點(diǎn)輸出后，如何將剩余序列 重新調(diào)整為堆？方法：將當(dāng)前頂點(diǎn)與堆尾記錄交換，然后仿建堆 動(dòng)作，從上至下新調(diào)整，如此反復(fù)直至排 序結(jié)束。3. 怎樣進(jìn)行堆排序？怎樣進(jìn)行堆排序？28刪除49123456136542例：對(duì)剛才建好的大根堆進(jìn)行排序例：對(duì)剛才建好的大根堆進(jìn)行排序29刪除2512345613654212345630歸并排序的基本思想是：歸并排序的基本思想是：將兩個(gè)（或以上）的有序表 組成新的有序表。更實(shí)際的意義：更實(shí)際的意義：可以把一個(gè)長(zhǎng)度為可以把一個(gè)長(zhǎng)度為n

27、 的無序序列看成是的無序序列看成是 n 個(gè)個(gè)長(zhǎng)度為長(zhǎng)度為 1 的有序子序列的有序子序列 ，首先做兩兩歸并，得到，首先做兩兩歸并，得到 n / 2 個(gè)個(gè)長(zhǎng)度為長(zhǎng)度為 2 的子序列的子序列 ；再做兩兩歸并，；再做兩兩歸并，如此重復(fù)，直到最，如此重復(fù)，直到最后得到一個(gè)長(zhǎng)度為后得到一個(gè)長(zhǎng)度為 n 的有序序列。的有序序列。10.5 歸并排序歸并排序31例：關(guān)鍵字序列關(guān)鍵字序列T= （21，25，49，25*，93，62，72，08，37，16，54），請(qǐng)給出歸并排序的具體實(shí)現(xiàn)過程。），請(qǐng)給出歸并排序的具體實(shí)現(xiàn)過程。32要討論的問題：要討論的問題：1.什么是“多關(guān)鍵字”排序？實(shí)現(xiàn)方法？2.單邏輯關(guān)鍵字怎樣

28、“按位值”排序？基數(shù)排序的基本思想是：基數(shù)排序的基本思想是：借助多關(guān)鍵字排序的思想對(duì)單邏輯關(guān)鍵字進(jìn)行排序。即：用關(guān)鍵字不同的位值進(jìn)行排序。10.6 基數(shù)排序基數(shù)排序33例例1：對(duì)一副撲克牌該如何排序？：對(duì)一副撲克牌該如何排序？ 若規(guī)定花色和面值的順序關(guān)系為：若規(guī)定花色和面值的順序關(guān)系為： 花色：花色： 面值：面值：2 3 4 5 6 7 8 9 10 J Q K A多關(guān)鍵字排序的實(shí)現(xiàn)方法通常有兩種： 最高位優(yōu)先法最高位優(yōu)先法MSD (Most Significant Digit first) 最低位優(yōu)先法最低位優(yōu)先法LSD (Least Significant Digit first)1.什么

29、是什么是“多關(guān)鍵字多關(guān)鍵字”排序？實(shí)現(xiàn)方法？排序？實(shí)現(xiàn)方法？34例：對(duì)一副撲克牌該如何排序？例：對(duì)一副撲克牌該如何排序？答答：若規(guī)定花色為第一關(guān)鍵字（高位），面值為第二關(guān)鍵字（低位），若規(guī)定花色為第一關(guān)鍵字（高位），面值為第二關(guān)鍵字（低位），則使用則使用MSD和和LSD方法都可以達(dá)到排序目的。方法都可以達(dá)到排序目的。MSD方法的思路：方法的思路：先設(shè)立先設(shè)立4個(gè)花色個(gè)花色“箱箱”，將全部牌按花色分別歸入，將全部牌按花色分別歸入4個(gè)箱內(nèi)（每個(gè)箱中有個(gè)箱內(nèi)（每個(gè)箱中有13張牌）；然后對(duì)每個(gè)箱中的牌按面值進(jìn)行排序。張牌）；然后對(duì)每個(gè)箱中的牌按面值進(jìn)行排序。LSD方法的思路：方法的思路：先按面值分成先

30、按面值分成13堆（每堆堆（每堆4張牌），然后對(duì)每堆中的張牌），然后對(duì)每堆中的牌按花色進(jìn)行排序。牌按花色進(jìn)行排序。1.什么是什么是“多關(guān)鍵字多關(guān)鍵字”排序？實(shí)現(xiàn)方法？排序？實(shí)現(xiàn)方法？35設(shè)設(shè)n n 個(gè)記錄的序列為：個(gè)記錄的序列為： V V0 0, , V V1 1, , , , V Vn n-1-1 ，可以把每個(gè)記錄，可以把每個(gè)記錄V Vi i 的的單關(guān)鍵碼單關(guān)鍵碼 K Ki i 看成是一個(gè)看成是一個(gè)d d元組元組（K Ki i1 1, , K Ki i2 2, , , , K Ki id d），則其中，則其中的每一個(gè)分量的每一個(gè)分量K Ki ij j ( 1( 1 j j d d ) ) 也可

31、看成是一個(gè)關(guān)鍵字。也可看成是一個(gè)關(guān)鍵字。4注注1 1： K Ki i1 1最高位，最高位，K Ki id d最低位；最低位；K Ki i共有共有d d位，可看成位，可看成d d元組；元組；注注2： 每個(gè)分量每個(gè)分量K Ki ij j (1 j d ) 有有radix種取值，則稱種取值，則稱radix為基數(shù)。為基數(shù)。26(9, 8, 4)(0, 1, , 9)（a, b, , z）(d, i, a, n)310例例1：關(guān)鍵碼關(guān)鍵碼984可以看成是可以看成是 元組；基數(shù)元組；基數(shù)radix 為為 。例例2：關(guān)鍵碼關(guān)鍵碼dian可以看成是可以看成是 元組；基數(shù)元組；基數(shù)radix 為為 。思路：思路

32、：2.單邏輯關(guān)鍵字怎樣單邏輯關(guān)鍵字怎樣“按位值按位值”排序？排序？36例：例：初始關(guān)鍵字序列初始關(guān)鍵字序列T=（32, 13, 27, 32*, 19，33），），請(qǐng)分別用請(qǐng)分別用MSD和和LSD進(jìn)行排序。進(jìn)行排序。法法1（MSD）：）：原始序列：原始序列：32, 19, 27, 32*, 13， 33 先按高位先按高位K Ki i1 1 排序：排序：（19, 13）, 27, （32, 32*，33） 再按低位再按低位K Ki i2 2 排序排序 ： 13, 19 ， 27, 32, 32*, 33法法2（LSD）：）： 原始序列：原始序列： 32, 13, 27, 32*, 19 ，33

33、先按低位先按低位K Ki i2 2排序：排序： 32, 32*, 13, 33, 27, 19 再按高位再按高位K Ki i1 1排序：排序： 13, 19 , 27, 32, 32*, 33這種這種LSD排序方法稱為：排序方法稱為：基數(shù)排序基數(shù)排序用鏈隊(duì)列來實(shí)現(xiàn)基數(shù)排序用鏈隊(duì)列來實(shí)現(xiàn)基數(shù)排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序2.單邏輯關(guān)鍵字怎樣單邏輯關(guān)鍵字怎樣“按位值按位值”排序？排序？37例:請(qǐng)實(shí)現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序：請(qǐng)實(shí)現(xiàn)以下關(guān)鍵字序列的鏈?zhǔn)交鶖?shù)排序： T=T=（614614，738738，921921，485485，637637， 101101，215215，530530，790790

34、，306306）e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9r0f e eifi+1 530790921101614485215306637738r038e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9530790921101614485215306637738eifi+1 530790921101614485215306637738r0

35、r0第一趟收集的結(jié)果第一趟收集的結(jié)果39530790921101614485215306637738e0 e1 e2 e3 e4 e5 e6 e7 e8 e9614738921485637101215530790306f0 f1 f2 f3 f4 f5 f6 f7 f8 f9eifi+1 530790921101614485215306637738r0r0第二趟收集的結(jié)果第二趟收集的結(jié)果40簡(jiǎn)單排序簡(jiǎn)單排序 O(n)O(n2) O(n2) O(1） 穩(wěn)定穩(wěn)定 快速排序快速排序O(nlgn )O(nlgn) O(n2) O(lgn) 不穩(wěn)定不穩(wěn)定 堆排序堆排序 O(nlgn )O(nlgn )

36、O(nlgn) O(1）不穩(wěn)定不穩(wěn)定 歸并排序歸并排序 O(nlgn ) O(nlgn ) O(nlgn) O(n）穩(wěn)定穩(wěn)定基數(shù)排序基數(shù)排序O(d(n+rd) O(d(n+rd) O(d(n+rd) O(rd)穩(wěn)定穩(wěn)定 簡(jiǎn)單選擇簡(jiǎn)單選擇 O(n2) O(n2) O(n2) O(1） 不穩(wěn)定不穩(wěn)定 直接插入直接插入 O(n) O(n2) O(n2) O(1）穩(wěn)定穩(wěn)定 折半插入折半插入O(nlgn )O(nlgn )O(nlgn )O(1）穩(wěn)定穩(wěn)定冒泡冒泡 O(n) O(n2) O(n2) O(1）穩(wěn)定穩(wěn)定 各種內(nèi)部排序方法的比較各種內(nèi)部排序方法的比較411. 以關(guān)鍵字序列（以關(guān)鍵字序列（256，

37、301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行直接插入排序的）為例，寫出執(zhí)行直接插入排序的各趟各趟排序過程。排序過程。原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438129

38、129，256256，301301，751751，937937，863863，742742，694694，076076，438438129129，256256，301301，751751，937937，863863，742742，694694，076076，438438129129，256256，301301，751751，863863，937937，742742，694694，076076，438438129129，256256，301301，742742，751751，863863，937937，694694，076076，438438129129，256256，301301，694694

39、，742742，751751，863863，937937，076076，438438076076，129129，256256，301301，694694，742742，751751，863863，937937，438438076076，129129，256256，301301，438438，694694，742742，751751，863863，937937第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟 練習(xí)練習(xí)42Q,P,R,Y,S ,XC,M,F,H,A,D,P,Q,R,2. 欲將序列（欲將序列（Q, H, C, Y, P, A, M, S, R

40、, D, F, X）中的關(guān)鍵碼按字）中的關(guān)鍵碼按字母升序重排，則初始步長(zhǎng)為母升序重排，則初始步長(zhǎng)為4的希爾排序第一趟的結(jié)果是？的希爾排序第一趟的結(jié)果是？答：答：原始序列：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shellshell一趟后：一趟后：A,D,H,C,F,M,S,X ,Y第一趟希爾排序結(jié)果：第一趟希爾排序結(jié)果：P A C S Q D F X R H M Y練習(xí)練習(xí)433 3、設(shè)文件有、設(shè)文件有1010個(gè)記錄，其關(guān)鍵字值分別個(gè)記錄，其關(guān)鍵字值分別為為:37,23,7,79,29,43,73,19,31,61,:37,23,7,79,29,43,

41、73,19,31,61,試給出冒泡排序法按非遞減的次試給出冒泡排序法按非遞減的次序進(jìn)行排序過程中的每一趟結(jié)果序列。序進(jìn)行排序過程中的每一趟結(jié)果序列。 4 4、有一組鍵值、有一組鍵值2525，8484，2121，4747，1515，2727，6868，3535，2424，采用快速排序方，采用快速排序方法由小到大進(jìn)行排序，請(qǐng)寫出第一趟排序過程中鍵值的移動(dòng)情況。法由小到大進(jìn)行排序，請(qǐng)寫出第一趟排序過程中鍵值的移動(dòng)情況。 5 5、已知有十個(gè)待排序的記錄，其關(guān)鍵字分別為：、已知有十個(gè)待排序的記錄，其關(guān)鍵字分別為：256256，301301，751751，129129，937,863937,863，742742，694694，076076，438438請(qǐng)用快速排序的方法將它們從小到大請(qǐng)用快速排序的方法將它們從小到大排列。排列。6 6、設(shè)待排序的記錄共、設(shè)待排序的記錄共7 7個(gè)，排序碼分別為個(gè)，排序碼分別為8 8，3 3，2 2，5 5，9 9，1 1，6 6。 (1) (1) 寫出直接插入排序的全過程，要求按遞減順序排序。寫出直接插入排序的全過程，要求按遞減順序排序。 (2) (2) 寫出直接選擇排序的全過程，要求按遞減順序排序。寫出直接選擇排序的全過程，要求按遞減順序排序。練習(xí)練習(xí)447 7、設(shè)文件有、設(shè)文件有1212個(gè)記錄個(gè)記錄, ,其關(guān)鍵