數(shù)據(jù)結(jié)構(gòu)第十章

1、排序：排序：將一個數(shù)據(jù)元素（或記錄）的任意序列，重新將一個數(shù)據(jù)元素（或記錄）的任意序列，重新 排列成一個按關(guān)鍵字有序的序列排列成一個按關(guān)鍵字有序的序列內(nèi)部排序：內(nèi)部排序：將待排記錄存放在計算機(jī)隨機(jī)存儲器重進(jìn)將待排記錄存放在計算機(jī)隨機(jī)存儲器重進(jìn) 行的排序過程。行的排序過程。外部排序：外部排序：由于待排記錄的數(shù)量很大，以至內(nèi)存一次由于待排記錄的數(shù)量很大，以至內(nèi)存一次 不能容納全部記錄，在排序過程中尚需要不能容納全部記錄，在排序過程中尚需要 對外存進(jìn)行訪問的排序過程。對外存進(jìn)行訪問的排序過程。1第十章第十章 內(nèi)部排序內(nèi)部排序210.1 10.1 概述概述10.2 10.2 插入排序插入排序10.3

2、10.3 交換排序交換排序10.4 10.4 選擇排序選擇排序10.5 10.5 歸并排序歸并排序10.6 10.6 基數(shù)排序基數(shù)排序310.1 10.1 概述概述1 1、排序是計算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一、排序是計算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組組“無序無序”的記錄序列調(diào)整為的記錄序列調(diào)整為“按關(guān)鍵字有序按關(guān)鍵字有序”的記錄序的記錄序列。列。52，49，80，36，14，58，61，23，97，7514，23，36，49，52，58，61，75，80，97一般情況下，一般情況下，假設(shè)含假設(shè)含n n個記錄的序列為個記錄的序列為R1R1，R2R2，RnRn其相應(yīng)的關(guān)鍵字序列為

3、其相應(yīng)的關(guān)鍵字序列為 K1K1，K2K2，KnKn這些關(guān)鍵字相互之間可以進(jìn)行比較，這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在這樣一個關(guān)系：即在它們之間存在這樣一個關(guān)系：Kp1=Kp2=Kp1=Kp2=Kpn=Kpn按此固有關(guān)系將上式記錄序列重新排列為按此固有關(guān)系將上式記錄序列重新排列為Rp1,Rp2,Rp1,Rp2,Rpn,Rpn的操作稱作排序的操作稱作排序42 2、關(guān)鍵字、關(guān)鍵字?jǐn)?shù)據(jù)對象有多個屬性域，即多個數(shù)據(jù)成員組成，其中有一個數(shù)據(jù)對象有多個屬性域，即多個數(shù)據(jù)成員組成，其中有一個屬性域可以用來區(qū)分對象，作為排序依據(jù)，稱為屬性域可以用來區(qū)分對象，作為排序依據(jù)，稱為關(guān)鍵字關(guān)鍵字。關(guān)鍵字與

4、記錄之間是一對一的關(guān)系關(guān)鍵字與記錄之間是一對一的關(guān)系 稱稱主關(guān)鍵字主關(guān)鍵字關(guān)鍵字與記錄之間是一對多的關(guān)系關(guān)鍵字與記錄之間是一對多的關(guān)系 稱稱次關(guān)鍵字次關(guān)鍵字53、排序的目的是什么？、排序的目的是什么？ 便于查找便于查找4、排序算法的好壞如何衡量？、排序算法的好壞如何衡量？v 時間效率時間效率 排序速度（即排序所花費(fèi)的全部比較次數(shù)）排序速度（即排序所花費(fèi)的全部比較次數(shù)）v 空間效率空間效率 占內(nèi)存輔助空間的大小占內(nèi)存輔助空間的大小v 穩(wěn)定性穩(wěn)定性 若兩個記錄若兩個記錄A和和B的關(guān)鍵字相等，但排序后的關(guān)鍵字相等，但排序后A， B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。的先后次序保持不變，則稱

5、這種排序算法是穩(wěn)定的。65 5、什么叫內(nèi)部排序？什么叫外部排序、什么叫內(nèi)部排序？什么叫外部排序 若待排序記錄都在內(nèi)存中，稱內(nèi)部排序若待排序記錄都在內(nèi)存中，稱內(nèi)部排序 若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外若待排序記錄一部分在內(nèi)存，一部分在外存，則稱為外部排序。部排序。注：外部排序時，要將數(shù)據(jù)分批掉入內(nèi)存來排序，中間結(jié)果注：外部排序時，要將數(shù)據(jù)分批掉入內(nèi)存來排序，中間結(jié)果還要及時放入內(nèi)存，顯然外部排序要復(fù)雜得的多。還要及時放入內(nèi)存，顯然外部排序要復(fù)雜得的多。76 6、待排序記錄在內(nèi)存中怎樣存儲和處理、待排序記錄在內(nèi)存中怎樣存儲和處理（1 1） 順序排序順序排序 排序時直接移動記錄；排序

