數(shù)據(jù)結(jié)構(gòu)課程講義8ppt課件

1、 排序的方法有很多，但簡單地判別那一種算排序的方法有很多，但簡單地判別那一種算 法最好，以便可以普遍選用那么是困難的。法最好，以便可以普遍選用那么是困難的。 評價(jià)排序算法好壞的規(guī)范主要有兩條：算法評價(jià)排序算法好壞的規(guī)范主要有兩條：算法 執(zhí)行所需求的時(shí)間和所需求的附加空間。執(zhí)行所需求的時(shí)間和所需求的附加空間。 另外，算法本身的復(fù)雜程度也是需求思索另外，算法本身的復(fù)雜程度也是需求思索 的一個(gè)要素。的一個(gè)要素。 排序算法所需求的附加空間普通都不大，矛排序算法所需求的附加空間普通都不大，矛 盾并不突出。而排序是一種經(jīng)常執(zhí)行的一盾并不突出。而排序是一種經(jīng)常執(zhí)行的一 種運(yùn)算，往往屬于系統(tǒng)的中心部分，因此種

2、運(yùn)算，往往屬于系統(tǒng)的中心部分，因此 排序的時(shí)間開銷是算法好壞的最重要的標(biāo)排序的時(shí)間開銷是算法好壞的最重要的標(biāo) 志。志。 為簡單起見，數(shù)據(jù)的存儲構(gòu)造采用記為簡單起見，數(shù)據(jù)的存儲構(gòu)造采用記錄數(shù)組方式。記錄數(shù)組的類型闡明如下：錄數(shù)組方式。記錄數(shù)組的類型闡明如下：其中其中n為記錄總數(shù)加為記錄總數(shù)加1算法中引入附加記錄算法中引入附加記錄temp的作用：是進(jìn)入的作用：是進(jìn)入查找循環(huán)之前，它保管了查找循環(huán)之前，它保管了Ri的副本，使得的副本，使得不至于因記錄的后移而喪失不至于因記錄的后移而喪失Ri中的內(nèi)容。中的內(nèi)容。算法分析算法分析nininOnninOnni2222)(2/ )4)(1()21()(2/

3、) 1)(2(移動次數(shù)的最大值比較次數(shù)的最大值希爾排序的根本過程希爾排序的根本過程希爾排序算法希爾排序算法rectype Rn+d1;rectype Rn+d1;int dt;int dt; SHELLSORT(rectype SHELLSORT(rectype R,int d)R,int d) int i,j,k,h; int i,j,k,h; rectype temp; rectype temp; k k0;0; dl=1; dl=1; do do h hdk;dk; for for (i=h+dl;in+dl;i+)(i=h+dl;in+dl;i+) temp tempRi;Ri; j

4、ji-h;i-h; while while (temp.keyRj.key)(temp.keyRj.key) pj+h pj+hRj;Rj; j jj-h;j-h; Rj+h Rj+htemp;temp; k+; k+; while(h!=1); while(h!=1); 為什么為什么shellshell排序的時(shí)間性能優(yōu)于直接插入排排序的時(shí)間性能優(yōu)于直接插入排序呢？由于直接插入排序在初態(tài)為正序時(shí)所需時(shí)間序呢？由于直接插入排序在初態(tài)為正序時(shí)所需時(shí)間最少，實(shí)踐上，初態(tài)為根本有序時(shí)直接插入排序所最少，實(shí)踐上，初態(tài)為根本有序時(shí)直接插入排序所需的比較和挪動次數(shù)均較少。另一方面，當(dāng)需的比較和挪動次數(shù)均較少

5、。另一方面，當(dāng)n n值較值較小時(shí)，小時(shí)，n n和和n2n2的差別也較小，即直接插入排序的最的差別也較小，即直接插入排序的最好時(shí)間復(fù)雜度好時(shí)間復(fù)雜度O(n)O(n)和最壞時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度O(n2)O(n2)差別不差別不大。在大。在shellshell排序開場時(shí)增量較大，分組較多，每排序開場時(shí)增量較大，分組較多，每組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增組的記錄數(shù)目少，故各組內(nèi)直接插入較快，后來增量逐漸減少，分組數(shù)逐漸減少，而各組的記錄數(shù)目量逐漸減少，分組數(shù)逐漸減少，而各組的記錄數(shù)目逐漸增多，但組內(nèi)元素曾經(jīng)過多次排序，數(shù)組曾經(jīng)逐漸增多，但組內(nèi)元素曾經(jīng)過多次排序，數(shù)組曾經(jīng)比較接近有序形

6、狀，所以新的一趟排序過程也較塊。比較接近有序形狀，所以新的一趟排序過程也較塊。 首先依序比較首先依序比較n個(gè)待排序記錄的一端開場，個(gè)待排序記錄的一端開場，依次兩兩比較排序碼，只需是逆序，那么交依次兩兩比較排序碼，只需是逆序，那么交換，這樣完成一趟交換排序，結(jié)果就是將最換，這樣完成一趟交換排序，結(jié)果就是將最大或最小的記錄交換到最后面或最前大或最小的記錄交換到最后面或最前面；面； 然后其他的記錄同法進(jìn)展兩兩比較，每一趟然后其他的記錄同法進(jìn)展兩兩比較，每一趟都將較大小元素交換到最后前面，都將較大小元素交換到最后前面，不斷進(jìn)展下去，直到最后一個(gè)記錄排完或沒不斷進(jìn)展下去，直到最后一個(gè)記錄排完或沒有要交換

7、的元素的時(shí)候?yàn)橹?。有要交換的元素的時(shí)候?yàn)橹埂?首先從首先從R0到到Rn-1對對n個(gè)元素比較其排序碼，個(gè)元素比較其排序碼，對逆序元素進(jìn)展交換，完成一趟排序時(shí)，將對逆序元素進(jìn)展交換，完成一趟排序時(shí)，將排序碼值最到的元素幾交換到最后一個(gè)位置，排序碼值最到的元素幾交換到最后一個(gè)位置，即即Rn-1，該過程相當(dāng)于一趟冒泡；，該過程相當(dāng)于一趟冒泡； 然后，又從然后，又從R0到到Rn-2中又進(jìn)展一趟交換中又進(jìn)展一趟交換冒泡，這樣不斷進(jìn)展下去，直到最后一個(gè)元冒泡，這樣不斷進(jìn)展下去，直到最后一個(gè)元素素R0或某一趟沒有交換元素為止。或某一趟沒有交換元素為止。 冒泡排序算法冒泡排序算法void bubblesort(

8、R)void bubblesort(R) for(i=0;in-2;i+) for(i=0;i=i;j+) for(j=n-1;j=i;j+) if (Rj+1.keyRj.key) if (Rj+1.key= temp.key)&(i= temp.key)&(ij) j-; if (ij) Ri+=Rj; if (ij) Ri+=Rj; while (Ri.key=temp.key)&(ij) i+; while (Ri.key=temp.key)&(ij) i+; if (ij) Rj-=Ri; if (ij) Rj-=Ri; while (i!=j); while (i!=j); Ri=

