1、 待排序記錄的存儲方式待排序記錄的存儲方式：以一維數(shù)組作為存儲結(jié)構(gòu)，排序時必須實以一維數(shù)組作為存儲結(jié)構(gòu)，排序時必須實際移動記錄；際移動記錄；以鏈表以鏈表( (動態(tài)鏈表或靜態(tài)鏈表動態(tài)鏈表或靜態(tài)鏈表) )作為存儲結(jié)作為存儲結(jié)構(gòu)，排序時不用物理移動記錄，只需修改構(gòu)，排序時不用物理移動記錄，只需修改指針；指針；有的排序方法難于在鏈表上實現(xiàn)，且需要有的排序方法難于在鏈表上實現(xiàn)，且需要避免排序過程中的記錄移動，可將待排序避免排序過程中的記錄移動，可將待排序記錄本身存儲在一組地址連續(xù)的存儲單元記錄本身存儲在一組地址連續(xù)的存儲單元內(nèi)，同時附設(shè)一個指示記錄存儲位置的地內(nèi)，同時附設(shè)一個指示記錄存儲位置的地址向量，

2、排序過程中不移動記錄，而移動址向量，排序過程中不移動記錄，而移動地址向量中這些記錄的地址。地址向量中這些記錄的地址。待排序記錄的數(shù)據(jù)類型說明：#define MAXSIZE 20typedef int KeyType;typedef struct KeyType key; InfoType otherinfo;RedType;typedef struct RedType rMAXSIZE; int length;SqList;各趟排序結(jié)果各趟排序結(jié)果1 2 3 4 5 61 2 3 4 5 6 temp251 2 3 4 5 6 temp4925*1 2 3 4 5 6 temp1 2 3 4

3、 5 6 temp161 2 3 4 5 6 temp081 2 3 4 5 6完成161 2 3 4 5 6 temp491 2 3 4 5 6 temp25*1 2 3 4 5 6251 2 3 4 5 6 temp1 2 3 4 5 6 temp21 void InsertSort( SqList &L ) int i, j; for( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / ,需將需將L.ri插入有序子表插入有序子表 L.r0=L.ri; / 復(fù)制為哨兵復(fù)制為哨兵 L.ri= L.ri-1; for(j=i-2; L.r

4、0.keyL.rj.key; -j ) L.rj+1=L.rj; / 記錄后移記錄后移 L.rj+1=L.r0; / 插入到正確位置插入到正確位置 保存記錄保存記錄L.ri的副本；的副本； 監(jiān)視下標監(jiān)視下標j是否越界，自動控制循環(huán)是否越界，自動控制循環(huán)結(jié)束結(jié)束L.r0void BInsertSort(SqList &L) int i, j, m, low, high; for( i=2; i=L.length; +i ) L.r0=L.ri; / 將將L.ri暫存到暫存到L.r0 low=1; high=i-1; while( low = high ) / 在在rlow.high中折半

5、查找有序插入的位置中折半查找有序插入的位置 m = (low+high)/2; / 折半折半 if ( L.r0.key =high+1; -j ) L.rj+1=L.rj; / 記錄后移記錄后移 L.rhigh+1=L.r0; / 插入插入 1 2 3 4 5 6492516084925*0821252125*161 2 3 4 5 6491625*0821250 1 2 3 4 5void ShellInsert( SqList &L,int dk ) for( i=dk+1; i=L.Length; i+ ) if(L.ri.key 0 & L.r0.keyL.rj.ke

6、y; j-=dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置記錄后移，查找插入位置L.rj+dk = L.r0; void ShellSort(SqList &L, int dlta, int t) / 按增量序列按增量序列dlta0.t-1對順序表對順序表L作希爾排序作希爾排序 for(k=0; kt; t+) ShellInsert( L, dltak ); / 一趟增量為一趟增量為dltak的插入排序的插入排序 0 1 2 3 4 50 1 2 3 4 5void BubbleSort( SqList &L ) / 從下往上掃描的起泡排序從下往上掃描的起

7、泡排序 for( i=0; i=i;j- ) / 從下往上掃描從下往上掃描 if(L.rj+1.key L.rj.key) temp=L.rj+1; / 交換記錄交換記錄 L.rj+1=L.rj; L.rj=temp; noSwap=FALSE; if( noSwap ) break; / 本趟掃描未發(fā)生交換，則終止算法本趟掃描未發(fā)生交換，則終止算法 11111233121nininninRMNnninKCN)()()()(：是任取待排序記錄序列中的某個記錄是任取待排序記錄序列中的某個記錄 ( (例如取第一個例如取第一個記錄記錄) ) 作為作為，按照該記錄的關(guān)鍵字大小，將整個，按照該記錄的關(guān)鍵

8、字大小，將整個記錄序列劃分為左右兩個子序列：記錄序列劃分為左右兩個子序列： 左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準記錄的關(guān)左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準記錄的關(guān)鍵字鍵字 右側(cè)子序列中所有記錄的關(guān)鍵字都大于或等于基準記錄的關(guān)右側(cè)子序列中所有記錄的關(guān)鍵字都大于或等于基準記錄的關(guān)鍵字鍵字基準記錄則排在這兩個子序列中間基準記錄則排在這兩個子序列中間( (這也是該記錄最終這也是該記錄最終應(yīng)安放的位置應(yīng)安放的位置) )。然后分別對這兩個子序列重復(fù)施行上述方法，直到所然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的記錄都排在相應(yīng)位置上為止。有的記錄都排在相應(yīng)位置上為止。1 2 3 4

9、5 6一趟劃分算法：一趟劃分算法：int Partition(SqList &L, int low, int high) L.r0 = L.rlow; / 用子表的第一個記錄作基準記錄用子表的第一個記錄作基準記錄 pivotkey = L.rlow.key; /基準記錄關(guān)鍵字基準記錄關(guān)鍵字 while( lowhigh ) / 從表的兩端交替地向中間掃描從表的兩端交替地向中間掃描 while(low=pivotkey) high-; L.rlow = L.rhigh; while(lowhigh & L.rlow.key=pivotkey) low+; L.rhigh = L.

10、rlow; L.rlow = L.r0; /基準記錄到位基準記錄到位 return low; / 返回樞軸位置返回樞軸位置 void QSort(SqList &L, int low, int high) int pivotloc; if( low high ) / 長度大于長度大于1 pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); / 對低子表遞歸排序?qū)Φ妥颖磉f歸排序 QSort(L,pivotloc+1,high); / 對高子表遞歸排序?qū)Ω咦颖磉f歸排序 2125*25490816。2121211nnninni)()

