(數(shù)據(jù)結(jié)構(gòu))第9章排序--2

1、第10章 排序Sort第十章 排序(Sort)目錄10.1 排序概述10.2 插入排序10.3 交換排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序排序排序10.4 選擇排序10.4.1 簡(jiǎn)單選擇排序10.4.2 堆排序選擇排序選擇排序簡(jiǎn)單選擇排序算法思想：8 設(shè)：排序區(qū)間R1.n;8 在排序的過(guò)程中，整個(gè)排序區(qū)間被分為兩個(gè)子區(qū)間：有序區(qū)R1.i-1和無(wú)序區(qū)Ri.n;8 共進(jìn)行n1趟排序，每趟排序都是選擇無(wú)序區(qū)的最小記錄Rmin；將Rmin與無(wú)序區(qū)的第一條記錄位置互換，使得無(wú)序區(qū)長(zhǎng)度減1，有序區(qū)長(zhǎng)度增1。RR1R2Ri-1RiRi+1Rn-1Rn012i-1ii+1n-1n選擇排序選

2、擇排序 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序有序區(qū)無(wú)序區(qū)8765432104567215851123345j 第一趟第一趟i=1i選擇排序選擇排序 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序8765432107367215851123345 第一趟第一趟i=18765432107367455851213312j 第二趟第二趟i=2i選擇排序選擇排序 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序8765432107367215851453312 第一趟第一趟i=18765432107367455851332112j 第三趟第三趟i=3i8765432107367335851452112 第二趟第二趟i=2選擇排序選擇排序 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排

3、序8765432107367215851453312 第一趟第一趟i=18765432107367585851332112 第三趟第三趟i=38765432107367335851452112 第二趟第二趟i=28765432107367583351452112j 第四趟第四趟i=4i選擇排序選擇排序 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序算法：void SelectSort( SqList &L ) /對(duì)順序表對(duì)順序表L作簡(jiǎn)單選擇排序作簡(jiǎn)單選擇排序 for(i=1; iL.length; i+) min=i; for(j=i+1;j=L.length;j+) /選最小的記錄選最小的記錄

