數(shù)據(jù)結(jié)構(gòu)6第6章：內(nèi)部分類(lèi)

1、第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 12015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)存中完成：內(nèi)存中完成：6.1 簡(jiǎn)單的分類(lèi)算法簡(jiǎn)單的分類(lèi)算法6.2 Shell分類(lèi)分類(lèi)6.3 快速分類(lèi)快速分類(lèi)6.4 歸并分類(lèi)歸并分類(lèi)6.5 堆分類(lèi)堆分類(lèi)6.6 基數(shù)分類(lèi)基數(shù)分類(lèi)第第6章章 內(nèi)部分類(lèi)（內(nèi)部分類(lèi)（Sorting）分類(lèi)分類(lèi)內(nèi)部分類(lèi)內(nèi)部分類(lèi)外部分類(lèi)外部分類(lèi)外存上完成：外存上完成：歸并歸并第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 22015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法分類(lèi)分類(lèi)(Sorting)也叫排序也叫排序(Ordering)，是將一組數(shù)據(jù)按照規(guī)定順，是將一組數(shù)據(jù)按照規(guī)

2、定順序進(jìn)行排列，其目的是為了方便查詢(xún)和處理。序進(jìn)行排列，其目的是為了方便查詢(xún)和處理。對(duì)于給定數(shù)組對(duì)于給定數(shù)組A，經(jīng)過(guò)分類(lèi)處理之后，滿(mǎn)足關(guān)系：，經(jīng)過(guò)分類(lèi)處理之后，滿(mǎn)足關(guān)系： A1.keyA2.key An.key如果在分類(lèi)之前存在關(guān)系如果在分類(lèi)之前存在關(guān)系 Ai.key=Aj.key ( 1ijn )經(jīng)分類(lèi)后，經(jīng)分類(lèi)后，Ai和和Aj分別被移至分別被移至Ai1和和Aj1，并且，并且i1和和j1滿(mǎn)足關(guān)系滿(mǎn)足關(guān)系 1i1j1n我們稱(chēng)這種分類(lèi)是我們稱(chēng)這種分類(lèi)是穩(wěn)定穩(wěn)定的，否則稱(chēng)其為的，否則稱(chēng)其為不穩(wěn)定不穩(wěn)定的分類(lèi)。的分類(lèi)。第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 32015秋秋數(shù)據(jù)結(jié)構(gòu)與算

3、法數(shù)據(jù)結(jié)構(gòu)與算法按分類(lèi)時(shí)分類(lèi)對(duì)象存放的設(shè)備，分成內(nèi)部分類(lèi)按分類(lèi)時(shí)分類(lèi)對(duì)象存放的設(shè)備，分成內(nèi)部分類(lèi)(internal sorting)和外部分類(lèi)和外部分類(lèi)(external sorting)。分類(lèi)分類(lèi)過(guò)程中數(shù)據(jù)對(duì)象全部在內(nèi)存中的分類(lèi)，叫內(nèi)部分類(lèi)。過(guò)程中數(shù)據(jù)對(duì)象全部在內(nèi)存中的分類(lèi)，叫內(nèi)部分類(lèi)。分類(lèi)過(guò)程數(shù)據(jù)對(duì)象并非完全在內(nèi)存中的分類(lèi)，叫外部分類(lèi)。分類(lèi)過(guò)程數(shù)據(jù)對(duì)象并非完全在內(nèi)存中的分類(lèi)，叫外部分類(lèi)。分類(lèi)的種類(lèi)分類(lèi)的種類(lèi)struct records keytype key ; fields other ; ；typedef records LISTmaxsize ;分類(lèi)表的存儲(chǔ)結(jié)構(gòu)分類(lèi)表的存儲(chǔ)結(jié)構(gòu)影響分

4、類(lèi)性能的因素影響分類(lèi)性能的因素比較關(guān)鍵字的次數(shù)比較關(guān)鍵字的次數(shù)當(dāng)關(guān)鍵字是字符串時(shí)，是主要因素。當(dāng)關(guān)鍵字是字符串時(shí)，是主要因素。交換記錄位置和移動(dòng)記錄的次數(shù)交換記錄位置和移動(dòng)記錄的次數(shù)當(dāng)記錄很大時(shí)，是主要因素。當(dāng)記錄很大時(shí)，是主要因素。第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 42015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 0 1 2 3 4 5 6 7 8 9 10265 076301 265 129751 301 265 265129 751 301 301 301937 129 751 438 438 438863 937 438 751 694 694 694742 863 9

5、37 694 751 742 742 742694 742 863 937 742 751 751 751 751076 694 742 863 937 863 863 863 863 863438 438 694 742 863 937 937 937 937 937 937如何取消不必如何取消不必要的循環(huán)？要的循環(huán)？6.1 簡(jiǎn)單的分類(lèi)算法簡(jiǎn)單的分類(lèi)算法6.1.1 氣泡分類(lèi)氣泡分類(lèi)第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 52015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法氣泡分類(lèi)算法：氣泡分類(lèi)算法：Void BubbleSort ( int n , LIST &A ) int