6、時直接移動記錄；（2 2）鏈表排序）鏈表排序 排序時只移動指針；排序時只移動指針；（3 3）地址排序）地址排序 排序時先移動地址，最后再移動記錄。排序時先移動地址，最后再移動記錄。注：地址排序中可以增設(shè)一維數(shù)組來專門存放記錄的地址。注：地址排序中可以增設(shè)一維數(shù)組來專門存放記錄的地址。8注：注：大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的( (便于直接移動元素便于直接移動元素) )Typedef struct /定義每個記錄（數(shù)據(jù)元素）的結(jié)構(gòu)定義每個記錄（數(shù)據(jù)元素）的結(jié)構(gòu) KeyType key ; /關(guān)鍵字關(guān)鍵字 InfoType otherinfo; /其它數(shù)據(jù)項(xiàng)其它

7、數(shù)據(jù)項(xiàng)RecordType ;Typedef struct /定義順序表的結(jié)構(gòu)定義順序表的結(jié)構(gòu) RecordType r MAXSIZE +1 ; /存儲順序表的向量存儲順序表的向量 /r0/r0一般作哨兵或緩沖區(qū)一般作哨兵或緩沖區(qū) int length ; /順序表的長度順序表的長度SqList ;# define MAXSIZE 20 /設(shè)記錄不超過設(shè)記錄不超過2020個個typedef int KeyType ; /設(shè)關(guān)鍵字為整型量（設(shè)關(guān)鍵字為整型量（intint型）型）9按排序的規(guī)則不同，可分為按排序的規(guī)則不同，可分為5類：類：插入排序插入排序交換排序（重點(diǎn)是快速排序）交換排序（重點(diǎn)是

8、快速排序）選擇排序選擇排序歸并排序歸并排序基數(shù)排序基數(shù)排序d關(guān)鍵字的位數(shù)關(guān)鍵字的位數(shù)(長度長度)按排序算法的時間復(fù)雜度不同，可分為按排序算法的時間復(fù)雜度不同，可分為3類：類：簡單的排序算法：時間效率低，簡單的排序算法：時間效率低，O(n2)先進(jìn)的排序算法先進(jìn)的排序算法: 時間效率高，時間效率高，O( nlog2n )基數(shù)排序算算法：時間效率高，基數(shù)排序算算法：時間效率高，O( dn)10插入排序的基本思想是：插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：插入排序有多種具體實(shí)現(xiàn)算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3) 表插入排序表插入排序 4) 希爾排序希

9、爾排序 每步將一個待排序的對象，每步將一個待排序的對象，按其關(guān)鍵碼大小，按其關(guān)鍵碼大小，插入到前面插入到前面已經(jīng)排好序的一組對已經(jīng)排好序的一組對象的適當(dāng)位置象的適當(dāng)位置上上，直到對象全部插入為止。，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。11基本思想： 假定前面m 個元素已經(jīng)排序； 取第(m+1) 個元素，插入到前面的適當(dāng)位置； 一直重復(fù)，到m=n 為止。 （初始情況下，m = 1）12例例1 1：關(guān)鍵字序列關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），）， 請寫出直接插入排序的中間過程序列。請寫

10、出直接插入排序的中間過程序列。【13】, 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【3, 5, 6, 9, 11，13，27, 31】 13void InsertSort(SqList &L) / 對順序表L作直接插入排序。 int i, j; for (i=2; i

11、=L.length; +i) if (LT(L.ri.key, L.ri-1.key) / 時，需將L.ri插入有序子表 L.r0 = L.ri; / 復(fù)制為哨兵 for (j=i-2; LT(L.r0.key, L.rj.key); -j) L.rj+1 = L.rj; / 記錄后移 L.rj+1 = L.r0; / 插入到正確位置 / InsertSort14* *表示后一個表示后一個25250 1 2 3 4 5 6252525494949252525* * *161616080808解：解：假設(shè)該序列已存入一維數(shù)組假設(shè)該序列已存入一維數(shù)組V7V7中，將中，將V0V0作為緩沖或作為緩沖或

12、暫存單元（暫存單元（TempTemp）。則程序執(zhí)行過程為：）。則程序執(zhí)行過程為：初態(tài)：初態(tài)：時間效率：時間效率： 因?yàn)樵谧顗那闆r下，所有元素的比較因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（次數(shù)總和為（0 02 2n)O(nn)O(n2 2) )。其他情況下。其他情況下還要加上移動元素的次數(shù)。還要加上移動元素的次數(shù)。 空間效率：空間效率：因?yàn)閮H占用因?yàn)閮H占用1 1個緩沖單元個緩沖單元算法的穩(wěn)定性：算法的穩(wěn)定性：因?yàn)橐驗(yàn)?525* *排序后仍然在排序后仍然在2525的后面。的后面。特點(diǎn)：因?yàn)樘攸c(diǎn)：因?yàn)镽1R1i-1i-1是一個按關(guān)鍵字有序的有序是一個按關(guān)鍵字有序的有序序列，則可以利用折半查找實(shí)現(xiàn)