9、temp; Ri=temp; return i; return i; QUICKSORT(rectype R,int s1,int t1)QUICKSORT(rectype R,int s1,int t1) int i; int i; if (s1t1) if (s1t1) i=PARTITION(R,s1,t1); i=PARTITION(R,s1,t1); QUICKSORT(R,s1,i-1); QUICKSORT(R,s1,i-1); QUICKSORT(R,i+1,t1); QUICKSORT(R,i+1,t1); 112)(2/ ) 1()(ninOnnin比較次數(shù)的最大值n)O(

10、nlognC(1)nnlog)C(n/22kn.)8C(n/23n)2C(n/24n/42n)4C(n/22n)2C(n/22n/2n2C(n/2)nC(n)22kk3322兩種常見的選擇排序兩種常見的選擇排序 直接選擇排序直接選擇排序 堆排序堆排序根本原理根本原理: 將待排序的結(jié)點(diǎn)分為已排序?qū)⒋判虻慕Y(jié)點(diǎn)分為已排序(初初始為空始為空)和為未排序兩組，依次將未排序的和為未排序兩組，依次將未排序的結(jié)點(diǎn)中值最小的結(jié)點(diǎn)插入已排序的組中。結(jié)點(diǎn)中值最小的結(jié)點(diǎn)插入已排序的組中。49386597761327491338659776492749132765977649384913273897764965491

