第7章-排序算法

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

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

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

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

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

6、 1(2nnini“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：“移動(dòng)移動(dòng)”的次數(shù)：的次數(shù)：2) 1)(4() 1(2nnini11 因?yàn)橐驗(yàn)镽1.i-1 R1.i-1 是一個(gè)按關(guān)鍵字有是一個(gè)按關(guān)鍵字有序的有序序列，則可以序的有序序列，則可以利用折半查找實(shí)利用折半查找實(shí)現(xiàn)現(xiàn)“在在R1.i-1R1.i-1中中查找查找RiRi的的插入位插入位置置”，如此實(shí)現(xiàn)的插入排序?yàn)?，如此?shí)現(xiàn)的插入排序?yàn)檎郯氩迦胝郯氩迦肱判?。排序。折半插入排序折半插入排?214 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; / 插入點(diǎn)在低半?yún)^(qū)else l

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

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

12、) 1(2nnini2) 1(3) 1(32nnini冒泡排序時(shí)間分析冒泡排序時(shí)間分析24一趟快速排序一趟快速排序目標(biāo)：目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動(dòng)至該記錄之前移動(dòng)至該記錄之前，反之，凡關(guān)鍵字大于關(guān)鍵字大于樞軸樞軸的記錄均移動(dòng)至該記錄之后移動(dòng)至該記錄之后。致使一趟排序一趟排序之后，記錄的無序序列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)鍵字進(jìn)行比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進(jì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快速排序快速排序 首先對(duì)無序的記錄序列進(jìn)行“一次劃分一次劃分”，之后分別分別對(duì)分割所得兩個(gè)子序列“遞歸遞歸”進(jìn)行快速進(jìn)行快速排序排序。無無 序序 的的 記記 錄錄 序序 列列無序記錄子序列無序記錄子序列(1)(1)無序子序列無序子序列(2)(2)樞軸樞軸一次劃分一次劃分分別進(jìn)行快速排序分別進(jìn)行快速排序29void QSort (RedType & R, int s, int t ) / 對(duì)記錄序列Rs.t進(jìn)行快速排序 if (s t-1) / 長度大于1 / QSortpivotloc = Partition(R, s, t); / 對(duì) Rs.t 進(jìn)行

16、一次劃分一次劃分QSort(R, s, pivotloc-1); / 對(duì)低子序列遞歸排序，pivotloc是樞軸位置是樞軸位置QSort(R, pivotloc+1, t); / 對(duì)高子序列遞歸排序30快速排序的時(shí)間分析快速排序的時(shí)間分析假設(shè)假設(shè)一次劃分所得樞軸位置一次劃分所得樞軸位置 i=ki=k，則對(duì)，則對(duì)n n 個(gè)記錄進(jìn)個(gè)記錄進(jìn)行快排所需時(shí)間：行快排所需時(shí)間：其中其中 T Tpasspass( (n n) )為對(duì)為對(duì) n n 個(gè)記錄進(jìn)行一次劃分所需時(shí)間。個(gè)記錄進(jìn)行一次劃分所需時(shí)間。 若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則若待排序列中記錄的關(guān)鍵字是隨機(jī)分布的，則 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é)論: 快速排序的時(shí)間復(fù)雜度為快速排序的時(shí)間復(fù)雜度為O(nlogn)由此可得快速排序所需時(shí)間的平均值為：32 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判驎r(shí)，快速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)間復(fù)雜度為O(n2)?？焖倥判虻臅r(shí)間分析快速排序的時(shí)間分析33簡單選擇排序簡單選擇

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

19、 1, i-1); / 對(duì) H.r1 進(jìn)行篩選4098814973556412362740例如例如:是最大堆是最大堆12但在 98 和 12 進(jìn)行互換之后，它就不不是堆了，因此，需要對(duì)它進(jìn)行“篩選”。98128173641298比較比較比較41void HeapAdjust (RcdType &R, int s, int m) / 已知 Rs.m中記錄的關(guān)鍵字除 Rs 之外均 / 滿足堆的特征，本函數(shù)自上而下調(diào)整 Rs 的 / 關(guān)鍵字，使 Rs.m 也成為一個(gè)大頂堆 / 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ìn)行相互比較 / 令 j 指示關(guān)鍵字較大記錄的位置43建堆是一個(gè)從下往上進(jìn)行建堆是一個(gè)從下往上進(jìn)行“篩選篩選”的過程的過程40554973816436122798例如例如: : 排序之前的關(guān)鍵字序列為排序之前的關(guān)鍵字序列為123681734998817355 現(xiàn)在，左現(xiàn)在，左/ /右子樹都已經(jīng)調(diào)整為堆，最后只要右子

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

22、) )。2. 對(duì)對(duì) n 個(gè)關(guān)鍵字，建成深度為個(gè)關(guān)鍵字，建成深度為h(= log2n +1)的堆，的堆，所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多 4n；45 通常采用的是通常采用的是2-2-路歸并路歸并排序。即：排序。即：將兩個(gè)將兩個(gè)位置相鄰的記錄有序子序列位置相鄰的記錄有序子序列歸并為一個(gè)記錄的有序序列。歸并為一個(gè)記錄的有序序列。有有 序序 序序 列列 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 復(fù)制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的 SRj.n 復(fù)制到 TR48歸并排序的算法歸并排序的算法如果記錄無序序列如果記錄無序序列 Rs.t 的兩部分的兩部分 R

