嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)(C語言版)PPT-第十章 課件原版

1、1數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.1 概述概述10.2 插入類排序插入類排序10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序10.3 交換類排序交換類排序10.5 歸并排序歸并排序10.6 基數(shù)排序基數(shù)排序10.7 各種排序方法的總和比較各種排序方法的總和比較2數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.1 概述概述第第10章章 內(nèi)部排序內(nèi)部排序排序排序是計算機(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,

2、58, 61, 23, 97, 7552, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為調(diào)整為14, 23, 36, 49, 52, 58, 61, 75, 80, 9714, 23, 36, 49, 52, 58, 61, 75, 80, 973數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.1 概述概述第第10章章 內(nèi)部排序內(nèi)部排序排序的排序的定義定義：假設(shè)含假設(shè)含n個記錄個記錄的序列為的序列為 a0, a1, ， an-1 其相應(yīng)的其相應(yīng)的關(guān)鍵字關(guān)鍵字序列為序列為 K0, K1, ，Kn-1 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著

3、這樣一個關(guān)系它們之間存在著這樣一個關(guān)系 ： Kp0Kp1Kpn-1按此固有關(guān)系將上式記錄序列重新排列為按此固有關(guān)系將上式記錄序列重新排列為 ap0, ap1, ，apn-1 的操作稱作的操作稱作排序排序。4數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.1 概述概述第第10章章 內(nèi)部排序內(nèi)部排序排序排序內(nèi)部排序內(nèi)部排序外部排序外部排序整個排序過程整個排序過程不需要訪問外存不需要訪問外存便能完成。便能完成。若參加排序的記錄數(shù)量很大，整個序列的排若參加排序的記錄數(shù)量很大，整個序列的排序過程序過程不可能在內(nèi)存中不可能在內(nèi)存中完成。完成。穩(wěn)定排序穩(wěn)定排序不穩(wěn)定排序不穩(wěn)定排序排序排序相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中未發(fā)生變

4、化。相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中未發(fā)生變化。相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中發(fā)生變化。相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中發(fā)生變化。5數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.1 概述概述第第10章章 內(nèi)部排序內(nèi)部排序內(nèi)部排序的過程：內(nèi)部排序的過程：是一個逐步擴(kuò)大記錄的有序序列長度的過程是一個逐步擴(kuò)大記錄的有序序列長度的過程。經(jīng)過一趟排序經(jīng)過一趟排序有序序列區(qū)有序序列區(qū)無無 序序 序序 列列 區(qū)區(qū)有序序列區(qū)有序序列區(qū)無無 序序 序序 列列 區(qū)區(qū)內(nèi)部排序的方法內(nèi)部排序的方法6數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.1 概述概述第第10章章 內(nèi)部排序內(nèi)部排序基于不同的基于不同的“擴(kuò)大擴(kuò)大” 有序序列長度的方法，有序序列長度

5、的方法，內(nèi)部排序方法大致可分下列幾種類型：內(nèi)部排序方法大致可分下列幾種類型：插入類插入類交換類交換類選擇類選擇類 歸并類歸并類其它方法其它方法7數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.1 概述概述第第10章章 內(nèi)部排序內(nèi)部排序待排記錄的數(shù)據(jù)類型定義如下待排記錄的數(shù)據(jù)類型定義如下:#define MAXSIZE 1000typedef int KeyType; typedef struct KeyType key; OtherType other_data; RecordType; typedef struct RcdType rMAXSIZE+1; int length; SqList; 8數(shù)數(shù) 據(jù)據(jù) 結(jié)

6、結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序?qū)o序無序子序列中的一個或幾個記錄子序列中的一個或幾個記錄“插入插入”到到有有序序序列中，從而序列中，從而增加增加記錄的記錄的有序有序子序列的子序列的長度長度。有序序列有序序列a1.i-1a1.i-1ai 無序序列無序序列 ai.n-1ai.n-1一趟直接插入排序的基本思想：一趟直接插入排序的基本思想：有序序列有序序列a1.ia1.i無序序列無序序列 ai+1.n-1ai+1.n-19數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序?qū)崿F(xiàn)實現(xiàn)“一趟插入排序一趟插入排序”可分三步進(jìn)行：可分三步進(jìn)

