數(shù)據(jù)結(jié)構(gòu)和排序分析

1、10.1 概述 排序計算機內(nèi)經(jīng)常進行的一種操作，將一組“無序”的記錄序列調(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一般，假設(shè)含n個記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互間可以進行比較，即它們之間存在一個關(guān)系Kp1Kp2Kpn按此固有關(guān)系將原記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。排序算法的穩(wěn)定性判斷標(biāo)準(zhǔn)：關(guān)鍵字相同的數(shù)據(jù)對象在排序過程中是否保持前

2、后次序不變。如 2, 2*,1，排序后若為1, 2*, 2 ，則該排序方法是不穩(wěn)定的。內(nèi)部排序和外部排序 若整個排序過程不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排序；若參加排序的記錄數(shù)量很大，整個序列的排序過程不可能在內(nèi)存中完成，則稱此類排序問題為外部排序。內(nèi)部排序的方法 內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。在排序的過程中，參與排序的記錄序列中存在兩個區(qū)域：有序區(qū)和無序區(qū)。有序序列區(qū)無序序列區(qū)使有序區(qū)中記錄的數(shù)目增加一個或幾個的操作稱為一趟排序。逐步擴大記錄有序序列長度的方法大致有下列幾類：插入類將無序序列中的一個或幾個記錄“插入”到有序序列中；交換類通過“交換”無序序

3、列中的記錄從而得到其中關(guān)鍵字最小或最大的記錄，并將它加到有序子序列中;選擇類從記錄的無序子序列中“選擇”關(guān)鍵字最小或最大的記錄，并將它加入到有序子序列中;歸并類通過“歸并”兩個或兩個以上的記錄有序序列;其它方法 10.2 插入排序 假設(shè)在排序過程中，記錄序列R1.n的狀態(tài)為：有序序列R1.i-1Ri無序序列Ri+1.n則一趟直接插入排序的基本思想：將記錄Ri插入到有序子序列R1.i-1中，使記錄的有序序列從R1.i-1變?yōu)镽1.i。完成一趟“插入”需分三步進行：1查找Ri的插入位置j+1；2將Rj+1.i-1中的記錄后移一個位置；3將Ri復(fù)制到Rj+1的位置上。一、直接插入排序利用順序查找實現(xiàn)

4、“在R1.i-1中查找Ri的插入位置”的插入排序。直接插入排序算法的三個要點： 1、從Ri-1起向前順序查找，監(jiān)視哨設(shè)置在R0；R0 = Ri; / 設(shè)置“哨兵”for (j=i-1; R0.keyRj.key; -j); / 從后往前找/循環(huán)結(jié)束后，可得Ri的插入位置j+12在查找過程中找到的關(guān)鍵字大于R0.key的記錄需在查找的同時向后移動；for (j=i-1; R0.keyRj.key; -j) Rj+1 = Rj;3i = 2，3，, n, 實現(xiàn)整個序列的排序。算法描述如下: void InsertionSort ( Elem R , int n) / 對記錄序列R1.n作直接插入排

5、序。for ( i=2; i=n; +i ) R0 = Ri; / 復(fù)制為監(jiān)視哨for ( j=i-1; R0.key Rj.key; -j )Rj+1 = Rj; / 記錄后移Rj+1 = R0; / 插入到正確位置 / InsertSort排序的時間分析： 實現(xiàn)排序的基本操作有兩個：（1）“比較”序列中兩個關(guān)鍵字的大?。唬?）“移動”記錄。對于直接插入排序：最好的情況(關(guān)鍵字在記錄序列中順序有序)：“比較”的次數(shù)：1*(n-1)=n-1“移動”的次數(shù)：0最壞的情況(關(guān)鍵字在記錄序列中逆序有序)：“比較”的次數(shù) “移動”的次數(shù)直接插入排序所需進行關(guān)鍵字間的比較次數(shù)和記錄移動的次數(shù)均為n2/4