24、s. (s+t)/2 和 R (s+t)/2 +1.t分別按關(guān)鍵字有序，分別按關(guān)鍵字有序， 則利用上述歸并算法很容易將它們歸則利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。并成整個(gè)記錄序列是一個(gè)有序序列。 由此，應(yīng)該先分別對(duì)這兩部分進(jìn)行由此，應(yīng)該先分別對(duì)這兩部分進(jì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 歸并排序?yàn)?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) / 對(duì)順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，對(duì) n 個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為(nlogn)。即： 每一趟歸并的時(shí)間復(fù)雜度為 O(n)， 總共需進(jì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)鍵字排序序”的思想來實(shí)現(xiàn)的思想來實(shí)現(xiàn)“單關(guān)鍵字排序單關(guān)鍵字排序”的內(nèi)部排序算法。的內(nèi)部排序算法。基數(shù)排序基數(shù)排序55多關(guān)鍵字的排序多關(guān)鍵字的排序 n 個(gè)記錄的序列個(gè)記錄的序列 R1, R2, ，Rn對(duì)關(guān)鍵字對(duì)關(guān)鍵字 (Ki0, Ki1, ,Kid-1) ) 有序有序是指： 其中其中: : K0 被稱為被稱為 “最主最主”位關(guān)鍵字位關(guān)鍵字Kd-1 被稱為

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

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

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

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

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

34、選擇起泡和簡單選擇) ) 和堆排序和堆排序的空間復(fù)雜度的空間復(fù)雜度為為O(1)O(1)；2.2.快速排序?yàn)榭焖倥判驗(yàn)镺(logO(logn n) )，為遞歸程序執(zhí)行過程中，棧為遞歸程序執(zhí)行過程中，棧所需的輔助空間；所需的輔助空間；各種排序方法空間性能各種排序方法空間性能3.3.歸并排序歸并排序所需輔助空間最多，其空間復(fù)雜度為所需輔助空間最多，其空間復(fù)雜度為 O(O(n n););4.4.鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為度為 O(O(rdrd) )。65排序方法的穩(wěn)定性能排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對(duì)于兩個(gè)關(guān)鍵字相等的記

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

36、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í)間復(fù)雜度的下限排序方法的時(shí)間復(fù)雜度的下限 本章討論的各種排序方法，除基數(shù)排序外，其它方法都是基于基于“比較關(guān)鍵字比較關(guān)鍵字”進(jìn)進(jìn)行排序的排序方法。行排序的排序方法。 可以證明， 這類排序法可能達(dá)到的最可能達(dá)到的最快的時(shí)間復(fù)雜度為快的時(shí)間復(fù)雜度為O(nlogn)。 (基數(shù)排序不

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

38、字”進(jìn)行排序進(jìn)行排序的的排序方法，可能達(dá)到的最快的時(shí)間復(fù)雜排序方法，可能達(dá)到的最快的時(shí)間復(fù)雜度為度為 O(nlogn)。70 對(duì)對(duì)外存中數(shù)據(jù)的讀外存中數(shù)據(jù)的讀/ /寫是以寫是以“數(shù)據(jù)塊數(shù)據(jù)塊”為單位進(jìn)行的為單位進(jìn)行的；讀讀/ /寫外存中一個(gè)寫外存中一個(gè)“數(shù)據(jù)塊數(shù)據(jù)塊”的數(shù)據(jù)所需要的時(shí)間為：的數(shù)據(jù)所需要的時(shí)間為： T TI/OI/O = t = tseek seek + t+ tlala + n + n t twmwm 其中其中 t tseek seek 為尋查時(shí)間為尋查時(shí)間( (查找該數(shù)據(jù)塊所在磁道查找該數(shù)據(jù)塊所在磁道) ) t tlala 為等待為等待( (延遲延遲) )時(shí)間時(shí)間 n n t

39、 twmwm 為傳輸數(shù)據(jù)塊中為傳輸數(shù)據(jù)塊中n n個(gè)記錄的時(shí)間。個(gè)記錄的時(shí)間。外部排序外部排序 待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，則待排序的記錄數(shù)量很大，不能一次裝入內(nèi)存，則無法利用前面討論的排序方法無法利用前面討論的排序方法71 按可用內(nèi)存大小，利用內(nèi)部排序方法，按可用內(nèi)存大小，利用內(nèi)部排序方法，構(gòu)造若干構(gòu)造若干( ( 記錄的記錄的) ) 有序子序列有序子序列，通常稱外，通常稱外存中這些記錄有序子序列為存中這些記錄有序子序列為 “歸并歸并”；外部排序的基本過程外部排序的基本過程由相對(duì)獨(dú)立的由相對(duì)獨(dú)立的兩個(gè)步驟兩個(gè)步驟組成：組成： 通過通過“歸并歸并”，逐步擴(kuò)大逐步擴(kuò)大 ( (記錄的記錄的) )有有序子序列的長度序子序列的長度，直至直至外存中