第7章-排序算法

1、1第七章：第七章：排序算法排序算法2排序的概念排序的概念排序是計算機內(nèi)經(jīng)常進行的一種操作，其排序是計算機內(nèi)經(jīng)常進行的一種操作，其目的是將一組目的是將一組“無序無序”的記錄序列調(diào)整為的記錄序列調(diào)整為“有序有序”的記錄序列。的記錄序列。例如：將下列關(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, 973假設(shè)含假設(shè)含n個記錄的序列為個記錄的序列為 R1, R2, ， Rn 其相應的關(guān)鍵字序列為其相應的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以

2、進行比較，即在這些關(guān)鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關(guān)系它們之間存在著這樣一個關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。的操作稱作排序。排序的概念排序的概念4內(nèi)部排序和外部排序內(nèi)部排序和外部排序若若整個排序過程不需要訪問外存整個排序過程不需要訪問外存便能便能完成，則稱此類排序問題完成，則稱此類排序問題為內(nèi)部排序；為內(nèi)部排序； 反之，若參加排序的記錄數(shù)量很大，反之，若參加排序的記錄數(shù)量很大， 整個序列的排序過程整個序列的排序過程不可能在內(nèi)存中不可能在內(nèi)存中 完成完成，則稱

3、此類排序問題，則稱此類排序問題為外部排序為外部排序。5待排記錄的數(shù)據(jù)類型定義待排記錄的數(shù)據(jù)類型定義#define MAXSIZE 1000 / 待排順序表最大長度待排順序表最大長度typedef int KeyType; / 關(guān)鍵字類型為整數(shù)類型關(guān)鍵字類型為整數(shù)類型typedef struct KeyType key; / 關(guān)鍵字項關(guān)鍵字項 InfoType otherinfo; / 其它數(shù)據(jù)項其它數(shù)據(jù)項 RcdType; / 記錄類型記錄類型typedef struct RcdType rMAXSIZE+1; / r0閑置閑置 int length; / 順序表長度順序表長度 SqList;

4、 / 順序表類型順序表類型6有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的基本思想一趟直接插入排序的基本思想有序序列R1.i無序序列 Ri+1.n7實現(xiàn)實現(xiàn)“一趟插入排序一趟插入排序”分三步進行分三步進行3將Ri 插入插入(復制)到Rj+1的位置上。2將Rj+1.i-1中的所有記錄記錄均后移后移 一個位置；1在R1.i-1中查找查找Ri的插入位置， R1.j.key Ri.key Rj+1.i-1.key；8直接插入排序直接插入排序9void InsertionSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i=2; i=L.leng

5、th; +i ) if (L.ri.key L.ri-1.key) / InsertSortL.r0 = L.ri; / 復制為監(jiān)視哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 記錄后移L.rj+1 = L.r0; / 插入到正確位置10直接插入排序時間分析直接插入排序時間分析最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較比較”的次數(shù)：的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較比較”的次數(shù)：的次數(shù)：112nni02) 1)(4()

6、 1(2nnini“移動移動”的次數(shù)：的次數(shù)：“移動移動”的次數(shù)：的次數(shù)：2) 1)(4() 1(2nnini11 因為因為R1.i-1 R1.i-1 是一個按關(guān)鍵字有是一個按關(guān)鍵字有序的有序序列，則可以序的有序序列，則可以利用折半查找實利用折半查找實現(xiàn)現(xiàn)“在在R1.i-1R1.i-1中中查找查找RiRi的的插入位插入位置置”，如此實現(xiàn)的插入排序為，如此實現(xiàn)的插入排序為折半插入折半插入排序。排序。折半插入排序折半插入排序1214 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhig

7、hmhighmhighmlow例如:再如:插入位置插入位置L.rL.r13void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 記錄后移L.rhigh+1 = L.r0; / 插入14low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入點在低半?yún)^(qū)else l

8、ow = m+1; / 插入點在高半?yún)^(qū)15 希爾排序希爾排序 基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。 具體做法為：16 將記錄序列分成若干子序列，分別對每個子序列進將記錄序列分成若干子序列，分別對每個子序列進行插入排序。行插入排序。 其中，其中，d d 稱為增量，它的值在排序過程中從大到小逐稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為漸縮小，直至最后一趟排序減為 1 1。例如：將例如：將 n 個記錄分成個記錄分成 d 個子序列：個子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+

