天津科技大學(xué)數(shù)據(jù)結(jié)構(gòu)排序

1、天津科技大學(xué)數(shù)據(jù)結(jié)構(gòu)排序計算機內(nèi)經(jīng)常進(jìn)行的一種操作，計算機內(nèi)經(jīng)常進(jìn)行的一種操作，。例如：將下列關(guān)鍵字序列例如：將下列關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75調(diào)整為調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97一般，假設(shè)含一般，假設(shè)含n個記錄的序列為個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互間可以進(jìn)行比較，即它們之間存在一個關(guān)系這些關(guān)鍵字相互間可以進(jìn)行比較，即它們之間存在一個關(guān)系Kp1Kp2Kpn按此固有關(guān)系將原記錄序列重新排列為按此固

2、有關(guān)系將原記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作的操作稱作?！氨容^”的次數(shù)：1*(n-1)=n-1“移動”的次數(shù)：0“比較”的次數(shù) “移動”的次數(shù)直接插入排序所需進(jìn)行關(guān)鍵字間的比較次數(shù)和記錄移動的次數(shù)均為n2/4，所以直接插入排序的時間復(fù)雜度為O(n2)。由于R1.i-1是一個按關(guān)鍵字有序的有序序列，則可，如此實現(xiàn)的插入排序為折半插入排序。 ，改變記錄的存儲結(jié)構(gòu)，利用改變記錄的存儲結(jié)構(gòu)，利用進(jìn)行排序，并在排序進(jìn)行排序，并在排序完成后，一次性地調(diào)整各個記錄相互之間的位置，從而實完成后，一次性地調(diào)整各個記錄相互之間的位置，從而實現(xiàn)排序?，F(xiàn)排序。例如：例如：下標(biāo)下標(biāo)012345

3、678關(guān)鍵字關(guān)鍵字MAXINT49 38 65 97 76 13 27 49*初值初值10-i=2201-i=32310-i=423140-i=5231504-i=66315042-i=763150472-終值終值681504723ipq01234567816a2-7MAXINT49386597762749*6815042327a3-2MAXINT386597764949*61504833(2),7a4-1MAXINT6597764949*6504834(1),6a5-8MAXINT97766549*6045358a6-3MAXINT7697656405例如：void ShellInsert(

4、SqList &L,int dk)/對順序表對順序表L做一趟希爾插入排序。本算法是和一趟直接插入排序相比，作了以下修改：做一趟希爾插入排序。本算法是和一趟直接插入排序相比，作了以下修改：1. 前前后記錄的增量是后記錄的增量是dk，而不是，而不是1; 2. 0號單元只是暫存單元，不是哨兵。當(dāng)號單元只是暫存單元，不是哨兵。當(dāng)j=0時，插入位置已時，插入位置已找到找到 int i,j; for(i=dk+1; i L.elemi) L.elem0=L.elemi; for(j=i-dk; j0 & L.elem0= temp.key)&(ij) j-; if (ij) Ri+

5、=Rj; while (Ri.key=temp.key)&(ij) i+; if (ij) Rj-=Ri; while (i!=j); Ri=temp; return i; QUICKSORT(rectype R,int s1,int t1) int i; if (s1t1) i=PARTITION(R,s1,t1); QUICKSORT(R,s1,i-1); QUICKSORT(R,i+1,t1); 設(shè)設(shè)C(n)表示對長度為表示對長度為n的序列進(jìn)行快速排序所需的比較次的序列進(jìn)行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對長度為數(shù)，顯然，它應(yīng)該等于對長度為n的無序區(qū)進(jìn)行劃分所需的比的無序

6、區(qū)進(jìn)行劃分所需的比較次數(shù)較次數(shù)n-1，加上遞歸地對劃分所得的左右兩個無序子區(qū)進(jìn)行，加上遞歸地對劃分所得的左右兩個無序子區(qū)進(jìn)行快速排序所需的比較次數(shù)。假設(shè)文件長度快速排序所需的比較次數(shù)。假設(shè)文件長度n=2k ，k=log2n，因此有：因此有：基本原理將待排序的結(jié)點分為已排序基本原理將待排序的結(jié)點分為已排序(初始為空初始為空)和為未排序和為未排序兩組，依次將未排序的結(jié)點中值最小的結(jié)點插入已排序的組中。兩組，依次將未排序的結(jié)點中值最小的結(jié)點插入已排序的組中。493865977613274913386597764927491327659776493849132738977649654913273849

