1、數(shù) 據(jù) 結 構,第 10 章 排序,概述,10.1 概述 10.2 插入排序 10.3 快速排序 10.4 選擇排序 10.5 歸并排序 10.6 基數(shù)排序 10.7 各種內(nèi)部排序方法的比較,10.1 概述,一、什么是排序？,排序是計算機內(nèi)經(jīng)常進行的一種操作,其目的是將一組無序的記錄序列調整為“有序”的記錄序列。,例如：將下列關鍵字序列,52, 49, 80, 36, 14, 58, 61, 23, 97, 75,調整為,14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,一般情況下， 假設含n個記錄的序列為 R1, R2, ， Rn 其相應的關鍵字序列為 K1, K

2、2, ，Kn ,10.1 概述,這些關鍵字相互之間可以進行比較，即在它們之間存在著這樣一個關系： Kp1Kp2Kpn,按此固有關系將上式記錄序列重新排列為 Rp1, Rp2, ，Rpn 的操作稱作排序。,數(shù)據(jù)表(data list): 它是待排序數(shù)據(jù)對象的有限集合。,10.1 概述,主關鍵字(key):是數(shù)據(jù)元素中的某個數(shù)據(jù)項。如果某個數(shù)據(jù) 項可以唯一地確定一個數(shù)據(jù)元素，就將其稱為主關鍵字； 否則，稱為次關鍵字。,學號 姓名 專業(yè) 年齡 01 王洪 計算機 17 06 余斌 計算機 19 07 鞏力 計算機 17 02 孫文 計算機 18 04 李輝 計算機 20 03 謝軍 計算機 18 0

3、5 沈祥福 計算機 25 08 王輝 計算機 18,10.1 概述,排序方法的穩(wěn)定性: 如果在對象序列中有兩 個對象ri和rj, 它們的排序碼 ki = kj , 在排序之前, 對象ri排在rj前面。如果在排序之后, 對象ri仍在對象rj的前面, 則稱這個排序方法是穩(wěn)定的, 否則稱這個排序方法是不穩(wěn)定的。 內(nèi)排序與外排序: 內(nèi)排序是指在排序期間數(shù)據(jù)對象全部存放在內(nèi)存的排序；外排序是指在排序期間全部對象個數(shù)太多，不能同時存放在內(nèi)存，必須根據(jù)排序過程的要求，不斷在內(nèi)、外存之間移動的排序。,10.1 概述,內(nèi)部排序的方法,內(nèi)部排序的過程是一個逐步擴大記錄的有序序列長度的過程。,經(jīng)過一趟排序,有序序列

4、區(qū),無 序 序 列 區(qū),有序序列區(qū),無 序 序 列 區(qū),排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)與數(shù)據(jù)移動次數(shù)來衡量。,10.1 概述,內(nèi)排序分類,依不同原則 插入排序、交換排序、選擇排序、歸并排序、和基數(shù)排序等。 依所須工作量 簡單排序-時間復雜度o(n2) 先進排序方法-時間復雜度o(n logn) 基數(shù)排序-時間復雜度o(d*n),10.2 插入排序,有序序列R1.i-1,Ri,無序序列 Ri.n,有序序列R1.i,無序序列 Ri+1.n,基本思想: 每步將一個待排序的對象, 按其排序碼大小, 插入到前面已經(jīng)排好序的一組對象的