13、在序列，則可以利用折半查找實(shí)現(xiàn)在R1R1i-1i-1中查中查找找RiRi的插入位置，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩宓牟迦胛恢?，如此?shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉Ｈ肱判?。限制：必須采用順序存儲方式。限制：必須采用順序存儲方式?516例：有例：有6個記錄，前個記錄，前5 個已排序的基礎(chǔ)上，對第個已排序的基礎(chǔ)上，對第6個記錄排序。個記錄排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 )( 42n/2時，表示結(jié)點(diǎn)時，

14、表示結(jié)點(diǎn)i為葉子結(jié)點(diǎn)。為葉子結(jié)點(diǎn)。44234561（大根堆）（大根堆）2345617有序列有序列T1=（08, 25, 49, 46, 58, 67）和序列）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判斷它們是否判斷它們是否 “堆堆”？（小根堆）（小根堆）（小頂堆）（小頂堆） （最小堆）（最小堆）（大頂堆）（大頂堆）（最大堆）（最大堆）45非終端結(jié)點(diǎn)非終端結(jié)點(diǎn)123456例：例：關(guān)鍵字序列關(guān)鍵字序列T= (21，25，49，25*，16，08），請建），請建大根堆大根堆。解：解：為便于理解，先將原始序列畫成完全二叉樹的形式：為便于理解，先將原始序列畫成完全二叉樹的形

15、式：注：注：終端結(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)整； 21小于小于25和和49，要調(diào)整！，要調(diào)整！而且而且21還應(yīng)當(dāng)向下比較！還應(yīng)當(dāng)向下比較！46471234561365424812345613654249123456136542501234561365425112345613654252歸并排序的基本思想是：歸并排序的基本思想是：將兩個（或以上）的有序?qū)蓚€（或以上）的有序表組成新的有序表。表組成新的有序表。更實(shí)際的意義：更實(shí)際的意義：可以把一

16、個長度為可以把一個長度為n 的無序序列看成是的無序序列看成是 n 個長度為個長度為 1 的有序子序列的有序子序列 ，首先做兩兩歸并，得到，首先做兩兩歸并，得到 n / 2 個長度為個長度為 2 的子序列的子序列 ；再做兩兩歸并，；再做兩兩歸并，如此重復(fù)，直，如此重復(fù)，直到最后得到一個長度為到最后得到一個長度為 n 的有序序列。的有序序列。例：例：關(guān)鍵字序列關(guān)鍵字序列T= （21，25，49，25*，93，62，72，08，37，16，54），請給出歸并排序的具體實(shí)），請給出歸并排序的具體實(shí)現(xiàn)過程?，F(xiàn)過程。53然后對這個有序表進(jìn)行歸并，如何進(jìn)行？然后對這個有序表進(jìn)行歸并，如何進(jìn)行？可以進(jìn)行兩兩歸

17、并，設(shè)置兩個指針，分別指向可以進(jìn)行兩兩歸并，設(shè)置兩個指針，分別指向2121，和，和2525，然，然后把后把2121與與2525進(jìn)行比較，如果進(jìn)行比較，如果2121較小則把較小則把2121調(diào)出來，指針往后調(diào)出來，指針往后移，把移，把2525與與2525* *進(jìn)行比較，進(jìn)行比較，2525較小，調(diào)出來，指針后移至到較小，調(diào)出來，指針后移至到結(jié)束，然后把第二部分的數(shù)據(jù)調(diào)出來，則排序完成，然后再結(jié)束，然后把第二部分的數(shù)據(jù)調(diào)出來，則排序完成，然后再次進(jìn)行歸并，直到所有的數(shù)排序成功為止。次進(jìn)行歸并，直到所有的數(shù)排序成功為止。54各種內(nèi)部排序方法的比較各種內(nèi)部排序方法的比較 (教材教材P289）55快速排序快

18、速排序O(nlgn )O(nlgn) O(n2) O(lgn) 不穩(wěn)定不穩(wěn)定 堆排序堆排序 O(nlgn )O(nlgn ) 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)定 簡單選擇簡單選擇 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(n

19、2) O(n2) O(1）穩(wěn)定穩(wěn)定 7. 內(nèi)部排序的算法有哪些？56按排序的規(guī)則不同，可分為按排序的規(guī)則不同，可分為5類：類：插入排序插入排序交換排序（重點(diǎn)是快速排序）交換排序（重點(diǎn)是快速排序）選擇排序選擇排序歸并排序歸并排序基數(shù)排序基數(shù)排序d關(guān)鍵字的位數(shù)關(guān)鍵字的位數(shù)(長度長度)按排序算法的時間復(fù)雜度不同，可分為按排序算法的時間復(fù)雜度不同，可分為3類：類：簡單的排序算法：時間效率低，簡單的排序算法：時間效率低，O(n2)先進(jìn)的排序算法先進(jìn)的排序算法: 時間效率高，時間效率高，O( nlog2n )基數(shù)排序算算法：時間效率高，基數(shù)排序算算法：時間效率高，O( dn)57例：有例：有6個記錄，前個記錄，前5 個已排序的基礎(chǔ)上，對第個已排序的基礎(chǔ)上，對第6個記錄排序。個記錄排序。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42