4、 if(L.Rj.keyL.Rmin.key)min=j; if(i!=min)L.RminL.Ri;/與無(wú)序區(qū)第一條記錄交換與無(wú)序區(qū)第一條記錄交換 /end for 選擇排序選擇排序 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序性能分析：比較次數(shù)與表的初態(tài)無(wú)關(guān)： 最好的情況：表的初態(tài)恰好是正序排列 移動(dòng)次數(shù)：Mmin0最壞的情況：每趟都有移動(dòng)發(fā)生 移動(dòng)次數(shù)：Mmax3(n-1)平均O(n2), 不穩(wěn)定的排序方法2111)/n(n-i)(nCCn-i maxmin選擇排序選擇排序 簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序10.4 選擇排序10.4.1 簡(jiǎn)單選擇排序10.4.2 堆排序選擇排序選擇排序 10.4.2 堆

5、排序(Heap Sort ) 用建堆的方法來(lái)選擇待排序區(qū)間的最大或最小用建堆的方法來(lái)選擇待排序區(qū)間的最大或最小鍵值。鍵值。 一、堆定義一、堆定義 二、篩選操作二、篩選操作 三、建堆算法三、建堆算法 四、堆排序算法四、堆排序算法選擇排序選擇排序 堆排序堆排序 一、堆定義 設(shè)設(shè)n個(gè)元素的有限序列：個(gè)元素的有限序列：K1, K2, K3, . , Kn如果滿足如果滿足 KiK2i & KiK2i+1 其中其中1i1i n/2n/2 則稱這個(gè)序列為則稱這個(gè)序列為小根堆小根堆或或小頂堆小頂堆；如果滿足如果滿足 KiK2i & KiK2i+1 其中其中1i 1i n/2n/2 則稱這個(gè)序列

6、為則稱這個(gè)序列為大根堆大根堆或或大頂堆大頂堆；選擇排序選擇排序 堆排序堆排序8 回顧完全二叉樹的性質(zhì),8 編號(hào)為i的結(jié)點(diǎn), 其左孩子的編號(hào)為2i, 右孩子的編號(hào)為2i+18 如果將堆序列看成完全二叉樹的按層次遍歷序列 則這棵完全二叉樹上每個(gè)結(jié)點(diǎn)的值比左孩子和右孩子值都要大(大根堆), 或比左孩子和右孩子值都要小(小根堆)。選擇排序選擇排序 堆排序堆排序例：大根堆 75, 38, 62, 25, 16, 49 小根堆 15, 36, 39, 45, 36, 60, 48, 93, 53 3862251649752639264560154893536543210256216 49387576543

7、21026483945 602615893953選擇排序選擇排序 堆排序堆排序 二、篩選操作8 前提：根結(jié)點(diǎn)的左、右子樹都是堆，而根結(jié)點(diǎn)不滿足堆條件;8 將根調(diào)整到合適的位置，使得整個(gè)序列成為堆。263926456072489353選擇排序選擇排序 堆排序堆排序392645607248935326 對(duì)對(duì)小根堆小根堆來(lái)說(shuō)，篩選就是不斷地將樹根與來(lái)說(shuō)，篩選就是不斷地將樹根與較小較小的孩子的孩子交換位置，直至整個(gè)序列都滿足堆定義。交換位置，直至整個(gè)序列都滿足堆定義。選擇排序選擇排序 堆排序堆排序395345604893722626305348264518261572 對(duì)對(duì)大根堆大根堆來(lái)說(shuō)，篩選就是將

8、樹根與來(lái)說(shuō)，篩選就是將樹根與較大的孩較大的孩子子交換位置，直至整個(gè)序列都滿足堆定義。交換位置，直至整個(gè)序列都滿足堆定義。選擇排序選擇排序 堆排序堆排序304548267218261553篩選算法篩選算法void HeapAdjustn ( SqList &H, int s, int m ) / /已知已知H.Rs+1.mH.Rs+1.m滿足大頂堆定義滿足大頂堆定義 /調(diào)整調(diào)整H.Rs, H.Rs.mH.Rs, H.Rs.m使得成為大頂堆使得成為大頂堆 rc=H.Rs; for(j=2*s; j=m; j*=2) if(jm & H.Rj.keyH.Rj.key) break;

9、H.Rs=H.Rj; s=j; H.Rs=rc;三、建堆8 將一個(gè)任意序列建成一個(gè)小根堆或大根堆；將一個(gè)任意序列建成一個(gè)小根堆或大根堆；8 自下而上、自右向左地進(jìn)行篩選，將以每一個(gè)非終自下而上、自右向左地進(jìn)行篩選，將以每一個(gè)非終端結(jié)點(diǎn)為根的子樹篩選成堆；端結(jié)點(diǎn)為根的子樹篩選成堆；8 具有具有n n個(gè)結(jié)點(diǎn)的完全二叉樹有個(gè)結(jié)點(diǎn)的完全二叉樹有 n/2n/2 個(gè)葉子結(jié)點(diǎn)，一個(gè)葉子結(jié)點(diǎn)，一個(gè)葉子就是一個(gè)堆。個(gè)葉子就是一個(gè)堆。8 完全二叉樹最后一個(gè)非終端結(jié)點(diǎn)的編號(hào)為完全二叉樹最后一個(gè)非終端結(jié)點(diǎn)的編號(hào)為 n/2n/2 ；選擇排序選擇排序 堆排序堆排序53481836 303693 1545765432108

10、9107236185336459315723048舉例：將10個(gè)元素的序列建成一個(gè)大頂堆：葉子非終端結(jié)點(diǎn)逐個(gè)進(jìn)行篩選選擇排序選擇排序 堆排序堆排序36485336451593723018364853724515933630183648937245155336301836489372451553363018934853724515363630187248534593153636301836489372451553363018四、堆排序以大頂堆為例：以大頂堆為例：8堆頂是排序區(qū)間最大的元素堆頂是排序區(qū)間最大的元素8去掉堆頂，將堆頂與堆的最后一個(gè)元素交換位置：去掉堆頂，將堆頂與堆的最后一個(gè)元素交換位

11、置： 最大元素歸位；最大元素歸位； 新樹根不滿足堆定義，需要通過(guò)篩選調(diào)整為堆新樹根不滿足堆定義，需要通過(guò)篩選調(diào)整為堆選擇排序選擇排序 堆排序堆排序72485345931536363018堆排序選擇排序選擇排序 堆排序堆排序53483645721536301893堆排序選擇排序選擇排序 堆排序堆排序45483636531530189372堆排序選擇排序選擇排序 堆排序堆排序45303636481518937253堆排序選擇排序選擇排序 堆排序堆排序第十章 排序(Sort)目錄10.1 排序概述10.2 插入排序10.3 交換排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序排序排序歸并排

12、序(Merging sort)算法思想:8一種基于將兩個(gè)有序表異地歸并成一個(gè)有序表的排序策略。8初態(tài)是將排序表中的每個(gè)元素看成是一個(gè)有序的子表，共有n個(gè)子表。 25 57 48 37 12 92 86 72 31 48 25 92 48 37 12 57 86 72 31 488經(jīng)過(guò)一趟排序，將兩個(gè)相鄰的有序子表歸異地并成一個(gè)有序子表；8共進(jìn)行l(wèi)og2n趟這樣的歸并，整個(gè)排序表就被歸并成了一個(gè)有序表。 25 92 48 37 57 92 86 72 31 48 R: 25924837125786723148 T: 25 92 37 48 12 57 72 86 31 48 R: 25 37 4

13、8 92 12 57 72 86 31 48 T: 12 25 37 48 57 72 86 92 31 48 R: 12 25 31 37 48 48 57 72 86 92 歸并排序歸并排序歸并排序算法：(1) 兩個(gè)相鄰子表的歸并：兩個(gè)相鄰子表的歸并： void Merge(RecType SR, RecType &TR, int i, int m, int n);(2) 對(duì)區(qū)間對(duì)區(qū)間s.t的歸并排序的歸并排序 void Merge(RecType SR, RecType &TR1, int s, int t);(3) 對(duì)整個(gè)表的歸并排序?qū)φ麄€(gè)表的歸并排序 void Mer