6、，所以直接插入排序的時間復(fù)雜度為O(n2)。直接插入排序是一種穩(wěn)定的排序方法。原因：關(guān)鍵字相同的兩個對象，在整個排序過程中，不會通過比較而相互交換。二、折半插入排序由于R1.i-1是一個按關(guān)鍵字有序的有序序列，則可利用折半查找實現(xiàn)“在R1.i-1中查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。折半插入排序比直接插入排序明顯地減少了關(guān)鍵字間的“比較”次數(shù)，但記錄“移動”的次數(shù)不變。void BInsertionSort (Elem R ， int n) / 對記錄序列R1.n作折半插入排序。for ( i=2; i=L.length; +i ) R0 = Ri; / 將Ri暫存到R0l

7、ow = 1; high = i-1;while (low=high)/在Rlow.high中折半查找插入的位置m = (low+high)/2; / 折半if (R0.key =high+1; -j )Rj+1 = Rj; / 記錄后移Rhigh+1 = R0; / 插入 / BInsertSort三、表插入排序 為了減少在排序過程中進行的“移動”記錄的操作，改變記錄的存儲結(jié)構(gòu)，利用靜態(tài)鏈表進行排序，并在排序完成后，一次性地調(diào)整各個記錄相互之間的位置，從而實現(xiàn)排序。例如：下標(biāo)012345678關(guān)鍵字MAXINT4938659776132749*初值10-i=2201-i=32310-i=42

8、3140-i=5231504-i=66315042-i=763150472-終值681504723void LInsertionSort (Elem SL ， int n)/ 對記錄序列SL1.n作表插入排序。SL0.key = MAXINT ;SL0.next = 1; SL1.next = 0;for ( i=2; i頭結(jié)點，k - a1 while(SLk.key7MAXINT4938659776132749*68150472327a3-2MAXINT1338659776492749*6(6)15048233(2),7a4-1MAXINT1327659776493849*6(6)(7)5

9、048134(1),6a5-8MAXINT1327389776496549*6(6)(7)(7)0485358a6-3MAXINT1327384976976549*6(6)(7)(7)(6)40536(3),7a7-5MAXINT1327384949*9765766(6)(7)(7)(6)(8)0547(5),8a8-4MAXINT13273849526597766(6)(7)(7)(6)(8)(7)04(4),(7),8MAXINT13273849526576976(6)(7)(7)(6)(8)(7)(8)0void Arrange ( Elem SL , int n ) p = SL0.n

10、ext; /p=6for ( i=1; in; +i ) while (pi) p = SLp.next;q = SLp.next; if ( p!= i ) SLpSLi; SLi.next = p; p = q; / Arrange根據(jù)靜態(tài)鏈表SL中各結(jié)點的指針值調(diào)整記錄位置，使得SL中記錄按關(guān)鍵字非遞減有序順序排列算法中使用了三個指針:p指示第i個記錄的當(dāng)前位置；i指示第i個記錄應(yīng)在的位置；q指示第i+1個記錄的當(dāng)前位置 p指示第一個記錄的當(dāng)前位置 SL1.i-1中記錄已按關(guān)鍵字有序排列，第i個記錄在SL中的當(dāng)前位置應(yīng)不小于i找到第i個記錄，并用p指示其在SL中當(dāng)前位置 q指示尚未調(diào)整的

11、表尾交換記錄，使第i個記錄到位 指向被移走的記錄， 使得以后可由while循環(huán)找回 p指示尚未調(diào)整的表尾，為找第i+1個記錄作準(zhǔn)備四、希爾排序（又稱縮小增量排序）1959年由D.L. Shell提出?；舅枷雽Υ庞涗浶蛄邢茸鳌昂暧^”調(diào)整，再作“微觀”調(diào)整?！昂暧^”調(diào)整“跳躍式”的插入排序。將記錄序列分成若干個由不相鄰的記錄構(gòu)成的子序列，每個子序列分別進行插入排序。假設(shè)將n個記錄分成d個子序列，則這d個子序列分別為： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 其中，d稱為增量，它的值在排序過程中從大到小逐漸縮小

12、（如：d=d/2），直至最后一趟排序減為1。例如：void ShellInsert(SqList &L,int dk)/對順序表L做一趟希爾插入排序。本算法是和一趟直接插入排序相比，作了以下修改：1. 前后記錄的增量是dk，而不是1; 2. 0號單元只是暫存單元，不是哨兵。當(dāng)j=0時，插入位置已找到 int i,j; for(i=dk+1; i L.elemi)/需將L.elemi插入有序子表 L.elem0=L.elemi; /暫存在0號單元 for(j=i-dk; j0 & L.elem0L.elemwordj; j -= dk) L.elemj+dk=L.elemj; /記錄后移，查找插

13、入位置 L.elemj+dk=L.elem0; /插入到正確的位置 void ShellSort(SqList &L,int dlta,int t)/按增量序列dlta0.t-1對順序表L作希爾排序for(int k=0;k1&change;-i) change=False; for(j=0;jL. keyj+1) L. keyj L. keyj+1 change=True; 算法分析最好情況：初始時關(guān)鍵字遞增有序，每一趟排序中僅需進行一次關(guān)鍵字的比較，所以總的比較次數(shù)為n-1。在while循環(huán)之前和之中，至少要移動記錄兩次，所以總的比較次數(shù)為2(n-1)。最壞情況：初始時關(guān)鍵字遞減有序，此時

14、記錄比較和移動次數(shù)分別為：直接插入排序是一種穩(wěn)定的排序方法。原因：關(guān)鍵字相同的兩個對象，在整個排序過程中，不會通過比較而相互交換?？焖倥判虮容^次數(shù)較少、內(nèi)部排序中速度較快的方法。基本過程取待排序的結(jié)點序列中某個結(jié)點的值作為控制值，采用某種方法把這個結(jié)點放到適當(dāng)?shù)奈恢?，使得這個位置的左邊的所有結(jié)點的值都小于等于這個控制值，而這個位置的右邊的所有結(jié)點的值都大于等于這個控制值。4938659776132749 38659776132749273865977613 492738 97761365492738139776 6549273813 76976549273813 49 76 97 654949

15、temp快速排序示例快速排序算法int PARTITION(rectype R,int l,int h) int i=l; j=h; rectype temp=Ri; do while (Rj.key = temp.key)&(ij) j-; if (ij) Ri+=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); QUICKS