6、x, y ; for ( i =1; i = i+1; j- ) if ( Aj.key =i+1; j-) /較小元素較小元素Aj if( Aj.key Aj-1.key ) flag=1; swap(Aj,Aj-1); for( j=i+1; j Aj+1.key ) flag=1; swap(Aj,Aj+1); i+; T(n)=O(n2)flag ?第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 72015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 初始狀態(tài)：初始狀態(tài)： (265) 301 751 129 937 863 742 694 076 438 第第1趟：趟： (265 301)

7、 751 129 937 863 742 694 076 438 第第2趟：趟： (265 301 751) 129 937 863 742 694 076 438 第第3趟：趟： (129 265 301 751) 937 863 742 694 076 438 第第4趟：趟： (129 265 301 751 937) 863 742 694 076 438 第第5趟：趟： (129 265 301 751 863 937) 742 694 076 438 第第6趟：趟： (129 265 301 742 751 863 937) 694 076 438 第第7趟：趟： (129 265

8、301 694 742 751 863 937) 076 438 第第8趟：趟： (076 129 265 301 694 742 751 863 937) 438 第第9趟：趟： (076 129 265 301 438 694 742 751 863 937) 6.1.2 插入分類(lèi)插入分類(lèi)第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 82015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法插入分類(lèi)算法：插入分類(lèi)算法：void InsertSort ( n, A )Int n; LIST A ; int i, j ; A0.key = - ; for(i=1; i=n; i+) j=i; whi

9、le(Aj.keyAj-1.key) swap(Aj,Aj-1) ; j=j-1; T(n)=O(n2)j=i; temp=AjWhile (temp.keyAj-1.key) Aj=Aj-1; j=j-1; Aj=temp;第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 92015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 初始狀態(tài)：初始狀態(tài)： 265 301 751 129 937 863 742 694 076 438 第第1趟：趟： 076 301 751 129 937 863 742 694 265 438 第第2趟：趟： 076 129 751 301 937 863 742 69

10、4 265 438 第第3趟：趟： 076 129 265 301 937 863 742 694 751 438 第第4趟：趟： 076 129 265 301 937 863 742 694 751 438 第第5趟：趟： 076 129 265 301 438 863 742 694 751 937 第第6趟：趟： 076 129 265 301 438 694 742 863 751 937 第第7趟：趟： 076 129 265 301 438 694 742 863 751 937 第第8趟：趟： 076 129 265 301 438 694 742 751 863 937 第第

11、9趟：趟： 076 129 265 301 438 694 742 751 863 9376.1.3 選擇分類(lèi)選擇分類(lèi)第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 102015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法選擇分類(lèi)算法（冒泡程序）選擇分類(lèi)算法（冒泡程序）void SelectSort ( n, A )int n; LIST A ; int i, j，lowindex ; keytype lowkey; for(i=1; in; i+) lowindex = i ; for ( j = i+1; j=n; j+) if ( Aj.key Ai+1) swap(Ai,Ai+1);if(

12、AiAi+1) swap(Ai,Ai+1); 重復(fù)上述二趟交換過(guò)程交換進(jìn)行，直至整個(gè)數(shù)組有序。重復(fù)上述二趟交換過(guò)程交換進(jìn)行，直至整個(gè)數(shù)組有序。問(wèn)：?jiǎn)枺?(1)(1)結(jié)束條件是什么？結(jié)束條件是什么？ (2)(2)實(shí)現(xiàn)算法。實(shí)現(xiàn)算法。第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 122015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法Void OESort(LIST &A , int n) int i , flag ; do flag = 0 ; for( i=0; i Ai+1 ) flag = 1; swap(Ai,Ai+1); for( i=1; i Ai+1 ) flag = 1;

13、swap(Ai,Ai+1); while(flag); (2)奇偶轉(zhuǎn)換排序算法：奇偶轉(zhuǎn)換排序算法：(1)結(jié)束條件為不產(chǎn)生交換：結(jié)束條件為不產(chǎn)生交換：第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 132015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法6.2 Shell 分類(lèi)分類(lèi)希爾（希爾（ShellShell）排序又稱(chēng)縮小增量法，基本思想為：）排序又稱(chēng)縮小增量法，基本思想為：先取定一個(gè)整數(shù)先取定一個(gè)整數(shù)d d1 1nn，把全部結(jié)點(diǎn)分成，把全部結(jié)點(diǎn)分成d d1 1個(gè)組，所有距離為個(gè)組，所有距離為d d1 1倍數(shù)的記錄放在一組中，在各組內(nèi)進(jìn)行直接插入排序；然倍數(shù)的記錄放在一組中，在各組內(nèi)進(jìn)行直接插入