11、327384976976549132738494997657613273849496597761327384949657697直接選擇排序算法直接選擇排序算法SELECTSORT(rectype R)SELECTSORT(rectype R) int i,j,k; int i,j,k; rectype temp; rectype temp; for (i=0;in-1;i+) for (i=0;in-1;i+) k=i; k=i; for (j=i+1;jn;j+) for (j=i+1;jn;j+) if (Rj.keyRk.key) k=j; if (Rj.key= low(n/2)i =

12、 low(n/2)的結(jié)的結(jié)點(diǎn)都是葉子，因此以這些結(jié)點(diǎn)為根的子點(diǎn)都是葉子，因此以這些結(jié)點(diǎn)為根的子樹都已是堆。這樣，我們只需依次將序樹都已是堆。這樣，我們只需依次將序號為號為low(n/2)low(n/2)，low(n/2)-1low(n/2)-1，.，1 1的的結(jié)點(diǎn)作為根的子樹都調(diào)整為堆即可。結(jié)點(diǎn)作為根的子樹都調(diào)整為堆即可。 我們以大根堆為例進(jìn)展闡明我們以大根堆為例進(jìn)展闡明 假設(shè)知結(jié)點(diǎn)假設(shè)知結(jié)點(diǎn)RiRi的左右子樹已是堆，如何將以的左右子樹已是堆，如何將以RiRi為根的完全為根的完全二叉樹也調(diào)整為堆？二叉樹也調(diào)整為堆？ 處理這一問題可采用處理這一問題可采用“挑選法，其根本思想是：由于挑選法，其根本

13、思想是：由于RiRi的的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點(diǎn)，所以我們必需在結(jié)點(diǎn)，所以我們必需在RiRi和它的左右孩子中選取關(guān)鍵字最大的結(jié)和它的左右孩子中選取關(guān)鍵字最大的結(jié)點(diǎn)放到點(diǎn)放到RiRi的位置上。假設(shè)的位置上。假設(shè)RiRi的關(guān)鍵字已是三者中的最大者，那的關(guān)鍵字已是三者中的最大者，那么無須做任何調(diào)整，以么無須做任何調(diào)整，以RiRi為根的子樹已構(gòu)成堆，否那么必需將為根的子樹已構(gòu)成堆，否那么必需將RiRi和具有最大關(guān)鍵字的左孩子和具有最大關(guān)鍵字的左孩子R2iR2i或右孩子或右孩子R2i+1R2i+1進(jìn)展交換。進(jìn)

14、展交換。假定假定R2iR2i的關(guān)鍵字最大，將的關(guān)鍵字最大，將RiRi和和R2iR2i交換位置，交換之后有能交換位置，交換之后有能夠?qū)е聣驅(qū)е翿2iR2i為根的子樹不再是堆，但由于為根的子樹不再是堆，但由于R2iR2i的左右子樹依然是的左右子樹依然是堆，于是可以反復(fù)上述過程，將以堆，于是可以反復(fù)上述過程，將以R2iR2i為根的子樹調(diào)整為堆，為根的子樹調(diào)整為堆，.，如此逐層遞推下去，最多能夠調(diào)整到樹葉。如此逐層遞推下去，最多能夠調(diào)整到樹葉。例子：關(guān)鍵字序列為例子：關(guān)鍵字序列為 42，13，91，23， 24， 16，05，88，n=8，故從第四個(gè)結(jié)點(diǎn)開場調(diào)，故從第四個(gè)結(jié)點(diǎn)開場調(diào)整整42421313

15、9191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不調(diào)整不調(diào)整424213139191888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆挑選算法挑選算法SIFT(rectype R,int i;int m)SIFT(rectype R,int

16、i;int m) int j; int j; rectype temp; rectype temp; temp=Ri; temp=Ri; j=2 j=2* *i;i; while (j=m) while (j=m) if (jm)&(Rj.keyRj+1.key) j+; if (jm)&(Rj.keyRj+1.key) j+; if (temp.keyRj.key) if (temp.key=1; i-) SIFT(R, i, n) 由于建堆的結(jié)果把關(guān)鍵字最大的記錄選到了堆由于建堆的結(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈恢?，而排序的結(jié)果應(yīng)是升序，所以，應(yīng)該頂?shù)奈恢?，而排序的結(jié)果應(yīng)是升序，所以，