5、適當位置上, 直到對象全部插入為止。,10.2 插入排序,實現(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,10.2 插入排序,直接插入排序（基于順序查找）,表插入排序（基于鏈表存儲）,不同的具體實現(xiàn)方法導致不同的算法描述,折半插入排序（基于折半查找）,希爾排序（基于逐趟縮小增量）,10.2 插入排序,直接插入排序,基本思想: 當插入第i (i 1) 個對象時, 前面的V0, V1, , Vi-1已經(jīng)排好序。這時, 用

6、Vi的排序碼與Vi-1, Vi-2, 的排序碼順序進行比較, 找到插入位置即將Vi插入, 原來位置上的對象向后順移。,10.2 插入排序,直接插入排序,從Ri-1起向前進行順序查找，監(jiān)視哨設置在R0；,R0 = Ri; / 設置“哨兵”,循環(huán)結束表明Ri的插入位置為 j +1,R0,Ri,for (j=i-1; R0.keyRj.key; -j); / 從后往前找,插入位置,對于在查找過程中找到的那些關鍵字不小于Ri.key的記錄，并在查找的同時實現(xiàn)記錄向后移動；,for (j=i-1; R0.keyRj.key; -j) Rj+1 = Rj,R0,Ri,上述循環(huán)結束后可以直接進行“插入”,插

7、入位置,10.2 插入排序,直接插入排序,10.2 插入排序,直接插入排序,令 i = 2，3，, n, （i=1時元素自身有序）實現(xiàn)整個序列的排序。,for ( i=2; i=n; +i ) if (Ri.keyRi-1.key) 在 R1.i-1中查找Ri的插入位置; 插入Ri ; ,10.2 插入排序,直接插入排序,void InsertionSort ( SqList / 插入到正確位置 / InsertSort,10.2 插入排序,直接插入排序,算法分析,設待排序對象個數(shù)為 n, 則該算法的主程序執(zhí)行n-1趟。 排序碼比較次數(shù)和對象移動次數(shù)與對象排序碼的初始排列有關。 最好情況下,

8、排序前對象已按排序碼從小到大有序, 每趟只需與前面有序對象序列的最后一個對象比較1次, 移動0次對象, 總的排序碼比較次數(shù)為 n-1。,10.2 插入排序,直接插入排序,最壞情況下, 第 i 趟時第 i 個對象必須與前面 i 個對象都做排 序碼比較, 并且每做1次比較就要做1次數(shù)據(jù)移動。則總排序 碼比較次數(shù)KCN和對象移動次數(shù)RMN分別為 在平均情況下的排序碼比較次數(shù)和對象動次數(shù)約為 n2/4。因此，直接插入排序的時間復雜度為 o(n2)。 直接插入排序是一種穩(wěn)定的排序方法。,10.2 插入排序,折半插入排序,基本思想: 因為 R1.i-1 是一個按關鍵字有序的有序序列，則可以利用折半查找實現(xiàn)

9、“在R1.i-1中查找Ri的插入位置”，如此實現(xiàn)的插入排序為折半插入排序。,10.2 插入排序,折半插入排序,void BiInsertionSort ( SqList i=L.length; +i ) / for,L.r0 = L.ri; / 將 L.ri 暫存到 L.r0,for ( j=i-1; j=high+1; -j ) L.rj+1 = L.rj; / 記錄后移,L.rhigh+1 = L.r0; / 插入,10.2 插入排序,折半插入排序,low = 1; high = i-1; while (low=high) ,m = (low+high)/2; / 折半,if (L.r0.

10、key L.rm.key) high = m-1; / 插入點在低半?yún)^(qū) else low = m+1; / 插入點在高半?yún)^(qū),（接上頁）在 L.r1.i-1中折半查找插入位置；,10.2 插入排序,折半插入排序,i,low,high,m,m,low,low,m,high,i,low,high,m,high,m,high,m,low,例如:,再如:,插入 位置,插入 位置,10.2 插入排序,折半插入排序,折半搜索比順序搜索查找快, 所以折半插入排序就平均性能來說比直接插入排序要快。 它所需的排序碼比較次數(shù)與待排序對象序列的初始排列無關, 僅依賴于對象個數(shù)。在插入第 i 個對象時, 需要經(jīng)過 lo

11、g2i +1 次排序碼比較, 才能確定它應插入的位置。因此, 將 n 個對象(為推導方便, 設為 n=2k )用折半插入排序所進行的排序碼比較次數(shù)為：,算法分析,10.2 插入排序,折半插入排序,當 n 較大時, 總排序碼比較次數(shù)比直接插入排序的最壞情況要好得多, 但比其最好情況要差。 在對象的初始排列已經(jīng)按排序碼排好序或接近有序時, 直接插入排序比折半插入排序執(zhí)行的排序碼比較次數(shù)要少。折半插入排序的對象移動次數(shù)與直接插入排序相同, 依賴于對象的初始排列。 折半插入排序是一個穩(wěn)定的排序方法。 折半插入排序的時間復雜度為o(n2)。,10.2 插入排序,表插入排序,為了減少在排序過程中進行的“移