9、2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 希爾排序希爾排序17例如：例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希爾排序，設(shè)增量第一趟希爾排序，設(shè)增量 d=5d=511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量第二趟希爾排序，設(shè)增量 d=3d=39 18 12 11 23 16 25 31 30 47 36第三趟希爾排序，設(shè)增量第三趟希爾排序，設(shè)增量 d=1d=1 9 11 12 16 18 23 25 30 31 36 47 18void ShellInsert ( SqList &L, i

10、nt dk ) for ( i=dk+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=dk) L.rj+dk = L.rj; / 記錄后移，查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsert19void ShellSort (SqList &L, int dlta, int t) / 增量為dlta的希爾排序 for (k=0; k1) / while / BubbleSorti = n;i = lastExchangeIndex; / 本趟進行過交換的 / 最后一個記錄的位置 if

11、 (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下進行交換的記錄位置 /iffor (j = 1; j i; j+)lastExchangeIndex = 1;23最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進行一趟起泡只需進行一趟起泡“比較比較”的次數(shù)：的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）： 需進行需進行n-1趟起泡趟起泡“比較比較”的次數(shù)：的次數(shù)：0“移動移動”的次數(shù)：的次數(shù)：“移動移動”的次數(shù)：的次數(shù)：n-12) 1(

12、) 1(2nnini2) 1(3) 1(32nnini冒泡排序時間分析冒泡排序時間分析24一趟快速排序一趟快速排序目標：目標：找一個記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動至該記錄之前移動至該記錄之前，反之，凡關(guān)鍵字大于關(guān)鍵字大于樞軸樞軸的記錄均移動至該記錄之后移動至該記錄之后。致使一趟排序一趟排序之后，記錄的無序序列Rs.t將分割成兩部分分割成兩部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key (sji-1) 樞軸樞軸 (i+1jt)。2552 49 80 36 14 58 61 97 23 75stlowhigh設(shè)設(shè) R

13、s=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關(guān)鍵字進行比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進行比較，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow26int Partition (RedType& R, int low, int high) pivotkey = Rlow.key; while (lowhigh) while (low=pivotkey) -high; RlowRhigh; while (lowhigh & Rlow.k

14、ey=pivotkey) +low; RlowRhigh; return low; / 返回樞軸所在位置 / Partition27int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸 while (lowhigh) while(low=pivotkey) - high; / 從右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索Rhigh = Rlow;Rlow =

15、R0; return low;28快速排序快速排序 首先對無序的記錄序列進行“一次劃分一次劃分”，之后分別分別對分割所得兩個子序列“遞歸遞歸”進行快速進行快速排序排序。無無 序序 的的 記記 錄錄 序序 列列無序記錄子序列無序記錄子序列(1)(1)無序子序列無序子序列(2)(2)樞軸樞軸一次劃分一次劃分分別進行快速排序分別進行快速排序29void QSort (RedType & R, int s, int t ) / 對記錄序列Rs.t進行快速排序 if (s t-1) / 長度大于1 / QSortpivotloc = Partition(R, s, t); / 對 Rs.t 進行

16、一次劃分一次劃分QSort(R, s, pivotloc-1); / 對低子序列遞歸排序，pivotloc是樞軸位置是樞軸位置QSort(R, pivotloc+1, t); / 對高子序列遞歸排序30快速排序的時間分析快速排序的時間分析假設(shè)假設(shè)一次劃分所得樞軸位置一次劃分所得樞軸位置 i=ki=k，則對，則對n n 個記錄進個記錄進行快排所需時間：行快排所需時間：其中其中 T Tpasspass( (n n) )為對為對 n n 個記錄進行一次劃分所需時間。個記錄進行一次劃分所需時間。 若待排序列中記錄的關(guān)鍵字是隨機分布的，則若待排序列中記錄的關(guān)鍵字是隨機分布的，則 k k 取取 1 1 至

17、至 n n 中任意一值的可能性相同。中任意一值的可能性相同。T(n) = Tpass(n) + T(k-1) + T(n-k)31nkavgavgavgknTkTnCnnT1)() 1(1)(設(shè) Tavg(1)b則可得結(jié)果：) 1ln() 1)(22()(nncbnTavg結(jié)論結(jié)論: 快速排序的時間復雜度為快速排序的時間復雜度為O(nlogn)由此可得快速排序所需時間的平均值為：32 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時，快速排序?qū)⑼懟癁槠鹋菖判驎r，快速排序?qū)⑼懟癁槠鹋菖判颍鋾r間復雜度為O(n2)?？焖倥判虻臅r間分析快速排序的時間分析33簡單選擇排序簡單選擇

