排序案例PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1排序案例排序案例10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 歸并排序歸并排序10.6 各種排序方法的綜合比較各種排序方法的綜合比較第1頁/共76頁10.1 概概 述述一、排序的定義一、排序的定義二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序三、內(nèi)部排序方法的分類三、內(nèi)部排序方法的分類第2頁/共76頁一、什么是排序？一、什么是排序？排序是計(jì)算機(jī)內(nèi)經(jīng)常進(jìn)行的一種操作，其目的是將一組“無序無序”的記錄序列調(diào)的記錄序列調(diào)整為整為“有序有序”的記錄序列。例如：將下列關(guān)鍵字序列52, 49, 80, 36, 14, 58, 61, 23, 9

2、7, 75調(diào)整為14, 23, 36, 49, 52, 58, 61 ,75, 80, 97第3頁/共76頁 一般情況下，假設(shè)含n個(gè)記錄的序列為 R1, R2, ， Rn 其相應(yīng)的關(guān)鍵字序列為 K1, K2, ，Kn 這些關(guān)鍵字相互之間可以進(jìn)行比較，即在它們之間存在著這樣一個(gè)關(guān)系 ： Kp1Kp2Kpn按此固有關(guān)系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作操作稱作排序排序。第4頁/共76頁二、內(nèi)部排序和外部排序二、內(nèi)部排序和外部排序若整個(gè)排序過程不需要訪問外存不需要訪問外存便能完成，則稱此類排序問題為內(nèi)部排內(nèi)部排序序； 反之，若參加排序的記錄數(shù)量很大， 整個(gè)序列的排序過程不

3、可能在內(nèi)存中 完成，則稱此類排序問題為外部排序外部排序。第5頁/共76頁三、內(nèi)部排序的方法三、內(nèi)部排序的方法內(nèi)部排序的過程是一個(gè)逐步擴(kuò)大逐步擴(kuò)大記錄的有序序列長度有序序列長度的過程。經(jīng)過一趟排序經(jīng)過一趟排序有序序列區(qū) 無 序 序 列 區(qū)有序序列區(qū)無 序 序 列 區(qū)第6頁/共76頁基于不同的“擴(kuò)大擴(kuò)大” 有序序列長度的方法，內(nèi)部排序方法方法，內(nèi)部排序方法大致可分下列幾種類型：插入類插入類交換類交換類選擇類選擇類 歸并類歸并類第7頁/共76頁待排記錄的數(shù)據(jù)類型定義如下待排記錄的數(shù)據(jù)類型定義如下:#define MAXSIZE 1000 / 待排順序表最大長度待排順序表最大長度typedef int

4、 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; / 順序表類型順序表類型第8頁/共76頁 10. 2 插插 入入 排排 序序第9頁/共76頁有序序列R1.i-1Ri無序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i無序序列 Ri+1.n