14、geSort(SqList &L) 歸并排序歸并排序兩個(gè)相鄰子表的歸并兩個(gè)相鄰子表的歸并:void Merge(RecType SR, RecType &TR, int i, int m, int n)/將有序的將有序的SRi.mSRi.m和和SRm+1.nSRm+1.n歸并為有序的歸并為有序的TRi.nTRi.nfor(j=m+1,k=i; im&j=n; +k)if(SRi.key=SRj.key) TRk=SRi+;else TRk=SRj+;if(i=m) TRk.n=SRi.m;if(j=n) TRk.n=SRj.m; /end Merge/end Merge

15、歸并排序歸并排序?qū)^(qū)間對(duì)區(qū)間s.t的歸并排序的歸并排序:void MSort(RecType SR, RecType &TR1, int s, int t)/將將SRs.tSRs.t歸并排序?yàn)闅w并排序?yàn)門R1s.tTR1s.tRecType TR2n; /定義輔助數(shù)組定義輔助數(shù)組TR2TR2 if(S=t) TR1s = SRs;else m=(s+t)/2; /將將SRs.tSRs.t平分為平分為SRs.mSRs.m和和SRm+1.tSRm+1.t MSort(SR, TR2, s, m); /SRs.m/SRs.m排序成排序成TR2s.mTR2s.m MSort(SR, TR2,

16、m+1, t);/SRm+1.t/SRm+1.t排序成排序成TR2m+1.tTR2m+1.t Merge(TR2, TR1, s, m, t); /兩個(gè)有序的相鄰區(qū)間歸并兩個(gè)有序的相鄰區(qū)間歸并 /end MSort/end MSort歸并排序歸并排序整個(gè)表的歸并排序整個(gè)表的歸并排序void MergeSort(SqList &L) /對(duì)順序表對(duì)順序表L L作歸并排序作歸并排序MSort(L.r, L.r, 1, L.length); /end MergeSort/end MergeSort歸并排序歸并排序歸并排序的非遞歸算法分三步進(jìn)行:兩個(gè)相鄰子表的歸并void Merge(RcdTy

17、pe SR , RcdType TR , int i, int m, int n) /將有序的SRi.m和SRm+1.n異地歸并為有序的TRi.n for (j=m+1, k=i; i=m&j=n; k+) if ( SR i .key=SR j .key ) TR k =SR i+ ; else TR k =SR j+ ; if ( i=m ) TR k . . n =SR i . . m ; if ( j=m ) TR k . . n =SR j . . n ;歸并排序歸并排序?qū)ε判虮硭凶颖磉M(jìn)行一趟歸并排序 設(shè)子表長(zhǎng)度為L(zhǎng)， 兩個(gè)特殊情況必須在算法中加以考慮： (1) 子表的個(gè)數(shù)

18、是奇數(shù)，此時(shí)最后一個(gè)子表不必歸并，直接抄； (2) 最后一個(gè)子表的長(zhǎng)度可能小于L歸并排序歸并排序2. 對(duì)排序表所有子表進(jìn)行一趟歸并排序void MergePass(RcdType SR , RcdType TR , int L, int n) /對(duì)對(duì)SR1.nSR1.n進(jìn)行趟歸并排序，結(jié)果放入進(jìn)行趟歸并排序，結(jié)果放入TRTR中，中，L L是子表的長(zhǎng)度是子表的長(zhǎng)度 for (i=1; i+2*L-1=n; i+=2*L) Merge(SR,TR,i,i+L-1,i+2*L-1); / /相鄰子表相鄰子表SRi.i+L-1SRi.i+L-1和和SRi+L.i+2SRi+L.i+2* *L-1L-1