7、行：3將將ai 插入插入(復(fù)制復(fù)制)到到aj+1的位置上。的位置上。2將將aj+1.i中的所有記錄均后移一個位置；中的所有記錄均后移一個位置；1在在a1.i-1中查找中查找ai的插入位置，的插入位置， a1.j.key ai.key aj+1.i.key；10數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序直接插入排序直接插入排序（基于順序查找）（基于順序查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量）不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述不同的具體實現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）表插入排序（基于鏈

8、表存儲）表插入排序（基于鏈表存儲）11數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序直接插入排序直接插入排序利用利用順序順序查找實現(xiàn)在查找實現(xiàn)在r1.i-1中中查找查找ri的插入位置的插入位置4862 357755 143598第第1 趟趟4862r06235235486237777455556277514 1435 4855627763535485562 7779898從從ri-1起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在r0；r0 = ri; 循環(huán)結(jié)束表明循環(huán)結(jié)束表明ri的插入位置為的插入位置為 j +1r0jrifor (j=i-

9、1; r0.keyrj.key; -j); j=i-1插入位置插入位置12數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序?qū)τ谠诓檎疫^程中找到的那些關(guān)鍵字不小于對于在查找過程中找到的那些關(guān)鍵字不小于ri.key的記錄，并在查找的同時實現(xiàn)記錄向后移動；的記錄，并在查找的同時實現(xiàn)記錄向后移動；for (j=i-1; r0.keyrj.key; -j); rj+1 = rj；上述循環(huán)結(jié)束后可以上述循環(huán)結(jié)束后可以直接直接進(jìn)行進(jìn)行“插入插入” rj+1 = r0；r0jrij=i-1插入位置插入位置直接插入排序直接插入排序13令令 i = 2，3，, n, 實現(xiàn)整個序列

10、的排序。實現(xiàn)整個序列的排序。for ( i=2; i=n; +i ) if (ri.keyri-1.key) 在在 r1.i-1中查找中查找ri的插入位置的插入位置; 插入插入ri ; 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序直接插入排序直接插入排序14數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序直接插入排序直接插入排序void InsertionSort ( SqList &L ) for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) L.r0 = L.ri;

11、for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; L.rj+1 = L.r0; 15內(nèi)部排序的時間分析：內(nèi)部排序的時間分析：實現(xiàn)內(nèi)部排序的基本操作有兩個：實現(xiàn)內(nèi)部排序的基本操作有兩個：（2）“移動移動”記錄。記錄。（1）“比較比較”序列中兩個關(guān)鍵字的大小；序列中兩個關(guān)鍵字的大小；數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序直接插入排序直接插入排序16對對于于直直接接插插入入排排序序最好的情況最好的情況（關(guān)鍵字在記錄序列中（關(guān)鍵字在記錄序列中順順序有序）：序有序）：“比較比較”的次數(shù)：的次數(shù)：最壞的情況