5、第10頁/共76頁實(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；第11頁/共76頁直接插入排序直接插入排序（基于順序查找）（基于順序查找）希爾排序希爾排序（基于逐趟縮小增量）（基于逐趟縮小增量） 不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述不同的具體實(shí)現(xiàn)方法導(dǎo)致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）第12頁/共76頁一、直接插入排序一、直接插入排序利

6、用 “順序查找順序查找”實(shí)現(xiàn)“在R1.i-1中查找查找Ri的插入位置”算法的實(shí)現(xiàn)要點(diǎn)：算法的實(shí)現(xiàn)要點(diǎn)：第13頁/共76頁 對于在查找過程中找到的那些關(guān)鍵字不小于Ri.key的記錄，并在查找的同時(shí)實(shí)現(xiàn)記錄向后移動；for (j=i-1; R0.keyRj.key; -j); Rj+1 = RjR0jRij= i-1上述循環(huán)結(jié)束后可以直接進(jìn)行“插入”插入位置插入位置第14頁/共76頁令 i = 2，3，, n, 實(shí)現(xiàn)整個(gè)序列的排序。for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; 第15頁/共76頁初始關(guān)鍵字序列

7、：初始關(guān)鍵字序列：【1313】，6 6，3 3，3131，9 9，2727，5 5， 1111第一次排序：第一次排序： 【6 6, , 1313】, 3, 31, 9, 27, 5, 11, 3, 31, 9, 27, 5, 11第二次排序：第二次排序： 【3 3, , 6, 136, 13】, 31, 9, 27, 5, 11, 31, 9, 27, 5, 11第三次排序：第三次排序： 【3, 6, 133, 6, 13，3131】, 9, 27, 5, 11, 9, 27, 5, 11第四次排序：第四次排序： 【3, 6, 3, 6, 9 9, , 1313，3131】, 27, 5, 1

8、1, 27, 5, 11第五次排序：第五次排序： 【3, 6, 9, 133, 6, 9, 13，2727, , 3131】, 5, 11, 5, 11第六次排序：第六次排序： 【3, 3, 5 5, , 6, 9, 136, 9, 13，27, 3127, 31】, 11, 11第七次排序：第七次排序： 【3, 5, 6, 9, 3, 5, 6, 9, 1111，1313，27, 3127, 31】 例：例：關(guān)鍵字序列關(guān)鍵字序列T=T=（1313，6 6，3 3，3131，9 9，2727，5 5，1111），請寫出直接插入排序的中間過程序列。），請寫出直接插入排序的中間過程序列。注：方括號

9、注：方括號 【 】中為已排序記錄的關(guān)鍵字，下劃橫線的中為已排序記錄的關(guān)鍵字，下劃橫線的 關(guān)鍵字關(guān)鍵字表示它對應(yīng)的記錄后移一個(gè)位置。表示它對應(yīng)的記錄后移一個(gè)位置。第16頁/共76頁void InsertionSort ( SqList &L ) / 對順序表 L 作直接插入排序。 for ( i=2; i=L.length; +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、/ 插入到正確位置第17頁/共76頁內(nèi)部排序的時(shí)間分析時(shí)間分析：實(shí)現(xiàn)內(nèi)部排序的基本操作基本操作有兩個(gè)：（2）“移動移動”記錄。（1）“比較比較”序列中兩個(gè)關(guān)鍵字的 大小；第18頁/共76頁對于直接插入排序：最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）：“比較”的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：“比較”的次數(shù)：112nni02) 1)(4() 1(2nnini“移動”的次數(shù)：“移動”的次數(shù)：2) 1)(2(2nnini第19頁/共76頁時(shí)間效率： 因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（01n-1

11、)O(n2)。其他情況下也要考慮移動元素的次數(shù)。 故時(shí)間復(fù)雜度為O(n2) 空間效率：僅占用1個(gè)緩沖單元O（1）算法的穩(wěn)定性：穩(wěn)定第20頁/共76頁 因?yàn)?R1.i-1 是一個(gè)按關(guān)鍵字有序的有序序列，則可以利用折半查找折半查找實(shí)現(xiàn)“在R1.i-1中查找查找Ri的插入位置”，如此實(shí)現(xiàn)的插入排序?yàn)檎郯氩逭郯氩迦肴肱判?。二、折半插入排序二、折半插入排序?1頁/共76頁void BiInsertionSort ( SqList &L ) / BInsertSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.r

12、j; / 記錄后移L.rhigh+1 = L.r0; / 插入第22頁/共76頁low = 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 low = m+1; / 插入點(diǎn)在高半?yún)^(qū)第23頁/共76頁14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh14 36 49 52 58 61 80 23 97 75ilowhighmhighmhighmlow例如:再如:插入位置插入位置L.rL.r第2

13、4頁/共76頁 三、希爾排序（又稱縮小增量排序）三、希爾排序（又稱縮小增量排序） 基本思想：對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。 所謂“宏觀”調(diào)整，指的是，“跳躍式”的插入排序。 具體做法為：第25頁/共76頁將記錄序列分成若干子序列，分別對每個(gè)子序列進(jìn)行插入排序。其中，d 稱為增量，它的值在排序過程中從大到小逐漸縮小，直至最后一趟排序減為 1。例如：將 n 個(gè)記錄分成 d 個(gè)子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 第26頁/共76頁例如：16 25 12 30 47 11 23 36