17、應(yīng)該將將R1和和Rn交換，這就得到了第一趟排序的結(jié)果。交換，這就得到了第一趟排序的結(jié)果。 第二趟排序的操作首先是將無序區(qū)第二趟排序的操作首先是將無序區(qū)R1到到Rn-1調(diào)整為堆。這時(shí)對于當(dāng)前堆來說，它的左右子樹調(diào)整為堆。這時(shí)對于當(dāng)前堆來說，它的左右子樹依然是堆，所以，可以調(diào)用依然是堆，所以，可以調(diào)用SIFT函數(shù)將函數(shù)將R1到到Rn-1調(diào)整為大根堆，選出最大關(guān)鍵字放入堆頂，調(diào)整為大根堆，選出最大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的最后一個(gè)記錄然后將堆頂與當(dāng)前無序區(qū)的最后一個(gè)記錄Rn-1交交換，如此反復(fù)進(jìn)展下去。換，如此反復(fù)進(jìn)展下去。9191888842422323242416160505131

18、39188422324160513a a初始堆初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591b b第一趟排序之后第一趟排序之后c c重建的堆重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591050524244242232313131616888891910524422313168891d d第二趟排序之后第二趟排序之后e e重建的堆重建的堆R1R1到到R6R642422424161623231313050588889191422416231305

19、8891f f第三趟排序之后第三趟排序之后050524241616232313134242888891910524162313428891g g重建的堆重建的堆R1R1到到R5R5242423231616050513134242888891912423160513428891h h第四趟排序之后第四趟排序之后131323231616050524244242888891911323160524428891i i重建的堆重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891j j第五趟排序之后第五趟排序之后05051313161

20、6232324244242888891910513162324428891k k重建的堆重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891l l第六趟排序之后第六趟排序之后050513131616232324244242888891910513162324428891m m重建的堆重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891n n第七趟排序之后第七趟排序之后0505131316162323242442428888919105131623244

21、28891堆排序算法堆排序算法HEAPSORT(rectype R)HEAPSORT(rectype R) int i; int i; rectype temp; rectype temp; for (i=n/2;i=1;i-) for (i=n/2;i=1;i-) SIFT(R,i,n); SIFT(R,i,n); for (i=n;i=1;i-) for (i=n;i=1;i-) temp=R1; R1=Ri; temp=R1; R1=Ri; Ri=temp; Ri=temp; SIFT(R,1,i-1); SIFT(R,1,i-1); 歸并排序是利用歸并排序是利用“歸并技術(shù)來進(jìn)展排序，所

22、歸并技術(shù)來進(jìn)展排序，所謂歸并是指將假設(shè)干個(gè)曾經(jīng)排序的子序列合并謂歸并是指將假設(shè)干個(gè)曾經(jīng)排序的子序列合并為一個(gè)有序序列。其算法比較簡單，可以直接為一個(gè)有序序列。其算法比較簡單，可以直接給出。給出。25 57 48 37 12 92 86 25 57 37 48 92 12 86 25 37 48 57 12 86 92 12 25 37 48 57 86 92 歸并算法歸并算法void merge(R,R1,low,mid,hign)void merge(R,R1,low,mid,hign)/Rlow/Rlow到到RmidRmid與與Rmid+1Rmid+1到到RhighRhigh是兩個(gè)有序是兩

23、個(gè)有序序列，結(jié)果是合并為一個(gè)有序序列序列，結(jié)果是合并為一個(gè)有序序列R1lowR1low到到R1high/ R1high/ i=low;j=mid+1;k=low; i=low;j=mid+1;k=low; while(i=mid&j=high) while(i=mid&j=high) if(Ri.key=Rj.key) if(Ri.key=Rj.key) R1k+=Ri+; R1k+=Ri+; else R1k+=Rj+; else R1k+=Rj+; while(i=mid ) R1k+=Ri+; while(i=mid ) R1k+=Ri+; while(j=high) R1k+=Rj+;

24、 while(j=high) R1k+=Rj+; 歸并排序就是利用上述歸并操作實(shí)歸并排序就是利用上述歸并操作實(shí)現(xiàn)排序的。其根本思想是：將待排序列現(xiàn)排序的。其根本思想是：將待排序列R0R0到到Rn-1Rn-1看成看成n n個(gè)長度為個(gè)長度為1 1的有序子的有序子序列，把這些子序列兩兩歸并，便得到序列，把這些子序列兩兩歸并，便得到high(n/2)high(n/2)個(gè)有序的子序列。然后再把個(gè)有序的子序列。然后再把這這high(n/2)high(n/2)個(gè)有序的子序列兩兩歸并，個(gè)有序的子序列兩兩歸并，如此反復(fù)，直到最后得到一個(gè)長度為如此反復(fù)，直到最后得到一個(gè)長度為n n的有序序列。上述每次的歸并操作，