12、最壞的情況（關(guān)鍵字在記錄序列中（關(guān)鍵字在記錄序列中逆序逆序有序）：有序）：“比較比較”的次數(shù)：的次數(shù)：112nni0 02) 1)(4() 1(2nnini“移動移動”的次數(shù)：的次數(shù)：“移動移動”的次數(shù)：的次數(shù)：2) 1)(4() 1(2nnini數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序直接插入排序直接插入排序17數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序折半插入排序折半插入排序因為因為 r1.i-1 是一個按關(guān)鍵字有序的是一個按關(guān)鍵字有序的有序有序序列，則序列，則可以利用可以利用折半查找折半查找實現(xiàn)實現(xiàn)“在在r

13、1.i-1中查找中查找ri的插的插入位置入位置”，如此實現(xiàn)的插入排序為，如此實現(xiàn)的插入排序為折半插入排序折半插入排序。14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如例如: :插入插入位置位置L.r18數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序折半插入排序折半插入排序void BiInsertionSort ( SqList &L ) 在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=low; -j ) L.rj+1 = L.rj; L.rlow = L.r0

14、; 19數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序折半插入排序折半插入排序low = 1; high = i-1;while (low=high) m= (low+high)/2; if (L.r0.key L.rm.key) high = m-1; else low = m+1; 在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；20數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序希爾排序希爾排序基本思想：基本思想：對待排記錄序列先作對待排記錄序列先作“宏觀宏觀”調(diào)整，再作調(diào)整，再作“微觀微觀”調(diào)調(diào)整。整。

15、所謂所謂“宏觀宏觀”調(diào)整，指的是，調(diào)整，指的是，“跳躍式跳躍式”的插入排的插入排序。序。（又稱縮小增量排序）（又稱縮小增量排序）21將記錄序列分成若干子序列，分將記錄序列分成若干子序列，分別對每個子序列進(jìn)行插入排序。別對每個子序列進(jìn)行插入排序。其中，其中，d d 稱為增量，它的值在排序過程中從稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為大到小逐漸縮小，直至最后一趟排序減為1 1。例如：將例如：將 n n 個記錄分成個記錄分成 d d 個子序列：個子序列： R1 R1，R1+dR1+d，R1+2dR1+2d，R1+kd R1+kd R2 R2，R2+dR2+d，R2+2dR

16、2+2d，R2+kd R2+kd Rd Rd，R2dR2d，R3dR3d，RkdRkd，R(k+1)d R(k+1)d 數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序希爾排序希爾排序 （又稱縮小增量排序）（又稱縮小增量排序）具體做法為：具體做法為：22數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序希爾排序希爾排序 （又稱縮小增量排序）（又稱縮小增量排序）4655134294170570d1=4465513429417057017550513d2=2461705429455137005134694d3=10517134246

17、5594701317709423數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序希爾排序希爾排序 （又稱縮小增量排序）（又稱縮小增量排序）void ShellInsert ( SqList &L, int dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; L.rj+dk = L.r0; 24數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.2 插入類排序插入類排序第第10章章 內(nèi)部排序內(nèi)部排序希爾排序希爾排序 （又稱縮小增量排序）（又稱縮小增量排序）void

18、ShellSort (SqList &L, int dlta, int t) for (k=0; kt; +t) ShellInsert(L, dltak); 25數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交換類排序第第10章章 內(nèi)部排序內(nèi)部排序基本思想：基本思想：通過通過交換逆序元素交換逆序元素進(jìn)行排序的方法。進(jìn)行排序的方法。冒泡排序冒泡排序（相鄰比逆法）（相鄰比逆法）快速排序快速排序通過通過“交換交換”無無序序列中的記錄從而得到其中關(guān)鍵字序序列中的記錄從而得到其中關(guān)鍵字最小最小或或最大最大的記錄，并將它的記錄，并將它加入到有序子序列加入到有序子序列中，中，以此方法以此方法增加記錄的有序子序

19、列的長度增加記錄的有序子序列的長度。26數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交換類排序第第10章章 內(nèi)部排序內(nèi)部排序冒泡排序冒泡排序（相鄰比逆法）（相鄰比逆法）思想：在掃描的過程中思想：在掃描的過程中順次比較相鄰順次比較相鄰的兩個的兩個 元素的大小，若元素的大小，若逆序逆序就交換位置。就交換位置。48623577551435982240第第1趟趟35625577147735 77229840989次次483562551435772240第第2趟趟7735485514356222408次次第第n-1趟趟 排序結(jié)束排序結(jié)束n-i次次第第i 趟趟27數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交

20、換類排序第第10章章 內(nèi)部排序內(nèi)部排序冒泡排序冒泡排序（相鄰比逆法）（相鄰比逆法）void BubbleSort(RecordType r ,int length) n=length; for(i=1; i=n-1; i+) for(j=1;jrj+1.key) x=aj;rj=rj+1;rj+1=x; 28數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交換類排序第第10章章 內(nèi)部排序內(nèi)部排序冒泡排序冒泡排序 時間分析時間分析: :情況情況序列序列起泡次數(shù)起泡次數(shù) 比較次數(shù)比較次數(shù)最最好好有有序序1n-1最最壞壞逆逆序序n-1n(n-1)/229數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交換類排序

21、第第10章章 內(nèi)部排序內(nèi)部排序快速排序快速排序改進(jìn)冒泡排序中一次交換只能消除一個逆序改進(jìn)冒泡排序中一次交換只能消除一個逆序的缺點，即實現(xiàn)的缺點，即實現(xiàn)一次交換消除多個逆序一次交換消除多個逆序。思想：思想：找一個記錄，以它的關(guān)鍵字作為找一個記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字，凡其關(guān)鍵字小于樞軸小于樞軸的記錄均的記錄均移動至該記錄之前移動至該記錄之前，凡其關(guān)鍵字，凡其關(guān)鍵字大于樞軸大于樞軸的記錄均的記錄均移動至該記錄之后移動至該記錄之后。即對無序的記錄序列進(jìn)行即對無序的記錄序列進(jìn)行“一次劃分一次劃分”，之后分別對分割所得之后分別對分割所得兩個子序列兩個子序列“遞歸遞歸”進(jìn)行進(jìn)行快速排序

22、快速排序。30數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交換類排序第第10章章 內(nèi)部排序內(nèi)部排序快速排序快速排序一次劃分（一趟快速排序）一次劃分（一趟快速排序）4862357755143598r048lowhighhigh35low62high14low low77highhigh4831數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交換類排序第第10章章 內(nèi)部排序內(nèi)部排序快速排序快速排序int QKpass (RecordType r , int low, int high) r0 = rlow; while (lowhigh) while(low= r0.key) - high; rlow =

23、 rhigh;while (lowhigh & rlow.key= r0.key) + low; rhigh = rlow;rlow = r0; return low;一趟快速排序算法一趟快速排序算法32void QKSort(RecordType r ,int low,int high) r0=rlow; if(lowhigh) pos=QKpass(r,low,high); QKSort(r,low,pos-1); QkSort(r,pos+1,high);數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.3 交換類排序交換類排序第第10章章 內(nèi)部排序內(nèi)部排序快速排序快速排序算法算法33數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)1

24、0.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序從記錄的從記錄的無無序子序列中序子序列中“選擇選擇”關(guān)鍵字關(guān)鍵字最小最小或或最大最大的記錄，并將它的記錄，并將它加入到有序子序列加入到有序子序列中，中，以此方法以此方法增加記錄的有序子序列的長度增加記錄的有序子序列的長度。簡單選擇排序簡單選擇排序堆排序堆排序樹型選擇樹型選擇排序排序34數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序簡單選擇排序簡單選擇排序4862357755143598i第第 1 趟趟kjjkjjj kjj14482i kj3562335624487755566277777898voi

25、d SelectSort(RecordType r ,int n) n=length; for(i=1;i=n-1;i+) k=i; for(j=i+1;j=n; +j) if(rj.keyrk.key) k=j; if(k!=i) x=ri;ri=rk;rk=x; 35數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序樹型選擇排序樹型選擇排序是一種按是一種按錦標(biāo)賽錦標(biāo)賽的思想進(jìn)行排序的方法。的思想進(jìn)行排序的方法。493827659776491338651327381313761327272749493838494949496549497665659797767

26、6979736數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序?qū)湫团判虻倪M(jìn)一步改進(jìn)。對樹型排序的進(jìn)一步改進(jìn)。堆是滿足下列性質(zhì)的數(shù)列堆是滿足下列性質(zhì)的數(shù)列r1, r2, ，rn：或或堆的定義堆的定義:12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例如例如: :是小頂堆是小頂堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆(小頂堆小頂堆)(大頂堆大頂堆)122iiiirrrr122iiiirrrr37rir2i r2i+1 若將該數(shù)列視作完全二叉樹，則若將該數(shù)列視