14、排序；然后取后取d d2 2d= 1; k /= 2 ) for( i=k+1; i0) & (x.keyR（L=R+1），成功劃分，），成功劃分，L是右邊子序列的是右邊子序列的 起始下表；起始下表； 交換：若交換：若LR（L=R+1）為止。）為止。第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 192015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法int findpivot( int i, int j ) keytype firstkey ; int k ; firstkey = Ai.key ; for ( k=i ; k firstkey ) return k ; else if

15、( Ak.key firstkey ) return i ; return 0 ;找中間值找中間值算法算法:第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 202015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法Int partion ( i, j, pivot )Int i, j; keytype pivot ; int L, R ; L = i ; R = j ; do swap ( AL, AR ) ; while ( AL.key = pivot ) R = R -1 ; while ( L = R ); return L ;Void quicksort ( int i, int j )

16、keytype pivot ; int piovtindex , k ; pivotindex = findpivot( i, j ) ; if ( pivotindex ) pivot = Apivotindex.key ; k = partion ( i, j, pivot ) ; quicksort( i, k-1); quicksort( k, j ); 分割分割: i, , j i, k-1, k, k+1, j 快速分類(lèi)快速分類(lèi)調(diào)用：調(diào)用：quicksort( 1, n )T(n) = O( f(n) )第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 212015秋秋數(shù)據(jù)結(jié)

17、構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法3562951413時(shí)間復(fù)雜性和穩(wěn)定性時(shí)間復(fù)雜性和穩(wěn)定性時(shí)間復(fù)雜性：時(shí)間復(fù)雜性：T(n) =O(nlog2n) 穩(wěn)定性：是不穩(wěn)定的分類(lèi)穩(wěn)定性：是不穩(wěn)定的分類(lèi)舉例舉例3563954112v =35569334v =5433v =49565v =9655v =6211v =29655433211組合組合第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 222015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法例：對(duì)長(zhǎng)度為例：對(duì)長(zhǎng)度為n的記錄序列進(jìn)行快速排序時(shí)，所需要的比較次數(shù)的記錄序列進(jìn)行快速排序時(shí)，所需要的比較次數(shù) 依賴(lài)于這依賴(lài)于這n個(gè)元素的初始序列。個(gè)元素的初始序列。 問(wèn)：?jiǎn)枺?

18、1) 當(dāng)當(dāng)n=8時(shí)，在最好情況下需要進(jìn)行多少次比較？時(shí)，在最好情況下需要進(jìn)行多少次比較？ (2) 給出給出n=8時(shí)的最好情況的初始排序?qū)嵗r(shí)的最好情況的初始排序?qū)嵗?。解：解：n=8n=3n=4n=1n=1n=1n=2n=17次比較2次比較3次比較1次比較(1) 共共13次次第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 232015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法(2) 如：如： 23 13 17 21 60 30 18 28一次劃分后：一次劃分后：18 13 17 21 23 30 60 28二次劃分后：二次劃分后：17 13 18 21四次劃分后：四次劃分后： 28 30 60三

19、次劃分后：三次劃分后：13 17 13216028結(jié)果：結(jié)果： 13 17 18 21 23 28 30 60第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 242015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法int Partition(int i，int j，int pivot) /對(duì)對(duì)Alow.high做劃分，并返回基準(zhǔn)記錄的位置做劃分，并返回基準(zhǔn)記錄的位置 while(ij) /從區(qū)間兩端交替向中間掃描，直至從區(qū)間兩端交替向中間掃描，直至i=j為止為止 while(i=pivot) /pivot相當(dāng)于在位置相當(dāng)于在位置i上上 j-； /從右向左掃描，查找第從右向左掃描，查找第1個(gè)關(guān)鍵字小