14、 9 18 31 第一趟希爾排序，設(shè)增量 d =511 23 12 9 18 16 25 36 30 47 31 第二趟希爾排序，設(shè)增量 d = 39 18 12 11 23 16 25 31 30 47 36第三趟希爾排序，設(shè)增量 d = 1 9 11 12 16 18 23 25 30 31 36 47 第27頁/共76頁void ShellInsert ( SqList &L, int 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

15、.rj+dk = L.r0; / 插入 / if / ShellInsert第28頁/共76頁void ShellSort (SqList &L, int dlta, int t) / 增量為dlta的希爾排序 for (k=0; k1) / while / BubbleSorti = n;i = lastExchangeIndex; / 本趟進(jìn)行過交換的 / 最后一個(gè)記錄的位置 if (Rj+1.key Rj.key) Swap(Rj, Rj+1); lastExchangeIndex = j; /記下進(jìn)行交換的記錄位置 /iffor (j = 1; j i; j+)lastExchange

16、Index = 1;第35頁/共76頁注意注意: :2. 一般情況下，每經(jīng)過一趟“起泡”，“i 減一”，但并不是每趟都如此。例如例如:523197825531579 89i=7i=6for (j = 1; j i; j+) if (Rj+1.key Rj.key) 13i=21. 起泡排序的結(jié)束條件為， 最后一趟沒有進(jìn)行最后一趟沒有進(jìn)行“交換記錄交換記錄”。第36頁/共76頁時(shí)間分析時(shí)間分析: :最好的情況（關(guān)鍵字在記錄序列中順序有序）：最好的情況（關(guān)鍵字在記錄序列中順序有序）： 只需進(jìn)行一趟起泡只需進(jìn)行一趟起泡“比較比較”的次數(shù)：的次數(shù)：最壞的情況（關(guān)鍵字在記錄序列中逆序有序）：最壞的情況（

17、關(guān)鍵字在記錄序列中逆序有序）： 需進(jìn)行需進(jìn)行n-1趟起泡趟起泡“比較比較”的次數(shù)：的次數(shù)：0“移動移動”的次數(shù)：的次數(shù)：“移動移動”的次數(shù)：的次數(shù)：n-12) 1() 1(2nnini2) 1(3) 1(32nnini第37頁/共76頁二、一趟快速排序（一次劃分）二、一趟快速排序（一次劃分）目標(biāo)：目標(biāo)：找一個(gè)記錄，以它的關(guān)鍵字作為“樞軸樞軸”，凡其關(guān)鍵字小于樞軸關(guān)鍵字小于樞軸的記錄均移動至該記錄之前移動至該記錄之前，反之，凡關(guān)鍵字大于關(guān)鍵字大于樞軸樞軸的記錄均移動至該記錄之后移動至該記錄之后。致使一趟排序一趟排序之后，記錄的無序序列Rs.t將分割成兩部分分割成兩部分：Rs.i-1和Ri+1.t

18、，且 Rj.key Ri.key Rj.key (sji-1) 樞軸樞軸 (i+1jt)。第38頁/共76頁52 49 80 36 14 58 61 97 23 75stlowhigh設(shè)設(shè) Rs=52 為樞軸為樞軸 將 Rhigh.key 和 樞軸的關(guān)鍵字進(jìn)行比較，要求Rhigh.key 樞軸的關(guān)鍵字 將 Rlow.key 和 樞軸的關(guān)鍵字進(jìn)行比較，要求Rlow.key 樞軸的關(guān)鍵字high23low80high14low52例如例如R052lowhighhighhighlow第39頁/共76頁 可見，經(jīng)過“一次劃分一次劃分” ，將關(guān)鍵字序列 52, 49, 80, 36, 14, 58, 6

19、1, 97, 23, 75 調(diào)整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在調(diào)整過程中，設(shè)立了兩個(gè)指針： low 和high，它們的初值分別為： s 和 t， 之后逐漸減小 high，增加 low，并保證 Rhigh.key52，和 Rlow.key52,否則進(jìn)行記錄的“交換”。第40頁/共76頁int Partition (RedType R, int low, int high) / Partition R0 = Rlow; pivotkey = Rlow.key; / 樞軸 while (lowhigh) while(low=pivotkey)

20、 - high; / 從右向左搜索Rlow = Rhigh;while (lowhigh & Rlow.key=pivotkey) + low; / 從左向右搜索Rhigh = Rlow;Rlow = R0; return low;第41頁/共76頁三、快速排序三、快速排序 首先對無序的記錄序列進(jìn)行“一次劃分一次劃分”，之后分別分別對分割所得兩個(gè)子序列“遞歸遞歸”進(jìn)行快速排序進(jìn)行快速排序。無 序 的 記 錄 序 列無序記錄子序列(1)無序子序列(2)樞軸樞軸一次劃分分別進(jìn)行快速排序第42頁/共76頁void QSort (RedType & R, int s, int t ) / 對記錄序列R

21、s.t進(jìn)行快速排序 if (s t-1) / 長度大于1 / QSortpivotloc = Partition(R, s, t); / 對 Rs.t 進(jìn)行一次劃分一次劃分QSort(R, s, pivotloc-1); / 對低子序列遞歸排序，pivotloc是樞軸位置是樞軸位置QSort(R, pivotloc+1, t); / 對高子序列遞歸排序第43頁/共76頁void QuickSort( SqList & L) / 對順序表進(jìn)行快速排序 QSort(L.r, 1, L.length); / QuickSort 第一次調(diào)用函數(shù) Qsort 時(shí)，待排序記錄序列的上、下界分別為 1 和

22、L.length。第44頁/共76頁四、快速排序的時(shí)間分析四、快速排序的時(shí)間分析時(shí)間效率：O(nlog2n) 因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O（log2n）因?yàn)檫f歸要用棧(存每層low，high和pivot)穩(wěn) 定 性： 不穩(wěn)定 因?yàn)橛刑S式交換。第45頁/共76頁 若待排記錄的初始狀態(tài)為按關(guān)鍵字有序若待排記錄的初始狀態(tài)為按關(guān)鍵字有序時(shí)，快速排序?qū)⑼懟癁槠鹋菖判驎r(shí)，快速排序?qū)⑼懟癁槠鹋菖判?，其時(shí)間復(fù)雜度為O(n2)。 為避免出現(xiàn)這種情況，需在進(jìn)行一次劃分之前，進(jìn)行“予處理予處理”，即： 先對 R(s).key, R(t).key 和 R(s+t)/2.key，進(jìn)行相互比較，然后取取關(guān)鍵