27、作完全二叉樹，則 r2i 是是 ri 的左孩子；的左孩子；r2i+1 是是 ri 的右孩子。的右孩子。例如例如: :數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 4912362765403498817355491414是小頂堆是小頂堆不不38堆排序即是利用堆排序即是利用堆的特性堆的特性對記錄序列進(jìn)行排序。對記錄序列進(jìn)行排序。例如：例如：建大頂堆建大頂堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36,

28、 27, 40, 55, 64, 98 交換交換 98 98 和和 1212重新調(diào)整為大頂堆重新調(diào)整為大頂堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 經(jīng)過篩選經(jīng)過篩選數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序391、如何由一個無序序列、如何由一個無序序列“建初堆建初堆”？堆排序的兩個問題堆排序的兩個問題: 2、輸出堆頂后，如何、輸出堆頂后，如何“篩選篩選”？數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排

29、序內(nèi)部排序堆排序堆排序所謂所謂“篩選篩選”指的是，對一棵指的是，對一棵左左/右子樹均為堆的完右子樹均為堆的完全全二叉樹二叉樹，“調(diào)整調(diào)整”根結(jié)點使整個二叉樹也成為一個堆根結(jié)點使整個二叉樹也成為一個堆。40數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序4898357755143562489877624841數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序例如：例如： 48, 62, 35, 77, 55, 14, 35, 984862357755143598顯然不是一個堆顯然不是一個堆調(diào)整調(diào)整如何建初堆