12、動”記錄的操作，必須改變排序過程中采用的存儲結構。利用靜態(tài)鏈表進行排序，并在排序完成之后，一次性地調整各個記錄相互之間的位置，即將每個記錄都調整到它們所應該在的位置上。,10.2 插入排序,表插入排序,1,例：關鍵字序列 T=(21，25，49，25*，16，08），請寫出表插入排序的具體實現(xiàn)過程。,解：假設該序列（結構類型)已存入一維數(shù)組V7中，將V0作為表頭結點。則算法執(zhí)行過程為：,指向第1個元素,指向頭結點,初態(tài) i=1,i=2,i=3,i=4,i=5,i=6,0,3,4,5,6,5,0,3,1,0,2,*表示后一個25,10.2 插入排序,表插入排序,算法中使用了三個指針: 其中：p指

13、示第i個記錄的當前位置； i指示第i個記錄應在的位置； q指示第i+1個記錄的當前位置,如何在排序之后調整記錄序列？,void Arrange ( Elem SL , int n ) p = SL0.next; / p指示第一個記錄的當前位置 for ( i=1; in; +i ) while (pi) p = SLp.next; q = SLp.next; / q指示尚未調整的表尾 if ( p!= i ) SLpSLi; / 交換記錄，使第i個記錄到位 SLi.next = p; / 指向被移走的記錄， /if p = q; / p指示尚未調整的表尾，準備找第i+1個記錄 /for / A

14、rrange,10.2 插入排序,表插入排序,10.2 插入排序,希爾排序,基本思想：設待排序對象序列有 n 個對象, 首先取一個整數(shù) gap n 作為間隔, 將全部對象分為 gap 個子序列, 所有距離為 gap 的對象放在同一個子序列中, 在每一個子序列中分別施行直接插入排序。然后縮小間隔 gap, 例如取 gap = gap/2，重復上述的子序列劃分和排序工作。直到最后取 gap = 1, 將所有對象放在同一個序列中排序為止。,10.2 插入排序,希爾排序,i = 3,Gap = 3,0 1 2 3 4 5,i = 2,Gap = 2,21,08,25,49,25*,16,i = 1,G