23、字為 “三者之中三者之中”的記錄為樞軸為樞軸記錄。第46頁/共76頁10.4 堆堆 排排 序序簡簡 單單 選選 擇擇 排排 序序堆堆 排排 序序第47頁/共76頁一、簡單選擇排序一、簡單選擇排序假設(shè)排序過程中，待排記錄序列的狀態(tài)為：有序序列R1.i-1 無序序列 Ri.n 第 i 趟簡單選擇排序從中選出關(guān)鍵字最小的記錄有序序列R1.i無序序列 Ri+1.n第48頁/共76頁例：例：關(guān)鍵字序列關(guān)鍵字序列T= T= （2121，2525，4949，2525* *，1616，0808），請給出簡單選擇排序的具體實(shí)現(xiàn)過程。），請給出簡單選擇排序的具體實(shí)現(xiàn)過程。原始序列：原始序列： 21，25，49，2

24、5*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16, 49，25*，25，2108，16, 21，25*，25，4908，16, 21，25*，25，4908，16, 21，25*，25，49第49頁/共76頁簡單選擇排序的算法描述如下：void SelectSort (Elem R, int n ) / 對記錄序列R1.n作簡單選擇排序。 for (i=1; in; +i) / 選擇第 i 小的記錄，并交換到位 / SelectSortj = SelectMinKey(R, i); / 在 Ri.n 中選擇關(guān)鍵字最小的記錄if (

25、i!=j) RiRj; / 與第 i 個(gè)記錄交換第50頁/共76頁時(shí)間性能分析時(shí)間性能分析時(shí)間效率：時(shí)間效率： O(n2)雖移動次數(shù)較少，雖移動次數(shù)較少，但比較次數(shù)仍多。但比較次數(shù)仍多。 空間效率空間效率：O（1）沒有附加單元（沒有附加單元（僅用到僅用到1個(gè)個(gè)temp)算法的穩(wěn)定性：算法的穩(wěn)定性：不穩(wěn)定不穩(wěn)定第51頁/共76頁10.5 歸歸 并并 排排 序序歸并排序的過程基于下列基本思想基本思想進(jìn)行： 將兩個(gè)或兩個(gè)以上的有序子序列 “歸并” 為一個(gè)有序序列。第52頁/共76頁在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰位置相鄰的記錄有序子序列歸并為一個(gè)一個(gè)記錄的有序序列。有有

26、序序 序序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n這個(gè)操作對順序表而言，是輕而易舉的。第53頁/共76頁void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 將有序的記錄序列 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+; 第54頁/共76頁if (i=m)