30、？如何建初堆？424862357755143598數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序987798776298776248439877356255143548數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序984898776248773577625535626214554814555535483548481435143535353535141444時間復(fù)雜度分析時間復(fù)雜度分析1. 1. 對深度為對深度為k k的堆，的堆，“篩選篩選”所需進(jìn)行的關(guān)鍵所需進(jìn)行的關(guān)鍵字字 比較的次數(shù)至多為比較的次數(shù)

31、至多為2(k-1)2(k-1)；3. 3. 調(diào)整調(diào)整“堆頂堆頂”n-1n-1次，總共進(jìn)行的關(guān)鍵字比較的次次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)數(shù) 不超過不超過 2(2( loglog2 2(n-1)(n-1) + + loglog2 2(n-2)(n-2) + + +loglog2 22 2)2)2n n( ( loglog2 2n n ) ) 因此，堆排序的時間復(fù)雜度為因此，堆排序的時間復(fù)雜度為O(O(n nloglogn n) )。2. 2. 對對n n個關(guān)鍵字，建成深度為個關(guān)鍵字，建成深度為h h(=(= loglog2 2n n +1)+1)的堆，的堆， 所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多所需進(jìn)行

32、的關(guān)鍵字比較的次數(shù)至多4 4n n；數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.4 選擇類排序選擇類排序第第10章章 內(nèi)部排序內(nèi)部排序堆排序堆排序45數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.5 歸并類排序歸并類排序第第10章章 內(nèi)部排序內(nèi)部排序通過通過“歸并歸并”兩個或兩個以上兩個或兩個以上的記錄的記錄有有序序子序列，逐步增加記錄有序序列的長度。子序列，逐步增加記錄有序序列的長度。在在內(nèi)內(nèi)部排序中，通常采用的是部排序中，通常采用的是2-路路歸并排序。歸并排序。即：即：將兩個位置相鄰的記錄有序子序列將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。歸并為一個記錄的有序序列。有有 序序 序序 列列 rrl l.n n

33、有序子序列有序子序列 rrl l.m m 有序子序列有序子序列 rrm+1m+1.n n 46數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.5 歸并類排序歸并類排序第第10章章 內(nèi)部排序內(nèi)部排序例如：例如：19，13，05，27，01，26，31，1613，1905，2701，2616 ，3105，13，19，2701，16，26，3101，05，13，16，19，26，27，31很少進(jìn)行內(nèi)排序，主要用于外排序。很少進(jìn)行內(nèi)排序，主要用于外排序。47數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.6 基數(shù)排序基數(shù)排序第第10章章 內(nèi)部排序內(nèi)部排序主要利用主要利用分配分配和和收集收集兩種基本操作。兩種基本操作。典型的就是典型的就是基數(shù)

34、類排序基數(shù)類排序。多關(guān)鍵字的排序多關(guān)鍵字的排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序48數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.6 基數(shù)排序基數(shù)排序第第10章章 內(nèi)部排序內(nèi)部排序多關(guān)鍵字的排序多關(guān)鍵字的排序最低位優(yōu)先最低位優(yōu)先LSD法法最高位優(yōu)先最高位優(yōu)先MSD法先對先對K0進(jìn)行排序，并按進(jìn)行排序，并按 K0 的不同值將記錄序列分的不同值將記錄序列分成若干子序列之后，分別對成若干子序列之后，分別對 K1 進(jìn)行排序，進(jìn)行排序，.， 依次類推，直至最后對最次位關(guān)鍵字排序完成為止。依次類推，直至最后對最次位關(guān)鍵字排序完成為止。先對先對 Kd-1 進(jìn)行排序進(jìn)行排序，然后對然后對 Kd-2 進(jìn)行排序，依進(jìn)行排序，依次類推，次類推