7、76976549132738494997657613273849496597761327384949657697直接選擇排序算法直接選擇排序算法SELECTSORT(rectype R) int i,j,k; rectype temp; for (i=0;in-1;i+) k=i; for (j=i+1;jn;j+) if (Rj.key low(n/2)的結(jié)點都是葉子，因此，以這些結(jié)點為根的子樹的結(jié)點都是葉子，因此，以這些結(jié)點為根的子樹都已是堆。都已是堆。即只需依次將序號為即只需依次將序號為low(n/2)，low(n/2)-1，.，1的結(jié)點作的結(jié)點作為根的子樹都調(diào)整為堆即可。為根的子樹都調(diào)

8、整為堆即可。以以為例進(jìn)行說明為例進(jìn)行說明因為因為Ri的左右子樹已是堆，這兩棵的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點，所以在子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點，所以在Ri和它的左右孩子中選取關(guān)鍵字最大的結(jié)點放到和它的左右孩子中選取關(guān)鍵字最大的結(jié)點放到Ri的位置上。的位置上。若若Ri的關(guān)鍵字已是三者中的最大者，則無須做任何的關(guān)鍵字已是三者中的最大者，則無須做任何調(diào)整，以調(diào)整，以Ri為根的子樹已構(gòu)成堆，為根的子樹已構(gòu)成堆，否則，將否則，將Ri和具有最大關(guān)鍵字的左孩子和具有最大關(guān)鍵字的左孩子R2i或右或右孩子孩子R2i+1進(jìn)行交換。進(jìn)行交換。假定假定R2i的關(guān)鍵字最大，

9、將的關(guān)鍵字最大，將Ri和和R2i交換位置，交換位置，交換之后有可能導(dǎo)致交換之后有可能導(dǎo)致R2i為根的子樹不再是堆，但由于為根的子樹不再是堆，但由于R2i的左右子樹仍然是堆，于是可以重復(fù)上述過程，將的左右子樹仍然是堆，于是可以重復(fù)上述過程，將以以R2i為根的子樹調(diào)整為堆，為根的子樹調(diào)整為堆，.，如此逐層遞推下去，如此逐層遞推下去，最多可能調(diào)整到樹葉。最多可能調(diào)整到樹葉。例子：關(guān)鍵字序列為例子：關(guān)鍵字序列為 42，13，91，23， 24， 16，05，88，n=8，故從第四個結(jié)點開始調(diào)整，故從第四個結(jié)點開始調(diào)整4242131391912323242416160505888842139123241

10、60588424213139191888824241616050523234213918824160523不調(diào)整不調(diào)整424213139191888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆篩選算法篩選算法SIFT(rectype R,int i;int m) int j; rectype temp; temp=Ri; j=2*i; while (j=m) if (

11、jm)&(Rj.keyRj+1.key) j+; if (temp.key=1; i-) SIFT(R, i, n)由于建堆的結(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈挥捎诮ǘ训慕Y(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈恢茫判虻慕Y(jié)果應(yīng)是升序，所以，應(yīng)該將置，而排序的結(jié)果應(yīng)是升序，所以，應(yīng)該將R1和和Rn交交換，這就得到了第一趟排序的結(jié)果。換，這就得到了第一趟排序的結(jié)果。 第二趟排序的操作首先是將無序區(qū)第二趟排序的操作首先是將無序區(qū)R1到到Rn-1調(diào)整為調(diào)整為堆。這時對于當(dāng)前堆來說，它的左右子樹仍然是堆，所以，堆。這時對于當(dāng)前堆來說，它的左右子樹仍然是堆，所以，可以調(diào)用可以調(diào)用SIFT函數(shù)將函數(shù)

12、將R1到到Rn-1調(diào)整為大根堆，選出最調(diào)整為大根堆，選出最大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的最后一個大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的最后一個記錄記錄Rn-1交換，如此反復(fù)進(jìn)行下去。交換，如此反復(fù)進(jìn)行下去。919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后（c c）重建的堆）重建的堆R1R1到到R7R7888824244242232313131616050

13、591918824422313160591050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（g g）重建的堆）重建的堆R1R1到到R5R524242323161605051313424288889191242316051342889

14、1（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891（k k）重建的堆）重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891（l l）第六趟排序之后）第六趟排序之

15、后050513131616232324244242888891910513162324428891（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891堆排序算法堆排序算法HEAPSORT(rectype R) int i; rectype temp; for (i=n/2;i=1;i-) SIFT(R,i,n); for (i=n;i=1;i-) temp=R1; R1

16、=Ri; Ri=temp; SIFT(R,1,i-1); 歸并過程示例歸并過程示例(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)一趟歸并算法一趟歸并算法MERGEPASS(rectype R,rectype R1,int length) int i,j; i=0; while (i+2*length-1n) MERGE(R,R1,i,i+length-1,i+2*length-1); i=i+2*length; if (i+l

17、ength-1n-1) MERGE(R,R1,i,i+length-1,n-1); else for (j=i;jn;j+) R1j=Rj;歸并算法歸并算法MERGE(rectypr R,rectype R1,int low,int mid,int high) int i,j,k; i=low; j=mid+1; k=low; while (i=mid)&(j=high) if (Ri.key=Rj.key) R1k+=Ri+; else R1k+=Rj+; while (i=mid) R1k+=Ri+; while (j=high) R1k+=Rj+;歸并排序算法歸并排序算法MERGESORT(rectype R