18、排序假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列R1.i-1無序序列 Ri.n 第 i 趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n34簡單選擇排序簡單選擇排序35void SelectSort (Elem R, int n ) / 對記錄序列R1.n作簡單選擇排序。 for (i=1; i0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大頂堆for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當前未經(jīng)排序子序列 / H.r1.i中最后一個記錄相互交換 HeapAdjust(H.r,

19、 1, i-1); / 對 H.r1 進行篩選4098814973556412362740例如例如:是最大堆是最大堆12但在 98 和 12 進行互換之后，它就不不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較比較41void HeapAdjust (RcdType &R, int s, int m) / 已知 Rs.m中記錄的關(guān)鍵字除 Rs 之外均 / 滿足堆的特征，本函數(shù)自上而下調(diào)整 Rs 的 / 關(guān)鍵字，使 Rs.m 也成為一個大頂堆 / HeapAdjustrc = Rs; / 暫存 Rs for ( j=2*s; j= Rj.key ) break;

20、 / 再作“根”和“子樹根”之間的比較， / 若“=”成立，則說明已找到 rc 的插 / 入位置 s ，不需要繼續(xù)往下調(diào)整Rs = Rj; s = j; / 否則記錄上移，尚需繼續(xù)往下調(diào)整if ( jm & Rj.keyRj+1.key ) +j; / 左/右“子樹根”之間先進行相互比較 / 令 j 指示關(guān)鍵字較大記錄的位置43建堆是一個從下往上進行建堆是一個從下往上進行“篩選篩選”的過程的過程40554973816436122798例如例如: : 排序之前的關(guān)鍵字序列為排序之前的關(guān)鍵字序列為123681734998817355 現(xiàn)在，左現(xiàn)在，左/ /右子樹都已經(jīng)調(diào)整為堆，最后只要右子

21、樹都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點，使整個二叉樹是個調(diào)整根結(jié)點，使整個二叉樹是個“堆堆”即可。即可。9849406436122744堆排序的時間復雜度分析堆排序的時間復雜度分析1. 對深度為對深度為 k 的堆，的堆，“篩選篩選”所需進行的關(guān)鍵字所需進行的關(guān)鍵字比較的次數(shù)至多為比較的次數(shù)至多為2(k-1)；3. 調(diào)整調(diào)整“堆頂堆頂” n-1 次，總共進行的關(guān)鍵次，總共進行的關(guān)鍵 字比較的次數(shù)不超過字比較的次數(shù)不超過 2 ( log2(n-1) + log2(n-2) + +log22) 2n( log2n ) 因此，因此，堆排序的時間復雜度為堆排序的時間復雜度為O(O(n nloglogn n

22、) )。2. 對對 n 個關(guān)鍵字，建成深度為個關(guān)鍵字，建成深度為h(= log2n +1)的堆，的堆，所需進行的關(guān)鍵字比較的次數(shù)至多所需進行的關(guān)鍵字比較的次數(shù)至多 4n；45 通常采用的是通常采用的是2-2-路歸并路歸并排序。即：排序。即：將兩個將兩個位置相鄰的記錄有序子序列位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。歸并為一個記錄的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n歸并排序歸并排序46void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有

23、序的記錄序列 SRi.m 和 SRm+1.n / 歸并為有序的記錄序列 TRi.n / Mergefor (j=m+1, k=i; i=m & j=n; +k) / 將將SR中記錄由小到大地并入中記錄由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; 47if (i=m) TRk.n = SRi.m; / 將剩余的 SRi.m 復制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的 SRj.n 復制到 TR48歸并排序的算法歸并排序的算法如果記錄無序序列如果記錄無序序列 Rs.t 的兩部分的兩部分 R

24、s. (s+t)/2 和 R (s+t)/2 +1.t分別按關(guān)鍵字有序，分別按關(guān)鍵字有序， 則利用上述歸并算法很容易將它們歸則利用上述歸并算法很容易將它們歸并成整個記錄序列是一個有序序列。并成整個記錄序列是一個有序序列。 由此，應該先分別對這兩部分進行由此，應該先分別對這兩部分進行 2-路歸并排序。路歸并排序。49例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80

25、 2350void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將SRs.t 歸并排序為 TR1s.t if (s= =t) TR1s=SRs; else / Msort 51m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將SRs.m歸并為有序的TR2s.mMsort (SR, TR2, m+1, t); /遞歸地SRm+1.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸

26、并到TR1s.t52void MergeSort (SqList &L) / 對順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對 n 個記錄進行歸并排序的時間復雜度為(nlogn)。即： 每一趟歸并的時間復雜度為 O(n)， 總共需進行 log2n 趟。53非遞歸的歸并排序非遞歸的歸并排序nVoid MergeSort(SqList &list ) len =1; while( len list.length ) MergePass( list, tempList,len); len *= 2; Mer

27、gePass( tempList, list, len); len *=2; nVoid MergePass(SqList &initList, SqList &mergedList, int len) int i = 1; while( i+2 * len -1= list.CurrentSize-1 ) merge(initlist, mergedList, i, i+len-1, i+2*len-1 ); i+=2*len; if ( i+len= initList. length-1) merge(initlist,mergedList,i,i+len-1,initLi

28、st. length-1 ); else for (intj = i; j = initList.length-1; j+) mergedList.r j = initLIst.r j ; 54基數(shù)排序是一種借助基數(shù)排序是一種借助“多關(guān)鍵字排多關(guān)鍵字排序序”的思想來實現(xiàn)的思想來實現(xiàn)“單關(guān)鍵字排序單關(guān)鍵字排序”的內(nèi)部排序算法。的內(nèi)部排序算法?；鶖?shù)排序基數(shù)排序55多關(guān)鍵字的排序多關(guān)鍵字的排序 n 個記錄的序列個記錄的序列 R1, R2, ，Rn對關(guān)鍵字對關(guān)鍵字 (Ki0, Ki1,Kid-1) ) 有序有序是指： 其中其中: : K0 被稱為被稱為 “最主最主”位關(guān)鍵字位關(guān)鍵字Kd-1 被稱為被稱