35、，直至對最主位關(guān)鍵字直至對最主位關(guān)鍵字 K0 排序完成為止排序完成為止。排序過程中不需要根據(jù)排序過程中不需要根據(jù) “前一個前一個” 關(guān)鍵字的排序結(jié)果，關(guān)鍵字的排序結(jié)果，將記錄序列分割成若干個將記錄序列分割成若干個(“前一個前一個”關(guān)鍵字不同的關(guān)鍵字不同的)子子序列。序列。49例如例如: :學(xué)生記錄含三個關(guān)鍵字學(xué)生記錄含三個關(guān)鍵字: :系別、班號和系別、班號和班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。班內(nèi)的序列號，其中以系別為最主位關(guān)鍵字。 無序序列無序序列對對K2排序排序?qū)1排序排序?qū)0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,2

36、02,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序過程如下的排序過程如下: :數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.6 基數(shù)排序基數(shù)排序第第10章章 內(nèi)部排序內(nèi)部排序多關(guān)鍵字的排序多關(guān)鍵字的排序50數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.6 基數(shù)排序基數(shù)排序第第10章章 內(nèi)部排序內(nèi)部排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按圍相同，則按LSD法進(jìn)行排序時，可以采用法進(jìn)行排序時，可以采用“分配分配-收收集集”的方法，其的方法

37、，其好處是不需要進(jìn)行關(guān)鍵字間的比較好處是不需要進(jìn)行關(guān)鍵字間的比較。對于對于數(shù)字型或字符型的單關(guān)鍵字?jǐn)?shù)字型或字符型的單關(guān)鍵字，可以看成是，可以看成是由多個由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字?jǐn)?shù)位或多個字符構(gòu)成的多關(guān)鍵字，此時可以采用這種，此時可以采用這種“分配分配-收集收集”的辦法進(jìn)行排序，稱作的辦法進(jìn)行排序，稱作基數(shù)排序法基數(shù)排序法。51例如：對下列這組關(guān)鍵字例如：對下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其首先按其 “個位數(shù)個位數(shù)” 取值分別為取值分別為 0, 1, , 9 “分配分配” 成成 10 組，之后按從組，之后按從

38、 0 至至 9 的順序?qū)⒌捻樞驅(qū)?它們它們 “收集收集” 在一起；在一起；然后按其然后按其 “十位數(shù)十位數(shù)” 取值分別為取值分別為 0, 1, , 9 “分配分配” 成成 10 組組，之后再按從，之后再按從 0 至至 9 的順序?qū)⑺鼈兊捻樞驅(qū)⑺鼈儭笆占占痹谝黄?；在一起；最后按其最后按其“百位?shù)百位數(shù)”重復(fù)一遍上述操作。重復(fù)一遍上述操作。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.6 基數(shù)排序基數(shù)排序第第10章章 內(nèi)部排序內(nèi)部排序鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序52在計算機(jī)上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空在計算機(jī)上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應(yīng)采用間，應(yīng)采用鏈表鏈表作存儲結(jié)構(gòu)，即作存儲結(jié)構(gòu)，即鏈?zhǔn)?/p>

39、基數(shù)排序鏈?zhǔn)交鶖?shù)排序。具體作法為：具體作法為： 待排序記錄以指針相鏈，構(gòu)成一個鏈表；待排序記錄以指針相鏈，構(gòu)成一個鏈表；“分配分配” ” 時，按當(dāng)前時，按當(dāng)前“關(guān)鍵字位關(guān)鍵字位”所取值，將記所取值，將記 錄分配到不同的錄分配到不同的 “ “鏈隊列鏈隊列” ” 中，每個隊列中記中，每個隊列中記 錄的錄的 “ “關(guān)鍵字位關(guān)鍵字位” ” 相同；相同；“收集收集”時，按當(dāng)前關(guān)鍵字位取值從小到大將時，按當(dāng)前關(guān)鍵字位取值從小到大將 各隊列首尾相鏈成一個鏈表各隊列首尾相鏈成一個鏈表; ;對每個關(guān)鍵字位均重復(fù)對每個關(guān)鍵字位均重復(fù) 2) 2) 和和 3) 3) 兩步。兩步。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)10.6 基數(shù)排序基數(shù)排序第第10章章 內(nèi)部排序內(nèi)部排序