20、于個(gè)關(guān)鍵字小于pivot的記錄的記錄Aj if(ij) /表示找到的表示找到的Aj的關(guān)鍵字的關(guān)鍵字pivot Ai+=Aj； /相當(dāng)于交換相當(dāng)于交換Ai和和Aj，交換后，交換后i指針加指針加1 while(ij&Ai.key=pivot) /pivot相當(dāng)于在位置相當(dāng)于在位置j上上 i+； /從左向右掃描，查找第從左向右掃描，查找第1個(gè)關(guān)鍵字大于個(gè)關(guān)鍵字大于pivot的記錄的記錄Ai if(ipivot Aj-=Ai; /相當(dāng)于交換相當(dāng)于交換Ai和和Aj，交換后，交換后j指針減指針減1 /endwhile Ai=pivot； /基準(zhǔn)記錄已被最后定位基準(zhǔn)記錄已被最后定位 return i

21、； /partition 另一種劃分方法另一種劃分方法第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 252015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法6.4 歸并分類(lèi)歸并分類(lèi)合并兩個(gè)有序序列合并兩個(gè)有序序列Void merge ( l l , m, n, A, B )Int l l, m, n ; LIST A, &B ; int i, j, k, t ; i = l l ; k = l l ; j = m+1 ; while ( ( i = m ) & ( j = n ) ) if ( Ai.key m ) for ( t = j ; t = n ; t+ ) Bk+t-

22、j = At ; else for ( t = i ; t = m ; t+ ) Bk+t-i = At ;合并Al,Am 和 Am+1,An形成新的分類(lèi)序列 Bl,Bn算法時(shí)間復(fù)雜度T(n) = O(n-l+1)第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 262015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法26 5 77 1 61 11 59 15 48 19 5 26 1 77 11 61 15 59 19 48 1 5 26 77 11 15 59 61 19 48 1 5 11 15 26 59 61 77 19 48 1 5 11 15 19 26 48 59 61 77 歸并次

23、數(shù)：歸并次數(shù)：1，2， ，2i-1，若長(zhǎng)度為若長(zhǎng)度為 n ，則共需歸并，則共需歸并 log2n總的時(shí)間復(fù)雜性為：總的時(shí)間復(fù)雜性為：T(n) = O( nlog2 n )第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 272015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法Void mpass ( n, l l, A , B )int n, l l ; LIST A, &B ; int i , t ; i = 1 ; while ( i = (n-2*l l+1) ) merge ( i, i+l l-1, i+2*l l-1, A, B ) i = i + 2*l l ; if ( i+l

24、 l-1) n ) merge ( i , i+l l-1, n, A, B ); else for ( t = i ; t = n ; t+ ) Bt = At;Void T_W_SORT(n , A )Int n ; LIST &A ; int l l ; LIST B ; l l = 1 ; while( l l n ) mpass( n, l l, A, B ) ; l l = 2* l l ; mpass( n, l l, B, A ) ; l l = 2*l l ; 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 282015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法Void