15、ap = 1,希爾排序過程,21,25*25,1649,08,21,08,2516,25*,49,10.2 插入排序,希爾排序,void ShellInsert ( SqList / 插入 / if / ShellInsert,10.2 插入排序,希爾排序,void ShellSort (SqList /一趟增量為dltak的插入排序 / ShellSort,10.2 插入排序,希爾排序,開始時 gap 的值較大, 子序列中的對象較少, 排序速度較快; 隨著排序進展, gap 值逐漸變小, 子序列中對象個數(shù)逐漸變多, 由于前面大多數(shù)對象已基本有序, 所以排序速度仍然很快。 Gap的取法有多種。

16、 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。 對特定的待排序對象序列，可以準確地估算排序碼的比較次數(shù)和對象移動次數(shù)。 希爾排序所需的比較次數(shù)和移動次數(shù)約為n 1.3 當n趨于無窮時可減少到n(log2 n)2,算法分析,10.3 快速排序,基本思想是兩兩比較待排序對象的排序碼,如發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之,直到所有對象都排好序為止。,10.3 快速排序,起泡排序,基本方法設待排序對象序列中的對象個數(shù)為n。一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄地關鍵字，如果發(fā)生逆序，則交換之，其結果是這n-i+1個記錄中，

17、關鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。,10.3 快速排序,起泡排序,假設在排序過程中，記錄序列R1.n的狀態(tài)為：,第 i 趟起泡排序,無序序列R1.n-i+1,有序序列 Rn-i+2.n,n-i+1,無序序列R1.n-i,有序序列 Rn-i+1.n,比較相鄰記錄，將關鍵字最大的記錄交換到 n-i+1 的位置上,10.3 快速排序,起泡排序,21,08,25,49,25,16,21,49,25,25,16,08,21,49,25,25,16,08,初 始 關 鍵 字,第 一 趟 排 序,第 四 趟 排 序,第 二 趟 排 序,第 三 趟 排 序,21,49,25,25,

18、16,08,第 五 趟 排 序,起泡排序的過程,10.3 快速排序,起泡排序,起泡排序的算法 typedef int SortData; void BubbleSort ( SortData V , int n ) int i = 1; int exchange = 1; while ( i = i; j- ) if ( Vj-1 Vj ) /逆序 Swap ( Vj-1, Vj ); /交換 exchange = 1; /標志置為1,有交換 i+; ,10.3 快速排序,起泡排序,時間分析,第i趟對待排序對象序列Vi-1,Vi,Vn-1進行排序, 結果將該序列中排序碼最小的對象交換到序列的第

19、一個位置(i-1), 其它對象也都向排序的最終位置移動。 最多做n-1趟起泡就能把所有對象排好序。 在對象的初始排列已經(jīng)按排序碼從小到大排好序時,此算法只執(zhí)行一趟起泡,做n-1次排序碼比較,不移動對象。這是最好的情形。,最壞的情形是算法執(zhí)行n-1趟起泡,第i趟 (1 i n) 做 n- i 次排序碼比較, 執(zhí)行 n-i 次對象交換。這樣在最壞情形下總的排序碼比較次數(shù)KCN和對象移動次數(shù)RMN為：,起泡排序是一個穩(wěn)定的排序方法。,10.3 快速排序,起泡排序,10.3 快速排序,一趟快速排序,目標：找一個記錄，以它的關鍵字作為“樞軸”，凡其關鍵字小于樞軸的記錄均移動至該記錄之前，反之，凡關鍵字大

20、于樞軸的記錄均移動至該記錄之后。,致使一趟排序之后，記錄的無序序列Rs.t將分割成兩部分：Rs.i-1和Ri+1.t, 且 Rj.key Ri.key Rj.key (sji-1) 樞軸 (i+1jt),10.3 快速排序,一趟快速排序,設 Rs=52 為樞軸暫存在R0的位置上,將 Rhigh.key 和 樞軸的關鍵字進行比較，要求Rhigh.key 樞軸的關鍵字,將 Rlow.key 和 樞軸的關鍵字進行比較，要求Rlow.key 樞軸的關鍵字,23,80,14,52,例如,R0,52,10.3 快速排序,一趟快速排序,可見，經(jīng)過“一次劃分” ，將關鍵字序列 52, 49, 80, 36,

21、14, 58, 61, 97, 23, 75 調整為: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75,在調整過程中，設立了兩個指針: low 和high，它們的初值分別為: s 和 t,之后逐漸減小 high，增加 low，并保證 Rhigh.key52，和 Rlow.key52,否則進行記錄的“交換”。,10.3 快速排序,一趟快速排序,int Partition (RedType R, int low, int high) / Partition,R0 = Rlow; pivotkey = Rlow.key; / 樞軸,while (lowhigh) ,w

22、hile(low=pivotkey) - high; / 從右向左搜索,Rlow = Rhigh;,while (lowhigh / 從左向右搜索,Rhigh = Rlow;,Rlow = R0; return low;,10.3 快速排序,快速排序,首先對無序的記錄序列進行“一次劃分”，之后分別對分割所得兩個子序列“遞歸”進行快速排序。,無 序 的 記 錄 序 列,無序記錄子序列(1),無序子序列(2),樞軸,一次劃分,分別進行快速排序,10.3 快速排序,快速排序,void QSort (RedType / 對 Rs.t 進行一次劃分,QSort(R, s, pivotloc-1); /

23、對低子序列遞歸排序，pivotloc是樞軸位置,QSort(R, pivotloc+1, t); / 對高子序列遞歸排序,10.3 快速排序,快速排序,void QuickSort( SqList / QuickSort,第一次調用函數(shù) Qsort 時，待排序記錄序列的上、下界分別為 1 和 L.length。,10.3 快速排序,快速排序,快速排序的過程,21,08,25,49,25*,16,初始關鍵字,08,25,49,25*,16,21,08,25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,08,25,49,25*,16,21,pivotkey,

24、一次交換,二次交換,三次交換,四次交換,完成一趟排序,i,j,i,j,j,i,10.3 快速排序,快速排序,08,25,49,25*,16,21,完成一趟排序,分別進行快速排序,08,25,49,25*,16,21,有序序列,08,25,49,25*,16,21,10.3 快速排序,快速排序,算法quicksort是一個遞歸的算法, 其遞歸樹如圖所示。 算法partition利用序列第一個對象作為基準，將整個序列劃分為左右兩個子序列。算法中執(zhí)行了一個循環(huán), 只要是排序碼小于基準對象排序碼的對象都移到序列左側, 最后基準對象安放到位, 函數(shù)返回其位置。,10.3 快速排序,快速排序,算法分析,快

25、速排序的趟數(shù)取決于遞歸樹的高度。 如果每次劃分對一個對象定位后, 該對象的左側子序列與右側子序列的長度相同, 則下 一步將是對兩個長度減半的子序列進行排序, 這是最理想的情況。 在 n個元素的序列中, 對一個對象定位所需時間為 O(n)。若設 t (n) 是對 n 個元素的序列進行排序所需的時間, 而且每次對一個對象正確定位后, 正好把序列劃分為長度相等的兩個子序列, 此時, 總的計算時間為 O(n log2n ),可以證明, 函數(shù)quicksort的平均計算時間也是O(nlog2n)。實驗結果表明: 就平均計算時間而言, 快速排序是所有內(nèi)排序方法中最好的一個。 快速排序是遞歸的，需要有一個棧

26、存放每層遞歸調用時的指針和參數(shù)。 快速排序是一種不穩(wěn)定的排序方法。,10.3 快速排序,快速排序,10.4 選擇排序,基本思想 每一趟 (例如第 i 趟, i = 1,2, , n-2) 在后面 n-i +1個待排序記錄中選出排序碼最小的記錄, 作為有序序列中的第 i 個記錄。待到第n-1 趟作完, 待排序記錄只剩下1個,就不用再選了。,10.4 選擇排序,直接選擇排序是一種簡單的排序方法, 它的基本步驟是： 在一組對象 ViVn 中選擇具有最小排序碼的對象； 若它不是這組對象中的第一個對象, 則將它與這組對象中的第一個對象對調; 在這組對象中剔除這個具有最小排序碼的對象。在剩下的對象Vi+1

27、Vn中重復執(zhí)行第、步, 直到剩余對象只有一個為止。,直接選擇排序,10.4 選擇排序,直接選擇排序,假設排序過程中，待排記錄序列的狀態(tài)為：,有序序列R1.i-1,無序序列 Ri.n,第 i 趟 簡單選擇排序,從中選出 關鍵字最小的記錄,有序序列R1.i,無序序列 Ri+1.n,10.4 選擇排序,直接選擇排序,直接選擇排序的過程,10.4 選擇排序,直接選擇排序,最小者 25* 無交換,10.4 選擇排序,直接選擇排序,簡單選擇排序的算法描述如下：,void SelectSort (Elem R, int n ) / 對記錄序列R1.n作簡單選擇排序。 for (i=1; in; +i) /

28、選擇第 i 小的記錄，并交換到位 / SelectSort,j = SelectMinKey(R, i); / 在 Ri.n 中選擇關鍵字最小的記錄,if (i!=j) RiRj; / 與第 i 個記錄交換,10.4 選擇排序,直接選擇排序,直接選擇排序的排序碼比較次數(shù) KCN 與對象的初始排列無關。設整個待排序對象序列有 n 個對象, 則第 i 趟選擇具有最小排序碼對象所需的比較次數(shù)總是 n-i-1 次。總的排序碼比較次數(shù)為,對象的移動次數(shù)與對象序列的初始排列有關。當這組對象的初始狀態(tài)是按其排序碼從小到大有序的時候, 對象的移動次數(shù)RMN = 0，達到最少。 最壞情況是每一趟都要進行交換，總

29、的對象移動次數(shù)為 RMN = 3(n-1)。 直接選擇排序是一種不穩(wěn)定的排序方法。,10.4 選擇排序,堆排序,堆 ( Heap )設有一個關鍵字集合，按完全二叉樹的順序存儲方式存放在一個一維數(shù)組中。對它們從根開始，自頂向下，同一層自左向右從 0開始連續(xù)編號。若滿足 Ki K2i+1 通過一系列的對象交換和重新調整堆進行排序。,10.4 選擇排序,堆排序,初始大頂堆的建立過程,3,初始排序碼集合,i = 2 時的局部調整,21,25,25*,49,16,08,0,1,2,3,4,5,i,49,25,25*,16,21,08,0,2,5,4,3,1,10.4 選擇排序,堆排序,10.4 選擇排序

30、,堆排序,基于初始堆(大頂堆)進行堆排序,最大堆堆頂V0具有最大的排序碼, 將V0與 Vn-1對調, 把具有最大排序碼的對象交換到最后, 再對前面的n-1個對象, 使用堆的調整算法, 重新建立最大堆, 具有次最大排序碼的對象又上浮到V0位置。 再對調V0和Vn-2,調用堆的調整算法,對前n-2個對象重新調整，。 如此反復執(zhí)行，最后得到全部排序好的對象序列。這個算法即堆排序算法，,10.4 選擇排序,堆排序,49 25 21 25* 16 08,08 25 21 25* 16 49,交換 0 號與 5 號對象, 5 號對象就位,初始最大堆,基于初始堆進行堆排序,10.4 選擇排序,堆排序,08,

31、16,49,08,25,49,25 25* 21 08 16 49,16 25* 21 08 25 49,交換 0 號與 4 號對象, 4 號對象就位,從 0 號到 4 號 重新 調整為最大堆,10.4 選擇排序,堆排序,25* 16 21 08 25 49,08 16 21 25* 25 49,交換 0 號與 3 號對象, 3 號對象就位,從 0 號到 3 號 重新 調整為最大堆,10.4 選擇排序,堆排序,21 16 08 25* 25 49,08 16 21 25* 25 49,交換 0 號與 2 號對象, 2 號對象就位,從 0 號到 2 號 重新 調整為最大堆,10.4 選擇排序,堆

32、排序,16,08,25*,21,25,49,0,1,2,3,4,5,08,16,25*,25,21,49,0,2,5,4,3,1,16 08 21 25* 25 49,08 16 21 25* 25 49,交換 0 號與 1 號對象, 1 號對象就位,從 0 號到 1 號 重新 調整為最大堆,10.4 選擇排序,堆排序,void HeapSort ( HeapType i0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大頂堆,for ( i=H.length; i1; -i ) H.r1H.ri; / 將堆頂記錄和當前未經(jīng)排序子序列 / H.r1.i中最

33、后一個記錄相互交換 HeapAdjust(H.r, 1, i-1); / 對 H.r1 進行篩選 ,堆排序的算法,10.4 選擇排序,堆排序,void HeapAdjust (RcdType / 暫存 Rs,for ( j=2*s; j=m; j*=2 ) / j 初值指向左孩子 自上而下的篩選過程; ,Rs = rc; / 將調整前的堆頂記錄插入到 s 位置,10.4 選擇排序,堆排序,if ( rc.key = Rj.key ) break; / 再作“根”和“子樹根”之間的比較， / 若“=”成立，則說明已找到 rc 的插 / 入位置 s ，不需要繼續(xù)往下調整,Rs = Rj; s =

34、j; / 否則記錄上移，尚需繼續(xù)往下調整,if ( jm / 左/右“子樹根”之間先進行相互比較 / 令 j 指示關鍵字較大記錄的位置,自上而下的篩選過程;,10.4 選擇排序,堆排序,建堆是一個從下往上進行“篩選”的過程。,40,55,49,73,81,64,36,12,27,98,例如: 排序之前的關鍵字序列為,12,36,81,73,49,98,81,73,55,現(xiàn)在，左/右子樹都已經(jīng)調整為堆，最后只要調整根結點，使整個二叉樹是個“堆”即可。,98,49,40,64,36,12,27,10.4 選擇排序,堆排序,堆排序的時間復雜度分析：,1. 對深度為 k 的堆，“篩選”所需進行的關鍵字

35、比較的次數(shù)至多為2(k-1);,2. 對 n 個關鍵字，建成深度為 h (=log2n+1) 的堆，所需進行的關鍵字比較的次數(shù)至多 4n;,3. 調整“堆頂” n-1 次，總共進行的關鍵字比較的次數(shù)不超過 2 (log2(n-1)+ log2(n-2)+ +log22) 2n(log2n),因此，堆排序的時間復雜度為O(nlogn),10.5 歸并排序,歸并排序的過程基于下列基本思想進行：將兩個或兩個以上的有序表合并成一個新的有序表。 兩路歸并 (2-way merging)原始序列initList 中兩個有序表 initListl initListm和initListm+1 initList

36、n，它們可歸并成一個有序表, 存于另一對象序列mergedList的 l n 中。,10.5 歸并排序,2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列,歸并為一個記錄的有序序列。,有 序 序 列 Rl.n,有序子序列 Rl.m,有序子序列 Rm+1.n,這個操作對順序表而言，是輕而易舉的。,10.5 歸并排序,void Merge (RcdType SR, RcdType i=m , ,10.5 歸并排序,if (i=m) TRk.n = SRi.m; / 將剩余的 SRi.m 復制到 TR,if (j=n) TRk.n = SRj.n; / 將剩余的 SRj.n 復制到 TR,10.5

37、歸并排序,迭代的歸并排序算法,迭代的歸并排序算法就是利用兩路歸并過程進行排序的。其基本思想是： 假設初始對象序列有 n 個對象，首先把它看成是 n 個長度為 1 的有序子序列 (歸并項)，先做兩兩歸并，得到 n / 2 個長度為 2 的歸并項 (如果 n 為奇數(shù)，則最后一個有序子序列的長度為1)；再做兩兩歸并，如此重復，最后得到一個長度為 n 的有序序列。,10.5 歸并排序,迭代的歸并排序算法,21,25,25*,25*,93,62,72,08,37,16,54,49,21,25,49,62,93,08,72,16,37,54,21,25,25*,49,08,62,72,93,16,37,5

38、4,08,08,21,16,25,21,25*,25,49,25*,62,37,72,49,93,54,16,37,54,62,72,93,len=1,len=2,len=4,len=8,len=16,10.5 歸并排序,void Msort ( RcdType SR, RcdType else / Msort, ,10.5 歸并排序,m = (s+t)/2; / 將SRs.t平分為SRs.m和SRm+1.t,Msort (SR, TR2, s, m); / 遞歸地將SRs.m歸并為有序的TR2s.m Msort (SR, TR2, m+1, t); /遞歸地SRm+1.t歸并為有序的TR2m

39、+1.t,Merge (TR2, TR1, s, m, t); / 將TR2s.m和TR2m+1.t歸并到TR1s.t,10.5 歸并排序,void MergeSort (SqList / MergeSort,容易看出，對 n 個記錄進行歸并排序的時間復雜度為(nlogn)。即： 每一趟歸并的時間復雜度為 O(n)， 總共需進行 log2n 趟。,10.6 基數(shù)排序,基數(shù)排序是一種借助“多關鍵字排序”的思想來實現(xiàn)“單關鍵字排序”的內(nèi)部排序算法。,多關鍵字的排序,鏈式基數(shù)排序,10.6 基數(shù)排序,多關鍵字的排序,n 個記錄的序列 R1, R2, ，Rn 對關鍵字 (Ki0, Ki1,Kid-1)

40、 有序是指：,其中: K0 被稱為 “最主”位關鍵字，,Kd-1 被稱為 “最次”位關鍵字。,對于序列中任意兩個記錄 Ri 和 Rj (1ijn) 都滿足下列有序關系： (Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1),10.6 基數(shù)排序,多關鍵字的排序,實現(xiàn)多關鍵字排序通常有兩種作法:,最低位優(yōu)先LSD法：,最高位優(yōu)先MSD法：,先對K0進行排序，并按 K0 的不同值將記錄序列分成若干子序列之后，分別對 K1 進行排序，.， 依次類推，直至最后對最次位關鍵字排序完成為止。,先對 Kd-1 進行排序，然后對 Kd-2 進行排序，依次類推，直至對最主位關鍵字 K0 排序

41、完成為止。,10.6 基數(shù)排序,多關鍵字的排序,例如:學生記錄含三個關鍵字:系別、班號和班內(nèi)的序列號，其中以系別為最主位關鍵字,無序序列,對K2排序,對K1排序,對K0排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,LSD的排序過程如下:,排序過程中不需要根據(jù) “前一個” 關鍵字的排序結果，將記錄序列分割成若干個(“前一個”關鍵字不同的)子序列。,10.6 基

42、數(shù)排序,鏈式基數(shù)排序,假如多關鍵字的記錄序列中，每個關鍵字的取值范圍相同，則按LSD法進行排序時，可以采用“分配-收集”的方法，其好處是不需要進行關鍵字間的比較。,對于數(shù)字型或字符型的單關鍵字，可以看成是由多個數(shù)位或多個字符構成的多關鍵字，此時可以采用這種“分配-收集”的辦法進行排序，稱作基數(shù)排序法。,10.6 基數(shù)排序,鏈式基數(shù)排序,例如：對下列這組關鍵字 209, 386, 768, 185, 247, 606, 230, 834, 539 ,首先按其 “個位數(shù)” 取值分別為 0, 1, , 9“分配” 成 10 組，之后按從 0 至 9 的順序將 它們 “收集” 在一起;,然后按其 “十

43、位數(shù)” 取值分別為 0, 1, , 9 “分配” 成 10 組，之后再按從 0 至 9 的順序將它們 “收集” 在一起；,最后按其“百位數(shù)”重復一遍上述操作。,待排序記錄以指針相鏈，構成一個鏈表；用鏈表作存儲結構的基數(shù)排序設置10個隊列，fi和ei分別為第i個隊列的頭指針和尾指針,“分配” 時，按當前“關鍵字位”所取值，將記錄分配到不同的 “鏈隊列” 中，每個隊列中記錄的 “關鍵字位” 相同；,“收集”時，按當前關鍵字位取值從小到大將各隊列首尾相鏈成一個鏈表;,對每個關鍵字位均重復 2) 和 3) 兩步。,10.6 基數(shù)排序,鏈式基數(shù)排序,在計算機上實現(xiàn)基數(shù)排序時，為減少所需輔助存儲空間，應采用鏈表作存儲結構，即鏈式基數(shù)排序，具體作法為：,例：,10.6 基數(shù)排序,鏈式基數(shù)排序,10.6 基數(shù)排序,鏈式基數(shù)排序,10.6 基數(shù)排序,鏈式基數(shù)排序,10.6 基數(shù)排序,鏈式基數(shù)排序,提醒注意：,“分配”和“收集”的實際操作僅為修改鏈表中的指針和設置隊列的頭、尾指針；,2. 基數(shù)排序的時間復雜度為O(d(n+rd),其中，分配為O(n); 收集為O(rd)(rd為“基”), d為“分配-收集”的趟數(shù)。,10.7 各種排序方法的綜合比較,一、時間性能,1. 平均的時間性能,基數(shù)排序,時間復雜度為 O(nlogn)：,快速排序、堆排序和歸并排序