27、 TRk.n = SRi.m; / 將剩余的 SRi.m 復(fù)制到 TRif (j=n) TRk.n = SRj.n; / 將剩余的 SRj.n 復(fù)制到 TR第55頁/共76頁歸并排序的算法歸并排序的算法如果記錄無序序列 Rs.t 的兩部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分別按關(guān)鍵字有序，則利用上述歸并算法很容易將它們歸并成整個(gè)記錄序列是一個(gè)有序序列。 由此，應(yīng)該先分別對這兩部分進(jìn)行 2-路歸并排序。第56頁/共76頁例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 52, 2380 52 23,

28、 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23第57頁/共76頁void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 將SRs.t 歸并排序?yàn)?TR1s.t if (s= =t) TR1s=SRs; else / Msort 第58頁/共76頁m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 遞歸地將SRs.m歸并為有序的TR2s.mMsort (SR, TR2, m+1,

29、t); /遞歸地SRm+1.t歸并為有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.t第59頁/共76頁void MergeSort (SqList &L) / 對順序表 L 作2-路歸并排序 MSort(L.r, L.r, 1, L.length); / MergeSort第60頁/共76頁因?yàn)樵谶f歸的歸并排序算法中，函數(shù)因?yàn)樵谶f歸的歸并排序算法中，函數(shù)Merge( )做一做一趟兩路歸并排序，需要調(diào)用趟兩路歸并排序，需要調(diào)用merge ( )函數(shù)函數(shù) n/(2len) O(n/len) 次，而每次次，而每次mer

30、ge( )要執(zhí)行要執(zhí)行比較比較O(len)次，另外整個(gè)歸并過程有次，另外整個(gè)歸并過程有 log2n “層層” ，所以算法總的時(shí)間復(fù)雜度為，所以算法總的時(shí)間復(fù)雜度為O(nlog2n)。因?yàn)樾枰粋€(gè)與原始序列同樣大小的輔助序列。因?yàn)樾枰粋€(gè)與原始序列同樣大小的輔助序列。這正是此算法的缺點(diǎn)。這正是此算法的缺點(diǎn)。第61頁/共76頁10.6 各種排序方法的綜合比較各種排序方法的綜合比較第62頁/共76頁一、時(shí)間性能一、時(shí)間性能1. 平均的時(shí)間性平均的時(shí)間性能能基數(shù)排序基數(shù)排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(nlog2n)：快速排序、堆排序和歸并排序快速排序、堆排序和歸并排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n

31、2)：直接插入排序、起泡排序和直接插入排序、起泡排序和簡單選擇排序簡單選擇排序時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n):第63頁/共76頁2. 當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)當(dāng)待排記錄序列按關(guān)鍵字順序有序時(shí)3. 簡單選擇排序、堆排序和歸并排序簡單選擇排序、堆排序和歸并排序的時(shí)間性能不隨不隨記錄序列中關(guān)鍵字的分布而改變。 直接插入排序直接插入排序和起泡排序起泡排序能達(dá)到O(n)的時(shí)間復(fù)雜度， 快速排序快速排序的時(shí)間性能蛻化為O(n2) 。第64頁/共76頁二、空間性能二、空間性能指的是排序過程中所需的輔助空間大小1. 所有的簡單排序方法簡單排序方法(包括：直接插入、起泡和簡單選擇) 和堆排序堆排序的空間復(fù)雜度為為O(1)；2. 快速排序?yàn)榭焖倥判驗(yàn)镺(log2n)，為遞歸程序執(zhí)行過程中，棧所需的輔助空間；第65頁/共76頁3. 歸并排序歸并排序所需輔助空間最多，其空間復(fù)雜度為 O(n);4. 鏈?zhǔn)交鶖?shù)排序鏈?zhǔn)交鶖?shù)排序需附設(shè)隊(duì)列首尾指針，則空間復(fù)雜度為 O(rd)。第66頁/共76頁三、排序方法的穩(wěn)定性能三、排序方法的穩(wěn)定性能 1. 穩(wěn)定的排序方法指的是，對于兩個(gè)關(guān)鍵字相等的記錄，它們在序列中的相對位置，在排序之前和經(jīng)過排序之后，沒有改變。 2. 當(dāng)對多關(guān)鍵字的記錄序列進(jìn)行LSD方法排序時(shí)，必須采用穩(wěn)定的排序方法。排序之前