25、都的有序序列。上述每次的歸并操作，都是將兩個(gè)子序列歸并為一個(gè)子序列，這是將兩個(gè)子序列歸并為一個(gè)子序列，這就是就是“二路歸并，類似地還可以有二路歸并，類似地還可以有“三三路歸并或路歸并或“多路歸并。多路歸并。歸并過程例如歸并過程例如(25) (57) (48) (37) (12) (92) (86)(25 57) (37 48) (12 92) (86)(25 37 48 57) (12 86 92)(12 25 37 48 57 86 92)一趟歸并算法一趟歸并算法歸并排序就是利用上述歸并操作實(shí)現(xiàn)排序的。歸并排序就是利用上述歸并操作實(shí)現(xiàn)排序的。 其根本思想是：其根本思想是： 將待排序的記錄序列

26、將待排序的記錄序列R0R0到到Rn-1Rn-1看成為看成為n n個(gè)長度為個(gè)長度為1 1的有序序列，將其進(jìn)展兩兩歸并，那么得的有序序列，將其進(jìn)展兩兩歸并，那么得到到n/2n/2個(gè)個(gè)n n為基數(shù)時(shí)候那么為為基數(shù)時(shí)候那么為 n+1n+1/2/2個(gè)個(gè)長度為長度為2 2的有序序列，然后繼續(xù)進(jìn)展，直到最后得到的有序序列，然后繼續(xù)進(jìn)展，直到最后得到一個(gè)長度為一個(gè)長度為n n的有序序列為止。這就是的有序序列為止。這就是2-2-路歸并排序。路歸并排序。 其中，最關(guān)鍵的是將兩個(gè)長度為其中，最關(guān)鍵的是將兩個(gè)長度為l l的有序序的有序序列歸并為長度為列歸并為長度為2l2l的有序序列。的有序序列。一趟歸并算法一趟歸并算

27、法MERGEPASS(rectype R,rectype R1,int MERGEPASS(rectype R,rectype R1,int length)length) int i,j; int i,j; i=0; i=0; while (i+2 while (i+2* *length-1n)length-1n) MERGE(R,R1,i,i+length-1,i+2 MERGE(R,R1,i,i+length-1,i+2* *length-1);length-1); i=i+2 i=i+2* *length;length; if (i+length-1n-1) if (i+length-1

28、n-1) MERGE(R,R1,i,i+length-1,n-1); MERGE(R,R1,i,i+length-1,n-1); else else for (j=i;jn;j+) R1j=Rj; for (j=i;jn;j+) R1j=Rj; 在上述一趟歸并過程中，假設(shè)正好配在上述一趟歸并過程中，假設(shè)正好配成對時(shí)候，即可正常完成，否那么最后一成對時(shí)候，即可正常完成，否那么最后一次歸并時(shí)，能夠有兩種情況：次歸并時(shí)，能夠有兩種情況： 1(2k+1)*lenn2(k+1)*len 表示有兩個(gè)有序序列，但后一個(gè)長度缺表示有兩個(gè)有序序列，但后一個(gè)長度缺乏乏len，此時(shí)歸并方法與前一樣，僅僅是參，此時(shí)歸

29、并方法與前一樣，僅僅是參數(shù)不同而已。數(shù)不同而已。 22k*lenn2(k+1)*len 表示只需一個(gè)有序序列，此時(shí)曾經(jīng)是有表示只需一個(gè)有序序列，此時(shí)曾經(jīng)是有序的，故只需求復(fù)制到序的，故只需求復(fù)制到R1中即可。中即可。歸并排序算法歸并排序算法MERGESORT(rectype R)MERGESORT(rectype R) int length=1; int length=1; while (lengthn) while (lengthn) MERGEPASS(R,R1,length); MERGEPASS(R,R1,length); length=2 length=2* *length;leng

30、th; MERGEPASS(R1,R,length); MERGEPASS(R1,R,length); length=2 length=2* *length;length; 1792083069385998455927133B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.

31、e B8.e B9.e 27193339845530620817985992719333984553062081798599B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 33984306208955859271179933062089335585

32、927117998493B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 17930698485993355932082719335593179208271306859984分配排序算法分配排序算法typedef structtypedef struct int keyd; int keyd; int next; int next