19、進(jìn)行歸并進(jìn)行歸并 if(i+L-1)n) /還剩兩個(gè)子表還剩兩個(gè)子表, , 但最后一個(gè)子表長(zhǎng)度不足但最后一個(gè)子表長(zhǎng)度不足L L Merge(SR,TR,i,i+L-1,n)； else / /還剩一個(gè)子表，直接抄入還剩一個(gè)子表，直接抄入TRTR TRi.n=SRi.n；歸并排序歸并排序3. 對(duì)排序表進(jìn)行歸并排序void MergeSort ( SqList &L ) / /對(duì)排序表對(duì)排序表L L進(jìn)行歸并排序進(jìn)行歸并排序 RcdType *TR; TR=new (sizeof(RcdType)*L.length); /輔助數(shù)組輔助數(shù)組 for(int L=1; Ln; L*=2) Mer

20、gePass(L.R,TR,L,L.length); / /一趟歸并，結(jié)果存入一趟歸并，結(jié)果存入TRTR中中 L*=2; /將子表長(zhǎng)度擴(kuò)大一倍將子表長(zhǎng)度擴(kuò)大一倍 MergePass(TR,L.R,L,L.length)； /一趟歸并，結(jié)果存入一趟歸并，結(jié)果存入L.rL.r中中 /end for /end for free(TR);歸并排序歸并排序第十章 排序(Sort)目錄10.1 排序概述10.2 插入排序10.3 交換排序10.4 選擇排序10.5 歸并排序10.6 基數(shù)排序排序排序c一種利用一種利用收集收集和和分配分配操作進(jìn)行排序的方法操作進(jìn)行排序的方法c適合于多級(jí)關(guān)鍵字記錄的排序適合于

21、多級(jí)關(guān)鍵字記錄的排序基數(shù)排序基數(shù)排序舉例：撲克牌排序方法一：先排數(shù)字，再排花色最低位優(yōu)先方法一：先排數(shù)字，再排花色最低位優(yōu)先基數(shù)排序基數(shù)排序3241511112222333344455554444233332221111555541324511112222333344455554115212432335452443155554544432333212121155545444323332121211撲克牌排序方法二：先排花色，再排數(shù)字最高位優(yōu)先方法二：先排花色，再排數(shù)字最高位優(yōu)先基數(shù)排序基數(shù)排序121542533252114353444444233332221111555532121542535

22、21143534455545444323332121211c一般，設(shè)一般，設(shè)n個(gè)記錄的序列：個(gè)記錄的序列： R1, R2, ., Rn c每個(gè)記錄每個(gè)記錄Ri中有中有d個(gè)關(guān)鍵字：個(gè)關(guān)鍵字：( Ki0, Ki1, ., Kid-1 )其中，其中，Ki0是最主位關(guān)鍵字；是最主位關(guān)鍵字； Kid-1是最次關(guān)鍵字。是最次關(guān)鍵字。c有序序列：有序序列： 按最主位關(guān)鍵字有序排列；按最主位關(guān)鍵字有序排列； 如果最主位關(guān)鍵字的值相同，則按次一位關(guān)鍵字的如果最主位關(guān)鍵字的值相同，則按次一位關(guān)鍵字的大小有序排列；大小有序排列； 依次類推。依次類推?；鶖?shù)排序基數(shù)排序c多關(guān)鍵字排序的兩種策略：多關(guān)鍵字排序的兩種策略：

23、MSD法、法、LSD法法cMSD法最高位優(yōu)先法最高位優(yōu)先(Most Significant Digit First) 先按最主位關(guān)鍵字先按最主位關(guān)鍵字K0的大小進(jìn)行排序，將記錄序列分的大小進(jìn)行排序，將記錄序列分成若干自序列，每個(gè)子序列有相同的成若干自序列，每個(gè)子序列有相同的K0值；值； 分別對(duì)每個(gè)子序列按關(guān)鍵字分別對(duì)每個(gè)子序列按關(guān)鍵字K1的大小進(jìn)行排序，將每的大小進(jìn)行排序，將每個(gè)序列分成若干更小的子序列；個(gè)序列分成若干更小的子序列； 依次重復(fù)，直到對(duì)依次重復(fù)，直到對(duì)Kd-2進(jìn)行排序后，得到的每個(gè)子序進(jìn)行排序后，得到的每個(gè)子序列都有相同的關(guān)鍵字列都有相同的關(guān)鍵字(K0,K1,.,Kd-2) 最后