29、為 “最次最次”位關(guān)鍵字位關(guān)鍵字 對于序列中任意兩個記錄 Ri 和 Rj(1ijn) 都滿足滿足下列(詞典詞典)有序有序關(guān)系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) )56 先對先對K0進行排序進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關(guān)鍵字排序完直至最后對最次位關(guān)鍵字排序完成為止成為止。最高位優(yōu)先最高位優(yōu)先MSD法法57 先對 Kd-1 進行排序，然后對 Kd-2 進行排序，依次類推，直至對最主位直至對最主位關(guān)鍵字關(guān)鍵字 K0 排序完成為止排序完成為止。最低位優(yōu)先最低位

30、優(yōu)先LSD法法58鏈式基數(shù)排序鏈式基數(shù)排序假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的假如多關(guān)鍵字的記錄序列中，每個關(guān)鍵字的取值范圍相同，則按取值范圍相同，則按LSD法進行排序時，可以法進行排序時，可以采用采用“分配分配- -收集收集”的方法，其好處是不需要進的方法，其好處是不需要進行關(guān)鍵字間的比較。行關(guān)鍵字間的比較。對于數(shù)字型或字符型的對于數(shù)字型或字符型的單關(guān)鍵字單關(guān)鍵字，可以，可以看看成成是由多個數(shù)位或多個字符構(gòu)成的是由多個數(shù)位或多個字符構(gòu)成的多關(guān)鍵字多關(guān)鍵字，此時可以此時可以采用采用這種這種“分配分配- -收集收集”的辦法的辦法進行排進行排序序，稱作基數(shù)排序法稱作基數(shù)排序法。59鏈式基數(shù)排序鏈