25、 merge ( l , m, n, A, B )Void mpass ( n, l, A , B )l m m+1 nl nABi = 1 ;while ( i = (n-2*l+1) ) merge ( i, i+l-1, i+2*l-1, A, B ) i = i + 2*l ; if ( i+l-1) n ) merge ( i , i+l-1, n, A, B );else for ( t = i ; t ll第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 292015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法26 5 77 1 61 11 59 15 48 19 5 26 1 77

26、11 61 15 59 19 48 1 5 26 77 11 15 59 61 19 48 1 5 11 15 26 59 61 77 19 48 1 5 11 15 19 26 48 59 61 77 歸并次數(shù)：歸并次數(shù)：1，2， ，2i-1，若長(zhǎng)度為若長(zhǎng)度為 n ，則共需歸并，則共需歸并 log2n總的時(shí)間復(fù)雜性為：總的時(shí)間復(fù)雜性為：T(n) = O( nlog2 n )第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 302015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法6.5 堆分類(lèi)堆分類(lèi)定義定義把具有如下性質(zhì)的數(shù)組把具有如下性質(zhì)的數(shù)組A表示的二元樹(shù)稱(chēng)為堆（表示的二元樹(shù)稱(chēng)為堆（Heap）:

27、 (1) 若若2*in，則，則Ai.key A2*i.key ; (2) 若若2*i+1n，則，則Ai.keyA2*i+1.key ; 小頂堆小頂堆 或：或： 把具有如下性質(zhì)的數(shù)組把具有如下性質(zhì)的數(shù)組A表示的二元樹(shù)稱(chēng)為堆（表示的二元樹(shù)稱(chēng)為堆（Heap）: (1) 若若2*in，則，則Ai.key A2*i.key ; (2) 若若2*i+1n，則，則Ai.key A2*i+1.key ; 大頂堆大頂堆例：例：11233946551 1 2 3 3 9 4 6 5 5第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 312015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法11233946551 1 2

28、 3 3 9 4 6 5 51325394651 3 2 5 3 9 4 6 5 1234539562 3 4 5 3 9 5 6 1 133456953 3 4 5 6 9 5 2 1 13545693 5 4 5 6 9 3 2 1 1459564 5 9 5 6 3 3 2 1 155965 5 9 6 4 3 3 2 1 15695 6 9 5 4 3 3 2 1 1696 9 5 5 4 3 3 2 1 199 6 5 5 4 3 3 2 1 1第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 322015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法Void pushdown( first

29、, last )Int first , last ; int r ; r = first ; while ( r A2*r.key ) swap ( Ar, A2*r ) ; r = last ; /*結(jié)束循環(huán)結(jié)束循環(huán)*/ else if ( ( Ar.key A2*r.key ) & ( A2*r.key A2*r+1.key ) & ( A2*r+1.key = 1 ; i- ) pushdown( i , n ) ; for ( i = n ; i = 2 ; i- ) swap ( A1, Ai ) ; pushdown ( 1, i -1 ) ; T( n ) = O

30、 ( nlog2n )整理堆整理堆建堆建堆堆排序堆排序？first ？last ?第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 352015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法6.6 基數(shù)分類(lèi)基數(shù)分類(lèi)多關(guān)鍵字分類(lèi)多關(guān)鍵字分類(lèi)321 986 123 432 543 018 765 678 987 789 098 890 109 901 210 012Q0:901 109Q1:210 012 018Q2:321 123Q3:432Q4:543Q5:Q6:765Q7:678Q8:986 987 789Q9:890 098901 109 210 012 018 321 123 432 543 7

31、65 678 986 987 789 890 098Q0:012 018 098Q1:109 123Q2:210Q3:321Q4:432Q5:543Q6:678Q7:765 789Q8:890Q9: 901 986 987012 018 098 109 123 310 321 432 543 678 765 789 890 901 986 987Q0:890 210Q1:321 901Q2:432 012Q3:123 543Q4:Q5:765Q6:986Q7:987Q8:018 678 098Q9:789 109890 210 321 901 432 012 123 543 765 986 9

32、87 018 678 098 789 109 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 362015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法Void radixsort ( figure , A )int figure ; QUEUE &A ; QUEUE Q10 ; records data ; int pass, r, i ; for ( pass=1 ; pass =figure ; pass+ ) for ( i=0 ; i=9 ; i+ ) MAKENULL( Qi ) ; while ( !EMPTY( A ) ) data = FRONT ( A ) ; DEQUE

33、UE ( A ) ; r = RADIX( data. key , pass ) ; ENQUEUE( data , Qr ) ; for ( i=0 ; i =9 ; i+ ) while ( !EMPTY( Qi ) ) data = FRONT ( Qi ) ; DEQUEUE( Qi ) ; ENQUEUE( data , A ) ; Int RADIX( k, p )Int k, p ; int power , i ; power = 1 ; for ( i=1; i=1 ; j- ) for ( i=0 ; i = m-1 ; i+ ) 初始化桶 Qi ; while ( QUEU

34、E 不空 ) 設(shè) Ai 為 QUEUE 的隊(duì)首元素，刪除Ai，并放到桶Qaij中 ； for ( i=0 ; i = m-1 ; i+ ) 將桶 Qi 連接到隊(duì)列 QUEUE 后 ; 詞典排序算法第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 382015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法6.8* 求第求第 k 個(gè)最小元素個(gè)最小元素順序統(tǒng)計(jì)問(wèn)題順序統(tǒng)計(jì)問(wèn)題在一個(gè)含有 n 個(gè)元素的序列中，要求出第 k 個(gè)最小元素, 也稱(chēng)順序統(tǒng)計(jì)?？梢韵冗M(jìn)行排序，然后求出第 k 個(gè)最小元素。T(n) = O(nlogn)。下面的算法使得 T(n) =O (n)。（證明P233略）基本思想： 根據(jù)某一元素m

35、將 原序列 S 化分成3個(gè)子序列S1，S2和S3，使得S1的所有元素都小于m ，S2的所有元素等于m，而S3的所有元素都大于m，通過(guò)統(tǒng)計(jì)S1和S2的元素個(gè)數(shù)，可以確定所求的第 k 個(gè)最小元素是在S1和S2或S3中。 通過(guò)上述方式，將一個(gè)給定的問(wèn)題轉(zhuǎn)換成一個(gè)更小的問(wèn)題。為保證O(n)，必須保證在線(xiàn)性時(shí)間里找到劃分元素 m，使得S1和S2的大小 不超過(guò)S的一個(gè)固定部分。問(wèn)題的關(guān)鍵是如何選擇劃分元素m。下面算法中，S 被劃分成若干子序列，每個(gè)子序列由 5 個(gè)元素組成。對(duì)每個(gè)子序列排序，取其中值組成一個(gè)序列 M。M 只包含 n/5 個(gè)元素， 可以比原來(lái)快 5 倍的速度找到 n 個(gè)元素的中值。第第6 6

36、章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 392015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法輸入：由 n 個(gè)元素組成的序列 S 和 整數(shù) k (1kn) 。輸出：S 中第 k 個(gè)最小元素 。Elementtype Select ( int k , LIST S ) if ( |S| = k ) return Select ( k , S1 ) ; else if ( |S1| + |S2| = k ) return m ; else return Select ( k - |S1| - |S2| , S3 ); 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 402015秋秋數(shù)據(jù)結(jié)構(gòu)與算

37、法數(shù)據(jù)結(jié)構(gòu)與算法小結(jié)小結(jié)各種排序的比較各種排序的比較排序方法排序方法平均時(shí)間平均時(shí)間最好情況最好情況最壞情況最壞情況輔助空間輔助空間穩(wěn)定性穩(wěn)定性簡(jiǎn)單排序簡(jiǎn)單排序O( n2 )O（n）O( n2 )O( 1 )穩(wěn)定穩(wěn)定希爾排序希爾排序O（n1.3）-O( 1 )不穩(wěn)定不穩(wěn)定快速排序快速排序O( nlog2n )O( nlog2n )O( n2 )O( log2n )不穩(wěn)定不穩(wěn)定堆排序堆排序O( nlog2n )O( nlog2n )O( nlog2n )O( 1 )不穩(wěn)定不穩(wěn)定歸并排序歸并排序O( nlog2n )O( nlog2n )O( nlog2n )O( n )穩(wěn)定穩(wěn)定基數(shù)排序基數(shù)排序O

38、( d (n+rd)O( d (n+rd) O( d (n+rd) O(n+ rd )穩(wěn)定穩(wěn)定第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 412015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法不同條件下，排序方法的選擇：不同條件下，排序方法的選擇：(1)若n較小(如n50)，可采用直接插入或直接選擇排序。 當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動(dòng)的記錄數(shù)少于 直接插人，應(yīng)選直接選擇排序?yàn)橐恕?2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序 為宜；且以直接插入排序最佳。(3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法： 快速排序、堆排序

39、或歸并排序。 快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法， 當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；堆排序所需的輔助空間少于快速排序，并且不會(huì)出現(xiàn)快速排序可能出現(xiàn)的最壞況。 這兩種排序都是不穩(wěn)定的?；鶖?shù)排序適用于 n 值很大而關(guān)鍵字較小的序列。若要求排序穩(wěn)定，則可選用歸并排序，基數(shù)排序穩(wěn)定性最佳。第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 422015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法課堂練習(xí)題：課堂練習(xí)題：在上面的排序方法中:(1)直接插入排序、冒泡排序、歸并排序和基數(shù)排序是穩(wěn)定的。(2)其他排序算法均是不穩(wěn)定的。(3)以帶 * 號(hào)的表示區(qū)別： 希爾排序：

40、8, 1, 10, 5, 6, 8* 快速排序： 2, 2*, 1 直接選擇排序： 2, 2*, 1 堆排序： 2, 2*, 1 1、以關(guān)鍵字序列 (265, 301, 751, 129, 937, 863, 742, 694, 076, 438)為例， 分別寫(xiě)出執(zhí)行以下排序算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。 (1) 直接插入排序 (2)希爾排序 (3)冒泡排序 (4)快速排序 (5) 直接選擇排序 (6) 歸并排序 (7) 堆排序 (8)基數(shù)排序 上述方法中： (1)哪些是穩(wěn)定的排序? (2)哪些是非穩(wěn)定的排序? (3)對(duì)不穩(wěn)定的排序試舉出一個(gè)不穩(wěn)定的實(shí)例。第第6 6章章 內(nèi)部分類(lèi)內(nèi)部

41、分類(lèi) Slide. 6 - 432015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法初始態(tài)：265 301 751 129 937 863 742 694 076 438第一趟：265 301 751 129 937 863 742 694 076 438第二趟：265 301 751 129 937 863 742 694 076 438第三趟：129 265 301 751 937 863 742 694 076 438第四趟：129 265 301 751 937 863 742 694 076 438第五趟：129 265 301 751 863 937 742 694 076 438第六趟：12

42、9 265 301 742 751 863 937 694 076 438第七趟：129 265 301 694 742 751 863 937 076 438第八趟：076 129 265 301 694 742 751 863 937 438第九趟：076 129 265 301 438 694 742 751 863 937 (1)直接插入排序直接插入排序(方括號(hào)表示無(wú)序區(qū)方括號(hào)表示無(wú)序區(qū))(2)希爾排序希爾排序(增量為增量為5，3，1)初始態(tài)：265 301 751 129 937 863 742 694 076 438 第一趟：265 301 694 076 438 863 742

43、751 129 937 第二趟：076 301 129 265 438 694 742 751 863 937 第三趟：076 129 265 301 438 694 742 751 863 937 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 442015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法 (3)冒泡排序冒泡排序(方括號(hào)為無(wú)序區(qū)方括號(hào)為無(wú)序區(qū))初始態(tài)： 265 301 751 129 937 863 742 694 076 438 第一趟： 076 265 301 751 129 937 863 742 694 438 第二趟： 076 129 265 301 751 438 937

44、 863 742 694 第三趟： 076 129 265 301 438 694 751 937 863 742 第四趟： 076 129 265 301 438 694 742 751 937 863 第五趟： 076 129 265 301 438 694 742 751 863 937 第六趟： 076 129 265 301 438 694 742 751 863 937(4)快速排序快速排序(方括號(hào)表示無(wú)序區(qū)，層表示對(duì)應(yīng)的遞歸樹(shù)的層數(shù)方括號(hào)表示無(wú)序區(qū)，層表示對(duì)應(yīng)的遞歸樹(shù)的層數(shù))初始態(tài)： 265 301 751 129 937 863 742 694 076 438第二層： 076

45、129 265 751 937 863 742 694 301 438第三層： 076 129 265 438 301 694 742 751 863 937第四層： 076 129 265 301 438 694 742 751 863 937第五層： 076 129 265 301 438 694 742 751 863 937第六層： 076 129 265 301 438 694 742 751 863 937第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 452015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法(5)直接選擇排序直接選擇排序(方括號(hào)為無(wú)序區(qū)方括號(hào)為無(wú)序區(qū)) 初始態(tài) 265

46、 301 751 129 937 863 742 694 076 438第一趟： 076 301 751 129 937 863 742 694 265 438第二趟： 076 129 751 301 937 863 742 694 265 438第三趟： 076 129 265 301 937 863 742 694 751 438第四趟： 076 129 265 301 937 863 742 694 751 438第五趟： 076 129 265 301 438 863 742 694 751 937第六趟： 076 129 265 301 438 694 742 751 863 937

47、第七趟： 076 129 265 301 438 694 742 751 863 937第八趟： 076 129 265 301 438 694 742 751 937 863第九趟： 076 129 265 301 438 694 742 751 863 937(6)歸并排序歸并排序(為了表示方便，采用自底向上的歸并，方括號(hào)為有序區(qū)為了表示方便，采用自底向上的歸并，方括號(hào)為有序區(qū))初始態(tài)：265 301 751 129 937 863 742 694 076 438第一趟：265 301 129 751 863 937 694 742 076 438第二趟：129 265 301 751 6

48、94 742 863 937 076 438第三趟：129 265 301 694 742 751 863 937 076 438第四趟：076 129 265 301 438 694 742 751 863 937第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 462015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法(6)堆排序（通過(guò)畫(huà)二叉樹(shù)可以一步步得出排序結(jié)果）堆排序（通過(guò)畫(huà)二叉樹(shù)可以一步步得出排序結(jié)果）初始態(tài)： 265 301 751 129 937 863 742 694 076 438建立初始堆： 937 694 863 265 438 751 742 129 075 301第一次排序

49、重建堆：863 694 751 765 438 301 742 129 075 937第二次排序重建堆：751 694 742 265 438 301 075 129 863 937第三次排序重建堆：742 694 301 265 438 129 075 751 863 937第四次排序重建堆：694 438 301 265 075 129 742 751 863 937第五次排序重建堆：438 265 301 129 075 694 742 751 863 937第六次排序重建堆：301 265 075 129 438 694 742 751 863 937第七次排序重建堆：265 129

50、075 301 438 694 742 751 863 937第八次排序重建堆：129 075265 301 438 694 742 751 863 937第九次排序重建堆： 075 129 265 301 438 694 742 751 863 937(8)基數(shù)排序基數(shù)排序(方括號(hào)內(nèi)表示一個(gè)箱子共有方括號(hào)內(nèi)表示一個(gè)箱子共有10個(gè)箱子，箱號(hào)從個(gè)箱子，箱號(hào)從0到到9)初始態(tài)：265 301 751 129 937 863 742 694 076 438第一趟： 301 751 742 863 694 265 076 937 438 129第二趟：301 129 937 438 742 751 8

51、63 265 076 694第三趟：075 129 265 301 438 694 742 751 863 937 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 472015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法若關(guān)鍵字是非負(fù)整數(shù)，則基數(shù)排序最快；若要求輔助空間為O(1)，則應(yīng)選堆排序；若要求排序是穩(wěn)定的，且關(guān)鍵字是實(shí)數(shù)，則應(yīng)選歸并排序，因?yàn)榛鶖?shù)排序不適用于實(shí)數(shù)，雖然它也是穩(wěn)定的。 此時(shí)Partion 返回值是low.此時(shí)快速排序的運(yùn)行時(shí)間是： (high-low)(high-low-1)/2=O(high-low)2)， 可以修改Partion ，將其中RecType pivot=Ri;

52、句改為： RecType pivot=R(j+i)/2； 也就是取中間的關(guān)鍵字為基準(zhǔn)，這樣就能使劃分的結(jié)果是平衡的。3、若關(guān)鍵字是非負(fù)整數(shù)，快速排序、歸并、堆和基數(shù)排序哪一個(gè)最快? 若要求輔助空間為O(1)，則應(yīng)選擇誰(shuí) ? 若要求排序是穩(wěn)定的，且關(guān)鍵字是實(shí)數(shù)，則應(yīng)選擇誰(shuí) ?2、當(dāng)Rlow.high中的關(guān)鍵字均相同時(shí)，Partion返回值是什么? 此時(shí)快速排序的的運(yùn)行時(shí)間是多少? 能否修改Partion,使得劃分結(jié)果是 平衡的(即劃分后左右區(qū)間的長(zhǎng)度大致相等)? 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 482015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法堆的性質(zhì)是： 任一非葉結(jié)點(diǎn)上的關(guān)鍵

53、字均不大于(或不小于)其孩子結(jié)點(diǎn)上的關(guān)鍵字。 據(jù)此我們可以通過(guò)畫(huà)二叉樹(shù)來(lái)進(jìn)行判斷和調(diào)整：(1) 此序列不是堆，經(jīng)調(diào)整后成為大頂堆： (100, 80, 73, 66, 39, 42, 57, 35, 21)(2) 此序列不是堆，經(jīng)調(diào)整后成為小頂堆：(12, 24, 33, 65, 33, 56, 48, 92, 86, 70)(3) 此序列是一大頂堆。(4) 此序列不是堆，經(jīng)調(diào)整后成為小頂堆：(05, 23, 20, 56, 28, 38, 29, 61, 35, 76, 100)4、判別下列序列是否為堆(小頂堆或大頂堆)，若不是，則將其調(diào)整為堆：(1) (100,86,73,35,39,42

54、,57,66,21)(2) (12,70,33,65,24,56,48,92,86,33)(3) (103,97,56,38,66,23,42,12,30,52,06,20)(4) (05,56,20,23,40,38,29,61,35,76,28,100)第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 492015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法5、有序數(shù)組是堆嗎?這四種排序算法中，直接選擇、快速排序均是不穩(wěn)定的，因此先予以排除，剩下兩種算法中，由于直接插入算法所費(fèi)時(shí)間比冒泡法更少，因此選擇直接插入排序算法為宜。有序數(shù)組是堆。因?yàn)橛行驍?shù)組中的關(guān)鍵字序列滿(mǎn)足堆的性質(zhì)。若數(shù)組為降序，則此