16、ORT(R,s1,i-1); QUICKSORT(R,i+1,t1); 最好情況每次所取的基準(zhǔn)都是當(dāng)前無序區(qū)的“中值”記錄，劃分的結(jié)果是基準(zhǔn)的左右兩個無序子區(qū)的長度大致相等。快速排序的時間復(fù)雜度考慮關(guān)鍵字的比較次數(shù)和對象移動次數(shù)最壞情況每次劃分選取的基準(zhǔn)都是當(dāng)前無序區(qū)中關(guān)鍵字最小(或最大)的記錄，劃分的結(jié)果是基準(zhǔn)的左邊(或右邊)為空，劃分前后無序區(qū)的元素個數(shù)減少一個，因此，排序必須做n-1趟，每一趟中需做n-i次比較，所以最大比較次數(shù)為 設(shè)C(n)表示對長度為n的序列進行快速排序所需的比較次數(shù)，顯然，它應(yīng)該等于對長度為n的無序區(qū)進行劃分所需的比較次數(shù)n-1，加上遞歸地對劃分所得的左右兩個無序子

17、區(qū)進行快速排序所需的比較次數(shù)。假設(shè)文件長度n=2k ，k=log2n，因此有： 快速排序的記錄移動次數(shù)不會大于比較次數(shù)，所以，快速排序的最壞時間復(fù)雜度為O(n2)；最好時間復(fù)雜度為O(nlog2n)。 可證:快速排序的平均時間復(fù)雜度也是O(nlog2n)。 快速排序是不穩(wěn)定的排序方法。四、選擇排序基本原理將待排序的結(jié)點分為已排序(初始為空)和為未排序兩組，依次將未排序的結(jié)點中值最小的結(jié)點插入已排序的組中。兩種常見的選擇排序直接選擇排序堆排序直接選擇排序的基本過程在一組對象Vi到Vn-1中選擇具有最小關(guān)鍵字的對象若它不是這組對象中的第一個對象，則將它與這組對象中的第一個對象對調(diào)。刪除具有最小關(guān)鍵

18、字的對象，在剩下的對象中重復(fù)第(1)、(2)步，直到剩余對象只有一個為止。49386597761327491338659776492749132765977649384913273897764965491327384976976549132738494997657613273849496597761327384949657697直接選擇排序示例直接選擇排序算法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é)點都是葉子，因此，以