31、式基數(shù)排序601 1、待排序記錄以指針相鏈，構(gòu)成一個鏈表；、待排序記錄以指針相鏈，構(gòu)成一個鏈表； 2 2、“分配分配” ” 時，按當前時，按當前“關(guān)鍵字位關(guān)鍵字位”所取值，所取值，將記錄分配到不同的將記錄分配到不同的 “ “鏈隊列鏈隊列” ” 中，每個中，每個隊列中記錄的隊列中記錄的 “ “關(guān)鍵字位關(guān)鍵字位” ” 相同；相同；3 3、“收集收集”時，按當前關(guān)鍵字位取值從小到時，按當前關(guān)鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表大將各隊列首尾相鏈成一個鏈表; ;4 4、對每個關(guān)鍵字位均重復、對每個關(guān)鍵字位均重復 2) 2) 和和 3) 3) 兩步。兩步。鏈式基數(shù)排序鏈式基數(shù)排序61 基數(shù)排序的

32、時間復雜度為基數(shù)排序的時間復雜度為O(d(n+rd)其中：分配為其中：分配為O(n) 收集為收集為O(rd)(rd為為“基基”) d為為“分配分配-收集收集”的趟數(shù)的趟數(shù)堆排序的時間復雜度分析堆排序的時間復雜度分析62各種排序方法時間性能各種排序方法時間性能1.1.平均的時間性能平均的時間性能基數(shù)排序基數(shù)排序時間復雜度為時間復雜度為 O(O(n nloglogn n) )：快速排序、堆排序和歸并排序快速排序、堆排序和歸并排序時間復雜度為時間復雜度為 O(n2)O(n2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡單選擇排序簡單選擇排序時間復雜度為時間復雜度為 O(n):O(n):632

33、.2.當待排記錄序列按關(guān)鍵字順序有序時當待排記錄序列按關(guān)鍵字順序有序時3.3.簡單選擇排序、堆排序和歸并排序的時間簡單選擇排序、堆排序和歸并排序的時間性能不隨記錄序列中關(guān)鍵字的分布而改變。性能不隨記錄序列中關(guān)鍵字的分布而改變。 直接插入排序和起泡排序直接插入排序和起泡排序能達到能達到O(O(n n) )的時的時間復雜度，間復雜度， 快速排序快速排序的時間性能的時間性能蛻化為蛻化為O(O(n n2 2) ) 。各種排序方法時間性能各種排序方法時間性能64指的是排序過程中所需的輔助空間大小指的是排序過程中所需的輔助空間大小1.1.所有的所有的簡單排序方法簡單排序方法( (包括：直接插入、包括：直接

34、插入、起泡和簡單選擇起泡和簡單選擇) ) 和堆排序和堆排序的空間復雜度的空間復雜度為為O(1)O(1)；2.2.快速排序為快速排序為O(logO(logn n) )，為遞歸程序執(zhí)行過程中，棧為遞歸程序執(zhí)行過程中，棧所需的輔助空間；所需的輔助空間；各種排序方法空間性能各種排序方法空間性能3.3.歸并排序歸并排序所需輔助空間最多，其空間復雜度為所需輔助空間最多，其空間復雜度為 O(O(n n););4.4.鏈式基數(shù)排序鏈式基數(shù)排序需附設(shè)隊列首尾指針，則空間復雜需附設(shè)隊列首尾指針，則空間復雜度為度為 O(O(rdrd) )。65排序方法的穩(wěn)定性能排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對于兩

35、個關(guān)鍵字相等的記穩(wěn)定的排序方法指的是，對于兩個關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。之后，沒有改變。 2. 當對多關(guān)鍵字的記錄序列進行當對多關(guān)鍵字的記錄序列進行LSD方法排序時，必方法排序時，必須采用穩(wěn)定的排序方法。須采用穩(wěn)定的排序方法。排序之前排序之前 : : Ri(K) Rj(K) 排序之后排序之后 : : Ri(K) Rj(K) 3. 快速排序、堆排序和希爾排序是不穩(wěn)定的排序方快速排序、堆排序和希爾排序是不穩(wěn)定的排序方法。法。66例如：例如： 排序前排序前 ( 56, 34, 47, 23, 66,

36、18, 82, 47 )若排序后得到結(jié)果若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是則稱該排序方法是穩(wěn)定的穩(wěn)定的;若排序后得到結(jié)果若排序后得到結(jié)果 ( 18, 23, 34, 47, 47, 56, 66, 82 )則稱該排序方法是則稱該排序方法是不穩(wěn)定的不穩(wěn)定的。67排序方法的時間復雜度的下限排序方法的時間復雜度的下限 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于基于“比較關(guān)鍵字比較關(guān)鍵字”進進行排序的排序方法。行排序的排序方法。 可以證明， 這類排序法可能達到的最可能達到的最快的時間復雜度為快的時間復雜度為O(nlogn)

37、。 (基數(shù)排序不是基于“比較關(guān)鍵字”的排序方法，所以它不受這個限制。)68 例如:對三個關(guān)鍵字進行排序的判定樹如下：K1K3K1K2K1K3K2K3K2 K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2樹上的樹上的每一次每一次“比較比較”都是必要的都是必要的;樹上的樹上的葉子結(jié)點包含所有可能情況葉子結(jié)點包含所有可能情況。69 一般情況下，對n個關(guān)鍵字進行排序，可能得到的結(jié)果有n! 種，由于含n! 個葉子結(jié)點的二叉樹的深度不小于log2(n!) +1, 則對 n 個關(guān)鍵字進行排序的比較次數(shù)至少是 log2(n!) nlog2n (斯蒂林近似公式)。 所以，基于基于“比

38、較關(guān)鍵字比較關(guān)鍵字”進行排序進行排序的的排序方法，可能達到的最快的時間復雜排序方法，可能達到的最快的時間復雜度為度為 O(nlogn)。70 對對外存中數(shù)據(jù)的讀外存中數(shù)據(jù)的讀/ /寫是以寫是以“數(shù)據(jù)塊數(shù)據(jù)塊”為單位進行的為單位進行的；讀讀/ /寫外存中一個寫外存中一個“數(shù)據(jù)塊數(shù)據(jù)塊”的數(shù)據(jù)所需要的時間為：的數(shù)據(jù)所需要的時間為： T TI/OI/O = t = tseek seek + t+ tlala + n + n t twmwm 其中其中 t tseek seek 為尋查時間為尋查時間( (查找該數(shù)據(jù)塊所在磁道查找該數(shù)據(jù)塊所在磁道) ) t tlala 為等待為等待( (延遲延遲) )時間時間 n n t twmwm 為傳輸數(shù)據(jù)塊中為傳輸數(shù)據(jù)塊中n n個記錄的時間。個記錄的時間。外部排序外部排序 待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，則待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，則無法利用前面討論的排序方法無法利用前面討論的排序方法71 按可用內(nèi)存大小，利用內(nèi)部排序方法，按可用內(nèi)存大小，利用內(nèi)部排序方法，構(gòu)造若干構(gòu)造若干( ( 記錄的記錄的) ) 有序子