55、堆為大頂堆，反之為小頂堆。6、若文件初態(tài)是反序的，且要求穩(wěn)定排序，則在直接插入、直接選擇、 冒泡排序和快速排序中選哪則種方法為宜? 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 502015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)選直接選擇排序?yàn)楦?。分析如下?1)在直接插入排序算法中，反序輸入時(shí)是最壞情況，此時(shí)： 關(guān)鍵字的比較次數(shù)：Cmax=(n+2)(n-2)/2 記錄移動(dòng)次數(shù)為： Mmax=(n-1)(n+4)/2 Tmax=n2-4n-3 (以上二者相加) (2)在冒泡排序算法中，反序也是最壞情況，此時(shí)： Cmax=n(n-1)/2 Mmax=3n(n-1)/2 Tmax=2n2

56、-2n (3)在選擇排序算法中， Cmax=n(n-1)/2 Mmax=3(n-1) Tmax=n2/2-5n/2-3 雖然它們的時(shí)間復(fù)雜度都是O(n2),但是選擇排序的常數(shù)因子為1/2， 因此選擇排序最省時(shí)間。7、若文件初態(tài)是反序的，則直接插入，直接選擇和冒泡排序哪一個(gè)更好? 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 512015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法重寫(xiě)的算法如下： void InsertSort(SeqList R) /對(duì)順序表中記錄R0.n-1按遞增序進(jìn)行插入排序 int i,j; for(i=n-2;i=0;i-) /在有序區(qū)中依次插入Rn-2.R0if(Ri

57、.keyRi+1.key) /若不是這樣則Ri原位不動(dòng) Rn=Ri;j=i+1; /Rn是哨兵do /從左向右在有序區(qū)中查找插入位置Rj-1=Rj; /將關(guān)鍵字小于Ri.key的記錄向右移j+;while(Rj.keyRn.key); Rj-1=Rn; /將Ri插入到正確位置上 /endif 8、將哨兵放在Rn中，被排序的記錄放在R0.n-1中，重寫(xiě)直接插入排序算法。第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 522015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法int QuickSort ( SeqList R, int j, int low, int high) /對(duì)Rlow.high快