11、(用居中關(guān)鍵字記錄作為基準記錄用居中關(guān)鍵字記錄作為基準記錄0 1 2 3 4 5最小者最小者最小者最小者最小者最小者0 1 2 3 4 5最小者最小者最小者最小者結(jié)果結(jié)果各趟排序后的結(jié)果各趟排序后的結(jié)果0 1 2 3 4 5i =1時選擇排序的過程時選擇排序的過程i k j i k j i k j 0 1 2 3 4 5i k j void SelectSort(SqList &L) int i, j; RedType temp; for( i=0; iL.length-1; i+ ) / 做做n-1趟選擇排序趟選擇排序 k = i; / 在當前無序區(qū)選關(guān)鍵字最小的記錄在當前無序區(qū)選關(guān)

12、鍵字最小的記錄 for( j=i+1; jL.length; j+ ) if( L.rj.key n/2 的結(jié)點都是葉子，的結(jié)點都是葉子，因此，以這些結(jié)點為根的子樹均已是堆，這樣只需將以因此，以這些結(jié)點為根的子樹均已是堆，這樣只需將以序號為序號為 n/2 n/2 -1, n/2 -2, , 1的結(jié)點為根的子樹都調(diào)的結(jié)點為根的子樹都調(diào)整為堆即可。在按此次序調(diào)整每個結(jié)點時，其左、右子整為堆即可。在按此次序調(diào)整每個結(jié)點時，其左、右子樹均已是堆。樹均已是堆。 若若ki 的左、右子樹已經(jīng)是堆，如何將以的左、右子樹已經(jīng)是堆，如何將以ki為根的為根的完全二叉樹也調(diào)整為堆？完全二叉樹也調(diào)整為堆？ 因因ki的左

13、、右子樹已經(jīng)是堆，所以必須在的左、右子樹已經(jīng)是堆，所以必須在ki 和和它的左、右孩子中選出最小（或最大）的結(jié)點放它的左、右孩子中選出最小（或最大）的結(jié)點放到到ki 的位置上，不妨設(shè)的位置上，不妨設(shè)k2i關(guān)鍵字最小，將關(guān)鍵字最小，將ki與與k2i 交換位置，而交換之后有可能導(dǎo)致以交換位置，而交換之后有可能導(dǎo)致以k2i為根的子為根的子樹不再為堆，于是可重復(fù)上述過程，將以樹不再為堆，于是可重復(fù)上述過程，將以k2i 為根為根的子樹調(diào)整為堆，的子樹調(diào)整為堆， , 如此逐層下去，最多可如此逐層下去，最多可能一直調(diào)整到樹葉，此方法稱為能一直調(diào)整到樹葉，此方法稱為“篩選法篩選法”。 例子：例子：關(guān)鍵字序列為關(guān)

14、鍵字序列為 42，13，91，23， 24， 16，05，88，n=8，故從第四個結(jié)點開始調(diào)，故從第四個結(jié)點開始調(diào)整整424213139191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不調(diào)整不調(diào)整4242131391918888242416160505232342139188241605234242888891912323242416160505131342889123241605139191888842422323242416160505131391884223241

15、60513建成的堆建成的堆調(diào)整算法：typedef SqList HeapType;void HeapAdjust(HeapType &H, int s, int m) RedType rc; rc = H.rs; for( j=2*s; j=m; j*=2 ) / 沿沿key較大的孩子結(jié)點向下篩選較大的孩子結(jié)點向下篩選 if( jm & H.rj.key= H.rj.key ) break; / rc應(yīng)插入在位置應(yīng)插入在位置s上上 H.rs = H.rj; s = j; H.rs = rc; / 已知已知H.rs.m中記錄的關(guān)鍵字除中記錄的關(guān)鍵字除H.rs.key之外均滿足堆

16、之外均滿足堆的定義，本算法調(diào)整的定義，本算法調(diào)整H.rs 的關(guān)鍵字，使的關(guān)鍵字，使H.rs.m成為一個成為一個大頂堆大頂堆. 上述算法只是對一個指定的結(jié)點進行調(diào)整。上述算法只是對一個指定的結(jié)點進行調(diào)整。有了這個算法，則將初始的無序區(qū)有了這個算法，則將初始的無序區(qū)R1R1到到RnRn建成一個大根堆，可用以下語句實現(xiàn)建成一個大根堆，可用以下語句實現(xiàn)：for ( i = n/2; i=1; i- ) HeapAdjust( H, i, H.length ) HeapAdjustHeapAdjust919188884242232324241616050513139188422324160513（a a

17、）初始堆）初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后（c c）重建的堆）重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f

18、 f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（g g）重建的堆）重建的堆R1R1到到R5R5242423231616050513134242888891912423160513428891（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891（j j）第五趟排序之后）第五趟排序之后05

19、0513131616232324244242888891910513162324428891（k k）重建的堆）重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891（l l）第六趟排序之后）第六趟排序之后050513131616232324244242888891910513162324428891（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891（n n）第七趟排序之后）第七趟排序之后0505131316162323242442

20、42888891910513162324428891void HeapSort(HeapType &H) RedType temp; int i; for(i=H.length/2; i0; i-) / 把把H.r1.H.length建成大頂堆建成大頂堆HeapAdjust(H,i,H.length); for( i=H.length; i1; i- )temp = H.r1; H.r1 = H.ri; H.ri = temp; HeapAdjust( H, 1, i-1 ); / 將將H.r1.i-1重新調(diào)整為大頂堆重新調(diào)整為大頂堆 1212ki1-iik / 將有序的將有序的SRi

21、.m和和SRm+1.n歸并為有序的歸并為有序的TRi.n 算法算法void Merge( RedType SR, RedType TR, int i,int m,int n) int j, k, l ; for( j=m+1,k=i; i=m & j=n; +k) if ( SRi.key = SRj.key ) TRk = SRi+; else TRk=SRj+; if( i = m ) for( l=0; l=m-i; l+ ) TRk+l=SRi+l; / 將剩余的將剩余的SRi.m復(fù)制到復(fù)制到TR if( j =n ) for( l=0; l=n-j; l+) TRk+l=SR

22、j+l; / 將剩余的將剩余的SRj.n復(fù)制到復(fù)制到TR 一趟歸并算法一趟歸并算法: :void MergePass(void MergePass(RedType R,R,RedType R1,int length)R1,int 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;leng

23、th; if (i+length-1n-1) if (i+length-1n-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; 歸并排序算法歸并排序算法: :void MergeSort(void MergeSort(RedType R) R) int length=1; int length=1; while (lengthn) while (lengthn) MERGEPASS(R,R1,length

24、); MERGEPASS(R,R1,length); length=2 length=2* *length;length; MERGEPASS(R1,R,length); MERGEPASS(R1,R,length); length=2 length=2* *length;length; void MSort(RedType SR, RedType TR1, int s, int t) int m; RedType TR2MAXSIZE+1; if( s = t ) TR1s=SRs; else m=(s+t)/2; / 將將SRs.t平分為平分為SRs.m和和SRm+1.t MSort(SR

25、, TR2, s, m); MSort(SR, TR2, m+1, t); Merge(TR2,TR1, s, m, t); 21 25 49 25* 16 08 21 25 49 25* 16 08 21 25 49 25 49 21 25* 16 08 25* 16 08 21 25 49 25* 16 08 25* 16 08 21 25 49 16 08 25* 25 49 21 21 25* 16 08 49 25 遞遞歸歸回回 推推內(nèi)部排序方法的比較和選擇內(nèi)部排序方法的比較和選擇選取排序方法時需要考慮的因素有：選取排序方法時需要考慮的因素有： 待排序的記錄數(shù)目待排序的記錄數(shù)目 記錄

26、本身信息量的大小記錄本身信息量的大小 關(guān)鍵字的結(jié)構(gòu)及其分布情況關(guān)鍵字的結(jié)構(gòu)及其分布情況 對排序穩(wěn)定性的要求對排序穩(wěn)定性的要求 語言工具的條件、輔助空間的大小語言工具的條件、輔助空間的大小 排序方法排序方法最壞時間最壞時間復(fù)雜度復(fù)雜度平均時間平均時間復(fù)雜度復(fù)雜度 輔助空間輔助空間 穩(wěn)定性穩(wěn)定性直接插直接插入排序入排序O(nO(n2 2) ) O(n O(n2 2) ) O(1) O(1) 穩(wěn)定的穩(wěn)定的二分法二分法插入排序插入排序O(nO(n2 2) ) O(n O(n2 2) ) O(1) O(1) 穩(wěn)定的穩(wěn)定的表插入排序表插入排序O(nO(n2 2) ) O(n O(n2 2) ) O(n)

27、O(n) 穩(wěn)定的穩(wěn)定的ShellShell排序排序O(nO(n1.31.3) ) O(n O(n1.31.3) ) O(1) O(1) 不穩(wěn)定的不穩(wěn)定的直接選直接選擇排序擇排序O(nO(n2 2) ) O(n O(n2 2) ) O(1) O(1)不穩(wěn)定的不穩(wěn)定的堆排序堆排序O(nlogO(nlog2 2n)n) O(nlog O(nlog2 2n)n) O(1) O(1)不穩(wěn)定的不穩(wěn)定的起泡排序起泡排序O(nO(n2 2) ) O(n O(n2 2) ) O(1) O(1) 穩(wěn)定的穩(wěn)定的快速排序快速排序O(nO(n2 2) ) O(nlog O(nlog2 2n)n) O(logO(log2 2n)n)不穩(wěn)定的不穩(wěn)定的基數(shù)排序基數(shù)排序O(d(n+r)O(d(n+r) O(d(n+r) O(d(n+r) O(r+n)O(r+n) 穩(wěn)定的穩(wěn)定的歸并排序歸并排序O(nlogO(nlog2 2n)n) O(nlog O(nlog2 2n)n) O(n) O(n) 穩(wěn)定的穩(wěn)定的 （1 1）平均時間性能：以快速排序法最佳，但最壞情況）平均時間性能：以快速排序法最佳，但最壞情況下不如堆排序和歸并排序；在下不