24、，分別對(duì)每個(gè)子序列按最后，分別對(duì)每個(gè)子序列按Kd-1進(jìn)行排序，然后將每進(jìn)行排序，然后將每個(gè)有序的子序列個(gè)有序的子序列依次連接依次連接在一起，成為一個(gè)有序序列。在一起，成為一個(gè)有序序列?；鶖?shù)排序基數(shù)排序cLSD法最低位優(yōu)先法最低位優(yōu)先(Last Significant Digit First) 從最次位關(guān)鍵字從最次位關(guān)鍵字Kd-1起進(jìn)行排序起進(jìn)行排序 然后在對(duì)高一位關(guān)鍵字然后在對(duì)高一位關(guān)鍵字Kd-2進(jìn)行排序進(jìn)行排序 依次重復(fù)，直到對(duì)依次重復(fù)，直到對(duì)K0進(jìn)行排序后，得到一個(gè)有序序列進(jìn)行排序后，得到一個(gè)有序序列基數(shù)排序基數(shù)排序c如果關(guān)鍵字是多位十進(jìn)制數(shù)，我們可以將每位數(shù)如果關(guān)鍵字是多位十進(jìn)制數(shù)，我們

25、可以將每位數(shù)看成為一個(gè)關(guān)鍵字：看成為一個(gè)關(guān)鍵字：比如：比如： 關(guān)鍵字關(guān)鍵字Key是是0999的三位數(shù)，可認(rèn)為的三位數(shù)，可認(rèn)為Key由三個(gè)關(guān)由三個(gè)關(guān)鍵字鍵字(K0,K1,K2)組成，每個(gè)組成，每個(gè)Ki的基數(shù)是的基數(shù)是10（可?。扇?9中中的任一個(gè)值）的任一個(gè)值）c如果關(guān)鍵字是由若干個(gè)字母組成的單詞，我們可如果關(guān)鍵字是由若干個(gè)字母組成的單詞，我們可以將每位字母看成是一個(gè)關(guān)鍵字：以將每位字母看成是一個(gè)關(guān)鍵字：比如：比如： 關(guān)鍵字關(guān)鍵字Key是由是由5個(gè)小寫字母組成的單詞，則個(gè)小寫字母組成的單詞，則Key由由5個(gè)關(guān)鍵字個(gè)關(guān)鍵字(K0,K1,K2,K3,K4)組成，每個(gè)組成，每個(gè)Ki的基數(shù)是的基數(shù)是2

26、6（可?。扇z中的任一個(gè)字符）中的任一個(gè)字符）基數(shù)排序基數(shù)排序下面介紹用下面介紹用LSD法進(jìn)行分配和收集法進(jìn)行分配和收集存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：常數(shù)常數(shù)RADIX：關(guān)鍵字的基數(shù)關(guān)鍵字的基數(shù)數(shù)組數(shù)組A0.n-1: 存放存放n個(gè)待排序的記錄個(gè)待排序的記錄數(shù)組數(shù)組B0.n-1: 與與A配合使用的輔助數(shù)組配合使用的輔助數(shù)組數(shù)組數(shù)組count0.RADIX-1：輔助數(shù)組，存放每輔助數(shù)組，存放每種關(guān)鍵字值在被分配時(shí)的位置種關(guān)鍵字值在被分配時(shí)的位置基數(shù)排序基數(shù)排序count數(shù)組的計(jì)算：數(shù)組的計(jì)算：1. 賦初值：賦初值：counti=0;2. 統(tǒng)計(jì)排序記錄序列中每種關(guān)鍵字的個(gè)數(shù)：統(tǒng)計(jì)排序記錄序列中每種關(guān)鍵字的個(gè)數(shù)：counti=關(guān)鍵字值等于關(guān)鍵字值等于di的記錄個(gè)數(shù)的記錄個(gè)數(shù)3. 計(jì)算排序中計(jì)算排序中di第一次出現(xiàn)時(shí)的第一次出現(xiàn)時(shí)的“分配分配”位置位置(這里約定排序這里約定排序次序從右向左進(jìn)行）次序從右向左進(jìn)行）counti=counti+counti-1i=1,2,.n-1基數(shù)排序基數(shù)排序類型定義：類型定義：#define MAX_NUM_OF_KEY 6 /關(guān)鍵字位數(shù)最大