《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第十章 原版ppt課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第十章 原版ppt課件.ppt（59頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,10.2 插入類排序,10.4 選擇類排序,第10章 內(nèi)部排序,10.3 交換類排序,10.5 歸并排序,10.6 基數(shù)排序,10.7 各種排序方法的總和比較,1,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將 一組“無(wú)序”的記錄序列調(diào)整為“有序”的記錄序列。,例如：將下列關(guān)鍵字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,調(diào)整為,14, 23, 36, 49, 52, 58, 61, 75, 80, 97,2,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,排序的定義：
2、 假設(shè)含n個(gè)記錄的序列為 a0, a1, ， an-1 其相應(yīng)的關(guān)鍵字序列為 K0, K1, ，Kn-1 ,這些關(guān)鍵字相互之間可以進(jìn)行比較，即在 它們之間存在著這樣一個(gè)關(guān)系 ： Kp0Kp1Kpn-1,按此固有關(guān)系將上式記錄序列重新排列為 ap0, ap1, ，apn-1 的操作稱作排序。,3,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,排序,內(nèi)部排序,外部排序,整個(gè)排序過程不需要訪問外存便能完成。,若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成。,穩(wěn)定排序,不穩(wěn)定排序,排序,相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中未發(fā)生變化。,相同關(guān)鍵字的領(lǐng)先關(guān)系在排序過程中發(fā)生變化。,4,
3、數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,內(nèi)部排序的過程： 是一個(gè)逐步擴(kuò)大記錄的有序序列長(zhǎng)度的過程。,經(jīng)過一趟排序,有序序列區(qū),無(wú) 序 序 列 區(qū),有序序列區(qū),無(wú) 序 序 列 區(qū),內(nèi)部排序的方法,5,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,基于不同的“擴(kuò)大” 有序序列長(zhǎng)度的方法，內(nèi)部排序方法大致可分下列幾種類型：,插入類,交換類,選擇類,歸并類,其它方法,6,數(shù) 據(jù) 結(jié) 構(gòu),10.1 概述,第10章 內(nèi)部排序,待排記錄的數(shù)據(jù)類型定義如下:,#define MAXSIZE 1000 typedef int KeyType; typedef struct KeyType ke
4、y; OtherType other_data; RecordType; typedef struct RcdType rMAXSIZE+1; int length; SqList;,7,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,將無(wú)序子序列中的一個(gè)或幾個(gè)記錄“插入”到有 序序列中，從而增加記錄的有序子序列的長(zhǎng)度。,有序序列a1.i-1,ai,無(wú)序序列 ai.n-1,一趟直接插入排序的基本思想：,有序序列a1.i,無(wú)序序列 ai+1.n-1,8,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,實(shí)現(xiàn)“一趟插入排序”可分三步進(jìn)行：,3將ai 插入(復(fù)制)到aj+1的位置上
5、。,2將aj+1.i中的所有記錄均后移一個(gè)位置；,1在a1.i-1中查找ai的插入位置， a1.j.key ai.key aj+1.i.key；,9,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序（基于順序查找）,希爾排序（基于逐趟縮小增量）,不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述,折半插入排序（基于折半查找）,表插入排序（基于鏈表存儲(chǔ)）,10,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,利用順序查找實(shí)現(xiàn)在r1.i-1中查找ri的插入位置,48,62,35,77,55,14,35,98,第1 趟,48,62,r0,62,35,2,35,48,6
6、2,3,77,77,4,55,55,62,77,5,14,14,35,48,55,62,77,6,35,35,48,55,62,77,7,98,98,從ri-1起向前進(jìn)行順序查找，監(jiān)視哨設(shè)置在r0；,r0 = ri;,循環(huán)結(jié)束表明ri的插入位置為 j +1,r0,j,ri,for (j=i-1; r0.keyrj.key; -j);,j=i-1,插入位置,11,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,對(duì)于在查找過程中找到的那些關(guān)鍵字不小于ri.key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動(dòng)；,for (j=i-1; r0.keyrj.key; -j); rj+1 = rj；,上
7、述循環(huán)結(jié)束后可以直接進(jìn)行“插入” rj+1 = r0；,r0,j,ri,j=i-1,插入位置,直接插入排序,12,令 i = 2，3，, n, 實(shí)現(xiàn)整個(gè)序列的排序。,for ( i=2; i=n; +i ) if (ri.keyri-1.key) 在 r1.i-1中查找ri的插入位置; 插入ri ; ,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,13,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,void InsertionSort ( SqList +i ) if (L.ri.key L.ri-1.key) ,L.r0 = L.ri; f
8、or ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; L.rj+1 = L.r0;,14,內(nèi)部排序的時(shí)間分析：,實(shí)現(xiàn)內(nèi)部排序的基本操作有兩個(gè)：,（2）“移動(dòng)”記錄。,（1）“比較”序列中兩個(gè)關(guān)鍵字的大??；,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入排序,15,對(duì) 于 直 接 插 入 排 序,最好的情況 （關(guān)鍵字在記錄序列中順序有序）：,“比較”的次數(shù)：,最壞的情況 （關(guān)鍵字在記錄序列中逆序有序）：,“比較”的次數(shù)：,0,“移動(dòng)”的次數(shù)：,“移動(dòng)”的次數(shù)：,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,直接插入
9、排序,16,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,折半插入排序,因?yàn)?r1.i-1 是一個(gè)按關(guān)鍵字有序的有序序列，則 可以利用折半查找實(shí)現(xiàn)“在r1.i-1中查找ri的插 入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩迦肱判颉?i,low,high,m,high,m,high,m,low,例如:,插入 位置,L.r,17,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,折半插入排序,void BiInsertionSort ( SqList i=L.length; +i ) ,L.r0 = L.ri;,for ( j=i-1; j=low; -j ) L.rj+1 = L.r
10、j;,L.rlow = L.r0;,18,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(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中折半查找插入位置；,19,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,基本思想： 對(duì)待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。,所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。,（又稱縮小增量排序）,20,將記錄序列分成
11、若干子序列，分 別對(duì)每個(gè)子序列進(jìn)行插入排序。,其中，d 稱為增量，它的值在排序過程中從 大到小逐漸縮小，直至最后一趟排序減為1。,例如：將 n 個(gè)記錄分成 d 個(gè)子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d ,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,具體做法為：,21,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,d1=4,17,55,05,13,d2=2,05,13,46,94,d3=1,13,17,70,94
12、,22,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,void ShellInsert ( SqList ,23,數(shù) 據(jù) 結(jié) 構(gòu),10.2 插入類排序,第10章 內(nèi)部排序,希爾排序,（又稱縮小增量排序）,void ShellSort (SqList ,24,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,基本思想：,通過交換逆序元素進(jìn)行排序的方法。,冒泡排序（相鄰比逆法）,快速排序,通過“交換”無(wú)序序列中的記錄從而得到其中關(guān)鍵字 最小或最大的記錄，并將它加入到有序子序列中， 以此方法增加記錄的有序子序列的長(zhǎng)度。,25,數(shù) 據(jù) 結(jié) 構(gòu),10.
13、3 交換類排序,第10章 內(nèi)部排序,冒泡排序（相鄰比逆法）,思想：在掃描的過程中順次比較相鄰的兩個(gè) 元素的大小，若逆序就交換位置。,第1趟,35,62,55,77,14,77,35,77,22,98,40,98,9次,第2趟,77,35,48,55,14,35,62,22,40,8次,第n-1趟,排序結(jié)束,n-i次,第i 趟,26,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,冒泡排序（相鄰比逆法）,void BubbleSort(RecordType r ,int length) n=length; for(i=1; irj+1.key) x=aj;rj=rj+1;rj+1=x;
14、 ,27,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,冒泡排序,時(shí)間分析:,28,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,改進(jìn)冒泡排序中一次交換只能消除一個(gè)逆序 的缺點(diǎn)，即實(shí)現(xiàn)一次交換消除多個(gè)逆序。,思想： 找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸”，凡其關(guān)鍵字 小于樞軸的記錄均移動(dòng)至該記錄之前，凡其關(guān)鍵字 大于樞軸的記錄均移動(dòng)至該記錄之后。 即對(duì)無(wú)序的記錄序列進(jìn)行“一次劃分”，,之后分別對(duì)分割所得兩個(gè)子序列“遞歸”進(jìn)行快速排序。,29,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,一次劃分（一趟快速排序）,r0,48,low,high
15、,high,35,low,62,high,14,low,low,77,high,high,48,30,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,int QKpass (RecordType r , int low, int high) ,r0 = rlow;,while (lowhigh) ,while(low= r0.key) - high;,rlow = rhigh;,while (lowhigh ,rhigh = rlow;,rlow = r0; return low;,一趟快速排序算法,31,void QKSort(RecordType r ,int low,
16、int high) r0=rlow; if(lowhigh) pos=QKpass(r,low,high); QKSort(r,low,pos-1); QkSort(r,pos+1,high); ,數(shù) 據(jù) 結(jié) 構(gòu),10.3 交換類排序,第10章 內(nèi)部排序,快速排序,算法,32,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,從記錄的無(wú)序子序列中“選擇”關(guān)鍵字最小或 最大的記錄，并將它加入到有序子序列中， 以此方法增加記錄的有序子序列的長(zhǎng)度。,簡(jiǎn)單選擇排序,堆排序,樹型選擇排序,33,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,簡(jiǎn)單選擇排序,i,第 1 趟,k,j,j,k
17、,j,j,j,k,j,j,14,48,2,i,k,j,35,62,3,35,62,4,48,77,5,55,6,62,77,7,77,8,98,void 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; ,34,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,樹型選擇排序,是一種按錦標(biāo)賽的思想進(jìn)行排序的方法。,49,38,27,65,97,76,49,13,38,65,13
18、,27,38,13,13,76,13,27,27,27,49,49,38,38,49,49,49,49,65,49,49,76,65,65,97,97,76,76,97,97,35,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,對(duì)樹型排序的進(jìn)一步改進(jìn)。,堆是滿足下列性質(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,不是堆,(小頂堆),(大頂堆),36,ri,r2i,r2i+1,若將該數(shù)
19、列視作完全二叉樹，則 r2i 是 ri 的左孩子；r2i+1 是 ri 的右孩子。,例如:,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49,12,36,27,65,40,34,98,81,73,55,49,14,14,是小頂堆,不,37,堆排序即是利用堆的特性對(duì)記錄序列進(jìn)行排序。,例如：,建大頂堆, 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 , 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 ,交換 98 和 12,重新調(diào)整為
20、大頂堆, 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 , 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 ,經(jīng)過篩選,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,38,1、如何由一個(gè)無(wú)序序列“建初堆”？,堆排序的兩個(gè)問題:,2、輸出堆頂后，如何“篩選”？,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,所謂“篩選”指的是，對(duì)一棵左/右子樹均為堆的完全 二叉樹，“調(diào)整”根結(jié)點(diǎn)使整個(gè)二叉樹也成為一個(gè)堆。,39,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,48,98,77,6
21、2,48,40,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,例如：, 48, 62, 35, 77, 55, 14, 35, 98,48,62,35,77,55,14,35,98,顯然不是一個(gè)堆,調(diào)整,如何建初堆？,41,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,98,77,98,77,62,98,77,62,48,42,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,98,48,98,77,62,48,77,35,77,62,55,35,62,62,14,55,48,14,55,55,35,48,35,48,48,14,35,1
22、4,35,35,35,35,35,14,14,43,時(shí)間復(fù)雜度分析,1. 對(duì)深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字 比較的次數(shù)至多為2(k-1)；,3. 調(diào)整“堆頂”n-1次，總共進(jìn)行的關(guān)鍵字比較的次數(shù) 不超過 2(log2(n-1)+log2(n-2)+ +log22)2n(log2n),因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)。,2. 對(duì)n個(gè)關(guān)鍵字，建成深度為h(=log2n+1)的堆， 所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多4n；,數(shù) 據(jù) 結(jié) 構(gòu),10.4 選擇類排序,第10章 內(nèi)部排序,堆排序,44,數(shù) 據(jù) 結(jié) 構(gòu),10.5 歸并類排序,第10章 內(nèi)部排序,通過“歸并”兩個(gè)或兩個(gè)以上的記錄有
23、序 子序列，逐步增加記錄有序序列的長(zhǎng)度。,在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的記錄有序子序列,歸并為一個(gè)記錄的有序序列。,有 序 序 列 rl.n,有序子序列 rl.m,有序子序列 rm+1.n,45,數(shù) 據(jù) 結(jié) 構(gòu),10.5 歸并類排序,第10章 內(nèi)部排序,例如：19，13，05，27，01，26，31，16,13，19,05，27,01，26,16 ，31,05，13，19，27,01，16，26，31,01，05，13，16，19，26，27，31,很少進(jìn)行內(nèi)排序，主要用于外排序。,46,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,主要利用分配和收集
24、兩種基本操作。 典型的就是基數(shù)類排序。,多關(guān)鍵字的排序,鏈?zhǔn)交鶖?shù)排序,47,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,多關(guān)鍵字的排序,最低位優(yōu)先LSD法,最高位優(yōu)先MSD法,先對(duì)K0進(jìn)行排序，并按 K0 的不同值將記錄序列分 成若干子序列之后，分別對(duì) K1 進(jìn)行排序，.， 依次類推，直至最后對(duì)最次位關(guān)鍵字排序完成為止。,先對(duì) Kd-1 進(jìn)行排序，然后對(duì) Kd-2 進(jìn)行排序，依 次類推，直至對(duì)最主位關(guān)鍵字 K0 排序完成為止。,排序過程中不需要根據(jù) “前一個(gè)” 關(guān)鍵字的排序結(jié)果， 將記錄序列分割成若干個(gè)(“前一個(gè)”關(guān)鍵字不同的)子 序列。,48,例如:學(xué)生記錄含三個(gè)關(guān)鍵字:系別、班
25、號(hào)和 班內(nèi)的序列號(hào)，其中以系別為最主位關(guān)鍵字。,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,LSD的排序過程如下:,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,多關(guān)鍵字的排序,49,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈?zhǔn)交鶖?shù)排序,假如多關(guān)鍵字的記錄序列中，每個(gè)關(guān)鍵字的取值范 圍相同，則按LSD法進(jìn)行排序時(shí)，可以采用“分配-收 集”的方法，其好處是不需要進(jìn)行關(guān)鍵字間的比較。,對(duì)于數(shù)字型或字符型的單關(guān)
26、鍵字，可以看成是由多個(gè) 數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種 “分配-收集”的辦法進(jìn)行排序，稱作基數(shù)排序法。,50,例如：對(duì)下列這組關(guān)鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 ,首先按其 “個(gè)位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后按從 0 至 9 的順序?qū)?它們 “收集” 在一起；,然后按其 “十位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序?qū)⑺鼈儭笆占痹谝黄穑?最后按其“百位數(shù)”重復(fù)一遍上述操作。,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序
27、,鏈?zhǔn)交鶖?shù)排序,51,在計(jì)算機(jī)上實(shí)現(xiàn)基數(shù)排序時(shí)，為減少所需輔助存儲(chǔ)空間，應(yīng)采用鏈表作存儲(chǔ)結(jié)構(gòu)，即鏈?zhǔn)交鶖?shù)排序。 具體作法為：,待排序記錄以指針相鏈，構(gòu)成一個(gè)鏈表；,“分配” 時(shí)，按當(dāng)前“關(guān)鍵字位”所取值，將記 錄分配到不同的 “鏈隊(duì)列” 中，每個(gè)隊(duì)列中記 錄的 “關(guān)鍵字位” 相同；,“收集”時(shí)，按當(dāng)前關(guān)鍵字位取值從小到大將 各隊(duì)列首尾相鏈成一個(gè)鏈表;,對(duì)每個(gè)關(guān)鍵字位均重復(fù) 2) 和 3) 兩步。,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈?zhǔn)交鶖?shù)排序,52,例如：,p369367167239237138230139,進(jìn)行第一次分配,進(jìn)行第一次收集,f0 r0,f7 r7,f8 r
28、8,f9 r9,p230,230,367,167,237,367167237,138,369239139,369,239,139,138,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈?zhǔn)交鶖?shù)排序,53,數(shù) 據(jù) 結(jié) 構(gòu),10.6 基數(shù)排序,第10章 內(nèi)部排序,鏈?zhǔn)交鶖?shù)排序,進(jìn)行第二次分配,p230237138239139,f3 r3,f6 r6,230,237,138,239,139,367,167,369,367167369,進(jìn)行第二次收集,54,f1 r1,進(jìn)行第三次分配,f2 r2,f3 r3,138,139,167,230,237,239,367,369,數(shù) 據(jù) 結(jié) 構(gòu),10
29、.6 基數(shù)排序,第10章 內(nèi)部排序,鏈?zhǔn)交鶖?shù)排序,進(jìn)行第三次收集之后便得到記錄的有序序列,55,數(shù) 據(jù) 結(jié) 構(gòu),10.7各種排序方法的綜合比較,第10章 內(nèi)部排序,各種排序方法的性能比較,56,數(shù) 據(jù) 結(jié) 構(gòu),10.7各種排序方法的綜合比較,第10章 內(nèi)部排序,各種排序方法的穩(wěn)定性比較,57,數(shù) 據(jù) 結(jié) 構(gòu),10.7各種排序方法的綜合比較,第10章 內(nèi)部排序,有效結(jié)論：,簡(jiǎn)單排序法一般只用于n較小的情況；,當(dāng)序列中的記錄“基本有序”時(shí)，直接插入排序最佳；,就平均時(shí)間性能而言，快速排序是最好的；,當(dāng)n值很大而關(guān)鍵字的位數(shù)d較小時(shí)，選擇基數(shù)排序；,可將簡(jiǎn)單排序與性能較好的排序方法結(jié)合使用。,總之，應(yīng)具體情況具體對(duì)待。,58,此課件下載可自行編輯修改，供參考！ 感謝您的支持，我們努力做得更好！,59,
嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言版第十章 原版ppt課件.ppt