19、這些結(jié)點為根的子樹都已是堆。即只需依次將序號為low(n/2)，low(n/2)-1，.，1的結(jié)點作為根的子樹都調(diào)整為堆即可。以大根堆為例進行說明“篩選法”基本思想：因為Ri的左右子樹已是堆，這兩棵子樹的根分別是各自子樹中關(guān)鍵字最大的結(jié)點，所以在Ri和它的左右孩子中選取關(guān)鍵字最大的結(jié)點放到Ri的位置上。若Ri的關(guān)鍵字已是三者中的最大者，則無須做任何調(diào)整，以Ri為根的子樹已構(gòu)成堆，否則，將Ri和具有最大關(guān)鍵字的左孩子R2i或右孩子R2i+1進行交換。假定R2i的關(guān)鍵字最大，將Ri和R2i交換位置，交換之后有可能導(dǎo)致R2i為根的子樹不再是堆，但由于R2i的左右子樹仍然是堆，于是可以重復(fù)上述過程，將

20、以R2i為根的子樹調(diào)整為堆，.，如此逐層遞推下去，最多可能調(diào)整到樹葉。例子：關(guān)鍵字序列為 42，13，91，23， 24， 16，05，88，n=8，故從第四個結(jié)點開始調(diào)整4213912324160588421391232416058842139188241605234213918824160523不調(diào)整421391882416052342139188241605234288912324160513428891232416051391884223241605139188422324160513建成的堆篩選算法SIFT(rectype R,int i;int m) int j; rectype

21、temp; temp=Ri; j=2*i; while (j=m) if (jm)&(Rj.keyRj+1.key) j+; if (temp.key=1; i-) SIFT(R, i, n)由于建堆的結(jié)果把關(guān)鍵字最大的記錄選到了堆頂?shù)奈恢茫判虻慕Y(jié)果應(yīng)是升序，所以，應(yīng)該將R1和Rn交換，這就得到了第一趟排序的結(jié)果。 第二趟排序的操作首先是將無序區(qū)R1到Rn-1調(diào)整為堆。這時對于當(dāng)前堆來說，它的左右子樹仍然是堆，所以，可以調(diào)用SIFT函數(shù)將R1到Rn-1調(diào)整為大根堆，選出最大關(guān)鍵字放入堆頂，然后將堆頂與當(dāng)前無序區(qū)的最后一個記錄Rn-1交換，如此反復(fù)進行下去。91884223241605139

22、188422324160513（a）初始堆R1到R813884223241605911388422324160591（b）第一趟排序之后（c）重建的堆R1到R78824422313160591882442231316059105244223131688910524422313168891（d）第二趟排序之后（e）重建的堆R1到R642241623130588914224162313058891（f）第三趟排序之后05241623134288910524162313428891（g）重建的堆R1到R524231605134288912423160513428891（h）第四趟排序之后132316

23、05244288911323160524428891（i）重建的堆R1到R423131605244288912313160524428891（j）第五趟排序之后05131623244288910513162324428891（k）重建的堆R1到R316130523244288911613052324428891（l）第六趟排序之后05131623244288910513162324428891（m）重建的堆R1到R213051623244288911305162324428891（n）第七趟排序之后05131623244288910513162324428891堆排序算法HEAPSORT(re

24、ctype 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=Ri; Ri=temp; SIFT(R,1,i-1); 堆排序的時間復(fù)雜度堆排序的時間復(fù)雜性為O(n log2n) 空間復(fù)雜性為 O(1)堆排序是不穩(wěn)定的排序方法。五、歸并排序通過對兩個有序結(jié)點序列的合并來實現(xiàn)排序。歸并：將若干個已排好序的部分合并成一個有序的部分。歸并的基本思想將待排序列R0到Rn-1看成n個長度為1的有序子序列，把這些子序列兩兩歸并，便得到high(n/2)個有序的子序列。然后再把這high(n

25、/2)個有序的子序列兩兩歸并，如此反復(fù)，直到最后得到一個長度為n的有序序列。該歸并操作，都是將兩個子序列歸并為一個子序列，稱“二路歸并”，類似地還有“三路歸并”或“多路歸并”。歸并過程示例(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,

26、i+length-1,i+2*length-1); i=i+2*length; if (i+length-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) int length=1; while (lengt