58、速排序int pivotpos； /劃分后的基準(zhǔn)記錄的位置if (low j) return (R, j, low, pivotpos-1);else return quicksort (R, j, pivotpos+1, high); /Endif /QuickSort9、對(duì)給定的j(1jn ),要求在無(wú)序的記錄區(qū)R1.n中找到按關(guān)鍵字自小 到大排在第 j 個(gè)位置上的記錄(即在無(wú)序集合中找到第j個(gè)最小元)，試 利用快速排序的劃分思想編寫(xiě)算法實(shí)現(xiàn)上述的查找操作。 第第6 6章章 內(nèi)部分類(lèi)內(nèi)部分類(lèi) Slide. 6 - 532015秋秋數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法10、設(shè)向量 A0.n-1中存有

59、 n 個(gè)互不相同的整數(shù)，且每個(gè)元素的值均在 0 到 n-1之間。試寫(xiě)一時(shí)間為O(n)的算法將向量A排序，結(jié)果可輸出 到另一個(gè)向量 B0.n-1 中。Sort ( int *A , int *B ) /將向量A排序后送入B向量中 int i; for(i=0;i=n-1;i+)BAi=Ai;Sort ( int *A ) int i; for(i=0;ilength+；R-dataR-length.key=key; /插入新的記錄for(i=R-length/2;i0;i-) /建堆 low=i;high=R-length;R-data0.key=R-datalow.key; /R-datalow是當(dāng)前調(diào)整的結(jié)點(diǎn)for(large=2*low;largehigh，則表示R-datalow是葉子，調(diào)整結(jié)束；否則large指向R-datalow的左孩子 if(largedatal