第9章 內(nèi)部排序.ppt

1、1,9.1 概述 9.2 插入排序 9.3 交換排序 9.4 選擇排序 9.5 歸并排序 9.6 基數(shù)排序,第9章 內(nèi)部排序,2,9.1 概述,1. 什么是排序？ 將一組雜亂無章的數(shù)據(jù)按一定的規(guī)律順次排列起來。,2. 排序的目的是什么？,存放在數(shù)據(jù)表中,按關(guān)鍵字排序,3.排序算法的好壞如何衡量？ 時間效率排序速度（即排序所花費的全部比較次數(shù)） 空間效率占內(nèi)存輔助空間的大小 穩(wěn)定性若兩個記錄A和B的關(guān)鍵字值相等，若排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。,便于查找！,3,4. 什么叫內(nèi)部排序？什么叫外部排序？,若待排序記錄都在內(nèi)存中，稱為內(nèi)部排序； 若待排序記錄一部分在內(nèi)存，一

2、部分在外存，則稱為外部排序。,注：外部排序時，要將數(shù)據(jù)分批調(diào)入內(nèi)存來排序，中間結(jié)果還要及時放入外存，顯然外部排序要復(fù)雜得多。,5.待排序記錄在內(nèi)存中怎樣存儲和處理？, 順序排序排序時直接移動記錄； 鏈表排序排序時只移動指針； 地址排序排序時先移動地址，最后再移動記錄。,注：地址排序中可以增設(shè)一維數(shù)組來專門存放記錄的地址。,4,注：大多數(shù)排序算法都是針對順序表結(jié)構(gòu)的(便于直接移動元素),6. 順序存儲（順序表）的抽象數(shù)據(jù)類型如何表示？,typedef struct /定義每個記錄（數(shù)據(jù)元素）的結(jié)構(gòu) KeyType key ; /關(guān)鍵字 InfoType otherinfo; /其它數(shù)據(jù)項 Rec

3、ordType ;,typedef struct /定義順序表的結(jié)構(gòu) RecordType r MAXSIZE +1 ; /存儲順序表的向量 /r0一般作哨兵或緩沖區(qū) int length ; /順序表的長度 SqList ;,# define MAXSIZE 20 /設(shè)記錄不超過20個 typedef int KeyType ; /設(shè)關(guān)鍵字為整型量（int型）,5,7. 內(nèi)部排序的算法有哪些？,按排序的規(guī)則不同，可分為5類： 插入排序 交換排序（重點是快速排序） 選擇排序 歸并排序 基數(shù)排序,d關(guān)鍵字的位數(shù)(長度),按排序算法的時間復(fù)雜度不同，可分為3類： 簡單的排序算法：時間效率低，O(n

4、2) 先進的排序算法: 時間效率高，O( nlog2n ) 基數(shù)排序算算法：時間效率高，O( dn),6,9.2 插入排序,插入排序的基本思想是：,插入排序有多種具體實現(xiàn)算法： 1) 直接插入排序 2) 折半插入排序 3) 表插入排序 4) 希爾排序,每步將一個待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的適當(dāng)位置上，直到對象全部插入為止。,簡言之，邊插入邊排序，保證子序列中隨時都是排好序的。,7,1) 直接插入排序,新元素插入到哪里？,例1：關(guān)鍵字序列T=（13，6，3，31，9，27，5，11）， 請寫出直接插入排序的中間過程序列。,【13】, 6, 3, 31, 9, 2

5、7, 5, 11 【6, 13】, 3, 31, 9, 27, 5, 11 【3, 6, 13】, 31, 9, 27, 5, 11 【3, 6, 13，31】, 9, 27, 5, 11 【3, 6, 9, 13，31】, 27, 5, 11 【3, 6, 9, 13，27, 31】, 5, 11 【3, 5, 6, 9, 13，27, 31】, 11 【3, 5, 6, 9, 11，13，27, 31】,在已形成的有序表中線性查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。,最簡單的排序法！,8,例2：關(guān)鍵字序列T= （21，25，49，25*，16，08），請寫出直接插入排序的具體實

6、現(xiàn)過程。,*表示后一個25,i=1,21,i=2,i=3,i=5,i=4,i=6,25,25,25,49,49,49,25*,49,16,16,08,49,解：假設(shè)該序列已存入一維數(shù)組V7中，將V0作為緩沖或暫存單元（Temp）。則程序執(zhí)行過程為：,初態(tài)：,16,25,21,16,完成!,時間效率：O(n2)因為在最壞情況下，所有元素的比較次數(shù)總和為（01n-1)O(n2)。其他情況下還要加上移動元素的次數(shù)。 空間效率：O(1)因為僅占用1個緩沖單元 算法的穩(wěn)定性：穩(wěn)定因為25*排序后仍然在25的后面。,9,若設(shè)待排序的對象個數(shù)為n，則算法需要進行n-1次插入。 最好情況下，排序前對象已經(jīng)按關(guān)

7、鍵碼大小從小到大有序，每趟只需與前面的有序?qū)ο笮蛄械淖詈笠粋€對象的關(guān)鍵碼比較 1 次，移動 2 次對象。因此，總的關(guān)鍵碼比較次數(shù)為n-1，對象移動次數(shù)為 2(n-1)。,直接插入排序的算法分析,10,最壞情況下，第i趟插入時，第i個對象必須與前面i-1個對象都做關(guān)鍵碼比較，并且每做 1 次比較就要做 1 次數(shù)據(jù)移動。則總的關(guān)鍵碼比較次數(shù)KCN和對象移動次數(shù)RMN分別為,11,若待排序?qū)ο笮蛄兄谐霈F(xiàn)各種可能排列的概率相同，則可取上述最好情況和最壞情況的平均情況。在平均情況下的關(guān)鍵碼比較次數(shù)和對象移動次數(shù)約為 n2/4。因此，直接插入排序的時間復(fù)雜度為 o(n2)。 直接插入排序是一種穩(wěn)定的排序方

8、法。,12,2） 折半插入排序,優(yōu)點：比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。 時間效率：雖然比較次數(shù)大大減少，可惜移動次數(shù)并未減少，所以排序效率仍為O(n2) 。 空間效率： O（1） 穩(wěn)定性：穩(wěn)定,新元素插入到哪里？,討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？ 答：直接插入不僅可行，而且還無需移動元素，時間效率更高！,折半插入排序的改進2-路插入排序見教材P267。,在已形成的有序表中折半查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。,但鏈表無法“折半”！,13,折半插入排序的算法分析,折半查找比順序查找快，所以折半插入排序就平均性能來說比直接插

9、入排序要快。 在插入第i個對象時，需要經(jīng)過log2i +1次關(guān)鍵碼比較，才能確定它應(yīng)插入的位置。因此，將n 個對象用折半插入排序所進行的關(guān)鍵碼比較次數(shù)為：n*log2n 折半插入排序是一個穩(wěn)定的排序方法。,14,3）表插入排序,基本思想：在順序存儲結(jié)構(gòu)中，給每個記錄增開一個指針分量，在排序過程中將指針內(nèi)容逐個修改為已經(jīng)整理（排序）過的后繼記錄地址。 優(yōu)點：在排序過程中不移動元素，只修改指針。,回憶： 鏈表排序排序時只移動指針； 地址排序排序時先移動地址，最后再移動記錄。,此方法具有鏈表排序和地址排序的特點。,15,1,例：關(guān)鍵字序列 T=(21，25，49，25*，16，08）， 請寫出表插入

10、排序的具體實現(xiàn)過程。,解：假設(shè)該序列（結(jié)構(gòu)類型)已存入一維數(shù)組V7中，將V0作為表頭結(jié)點。則算法執(zhí)行過程為：,指向第1個元素,指向頭結(jié)點,初態(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,16,int LinkInsertSort ( staticlinklis /在pre與current之間鏈入 ,表插入排序的算法,17,表插入排序算法分析：, 無需移動記錄，只需修改2n次指針值。但由于比較次數(shù)沒有減少，故時間效率仍為O(n2) 。 空間效率肯定低，因為增開了指針分量（但在運算過程中沒有用到更多的輔助單元）。 穩(wěn)定性：25和2

11、5*排序前后次序未變，穩(wěn)定。 討論：此算法得到的只是一個有序鏈表，查找記錄時只能滿足順序查找方式。 改進：可以根據(jù)表中指針線索，很快對所有記錄重排，形成真正的有序表（順序存儲方式），從而能滿足折半查找方式。,18,4）希爾（shell）排序（又稱縮小增量排序）,基本思想：先將整個待排記錄序列分割成若干子序列,分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。 技巧：子序列的構(gòu)成不是簡單地“逐段分割”，而是將相隔某個增量dk的記錄組成一個子序列,讓增量dk逐趟縮短(例如依次取5,3,1)，直到dk1為止。 優(yōu)點：讓關(guān)鍵字值小的元素能很快前移，且序列若基本有

12、序時，再用直接插入排序處理，時間效率會高很多。,19,38,例：關(guān)鍵字序列 T=(49,38,65,97,76,13,27,49*,55,04），請寫出希爾排序的具體實現(xiàn)過程。,初態(tài)：,第1趟 (dk=5),第2趟 (dk=3),第3趟 (dk=1),49,13,13,49,38,27,65,49*,97,55,76,04,27,38,65,49*,97,55,13,55,76,04,55,13,27,04,27,04,49,49*,49,49*,76,38,76,65,65,97,97,13,27,04,49*,76,97,算法分析：開始時dk 的值較大，子序列中的對象較少，排序速度較快；隨

13、著排序進展，dk 值逐漸變小，子序列中對象個數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對象已基本有序，所以排序速度仍然很快。,ri,20,void ShellSort(SqList /取支點的關(guān)鍵碼存入pivotkey變量,while(low =pivotkey)-high; rlow=rhigh; /將比支點小的記錄交換到低端； while(lowhigh /將比支點大的記錄交換到高端； ,rlow=r0; /支點記錄到位； return low; /返回支點記錄所在位置。 /Partition,33,Low=high=3，本趟停止，將支點定位并返回位置信息,例2：關(guān)鍵字序列 T=(21，25，

14、49，25*，16，08），請寫出快速排序算法的一趟實現(xiàn)過程。,high,low,21,08,25,16,49,25*,3,21,pivotkey=21,08,25,16,49,( 08 ，16 ） 21 （ 25* ， 49， 25 ）,25*跑到了前面，不穩(wěn)定！,34,j從高端掃描 尋找小于pivot的元素,i從低端掃描 尋找大于pivot的元素,一趟快速排序算法流程圖,35,void QSort ( SqList ,整個快速排序的遞歸算法：,見教材P276,/長度1,/對順序表L中的子序列r lowhigh 作快速排序,/一趟快排，將r 一分為二,/在左子區(qū)間進行遞歸快排，直到長度為1,

15、/在右子區(qū)間進行遞歸快排，直到長度為1,/QSort,新的low,void QuickSort ( SqList ,對順序表L進行快速 排序的操作函數(shù)為：,36,例3：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的各趟排序結(jié)束時，關(guān)鍵字序列的狀態(tài)。,原始序列： 256，301，751，129，937，863，742，694，076，438,快速排序,第1趟 第2趟 第3趟 第4趟,256，301，751，129，937，863，742，694，076，438,076，129，256，751，937，863，742，694，

16、301，438,要求模擬算法實現(xiàn)步驟,256,076,301,129,751,256,076，129，256，438，301，694，742，694，863，937,751,076，129，256，438，301，694，742，751，863，937,076，129，256，301，301，694，742，751，863，937,438,076，129，256，301，438，694，742，751，863，937,時間效率：O(nlog2n) 因為每趟確定的元素呈指數(shù)增加 空間效率：O（log2n）因為算法的遞歸性，要用到?？臻g 穩(wěn) 定 性： 不穩(wěn)定 因為可選任一元素為支點。,37,快速排

17、序算法詳細分析：,快速排序是遞歸的，需要有一個棧存放每層遞歸調(diào)用時的指針和參數(shù)（新的low和high）。 可以證明，函數(shù)quicksort的平均計算時間也是O(nlog2n)。實驗結(jié)果表明：就平均計算時間而言，快速排序是我們所討論的所有內(nèi)排序方法中最好的一個。 最大遞歸調(diào)用層次數(shù)與遞歸樹的深度一致，理想情況為 log2(n+1) 。因此，要求存儲開銷為 o(log2n)。 如果每次劃分對一個對象定位后，該對象的左側(cè)子序列與右側(cè)子序列的長度相同，則下一步將是對兩個長度減半的子序列進行排序，這是最理想的情況。此時，快速排序的趟數(shù)最少。,38,在最壞的情況，即待排序?qū)ο笮蛄幸呀?jīng)按其關(guān)鍵碼從小到大排好

18、序的情況下，其遞歸樹成為單支樹，每次劃分只得到一個比上一次少一個對象的子序列。這樣，必須經(jīng)過 n-1 趟才能把所有對象定位，而且第 i 趟需要經(jīng)過 n-i 次關(guān)鍵碼比較才能找到第 i 個對象的安放位置，總的關(guān)鍵碼比較次數(shù)將達到n2/2 快速排序是一個不穩(wěn)定的排序方法,39,討論2. “快速排序”是否真的比任何排序算法都快？,設(shè)每個子表的支點都在中間（比較均衡），則： 第1趟比較，可以確定1個元素的位置； 第2趟比較（2個子表），可以再確定2個元素的位置； 第3趟比較（4個子表），可以再確定4個元素的位置； 第4趟比較（8個子表），可以再確定8個元素的位置； 只需log2n 1趟便可排好序。,基

19、本上是！因為每趟可以確定的數(shù)據(jù)元素是呈指數(shù)增加的！,而且，每趟需要比較和移動的元素也呈指數(shù)下降，加上編程時使用了交替逼近技巧,更進一步減少了移動次數(shù),所以速度特別快。,快速排序的平均排序效率為O(nlog2n)； 但最壞情況(例如已經(jīng)有序)下仍為O(n2) 。,40,9.4 選擇排序,選擇排序有多種具體實現(xiàn)算法： 1) 簡單選擇排序 2) 錦標賽排序 3) 堆排序,選擇排序的基本思想是：每一趟在后面n-i 個待排記錄中選取關(guān)鍵字最小的記錄作為有序序列中的第i 個記錄。,41,1）簡單選擇排序,思路簡單：每經(jīng)過一趟比較就找出一個最小值，與待排序列最前面的位置互換即可。 首先，在n個記錄中選擇最小

20、者放到r1位置；然后，從剩余的n-1個記錄中選擇最小者放到r2位置；如此進行下去，直到全部有序為止。 優(yōu)點：實現(xiàn)簡單 缺點：每趟只能確定一個元素，表長為n時需要n-1趟 前提：順序存儲結(jié)構(gòu),42,例：關(guān)鍵字序列T= （21，25，49，25*，16，08），請給出簡單選擇排序的具體實現(xiàn)過程。,原始序列： 21，25，49，25*，16，08,直接選擇排序,第1趟 第2趟 第3趟 第4趟 第5趟,08，25，49，25*，16，21 08，16, 49，25*，25，21 08，16, 21，25*，25，49 08，16, 21，25*，25，49 08，16, 21，25*，25，49,時間

21、效率： O(n2)雖移動次數(shù)較少，但比較次數(shù)仍多。 空間效率：O（1）無需任何附加單元！ 算法的穩(wěn)定性：不穩(wěn)定因為排序時，25*到了25的前面。,最小值 08 與r1交換位置,43,簡單選擇排序的算法如下：,Void SelectSort(SqList /SelectSort,/對順序表L作簡單選擇排序,/選擇第i小的記錄，并交換到位,/在riL.length中選擇key最小的記錄,/與第i個記錄交換,討論：能否利用（或記憶）首趟的n-1次比較所得信息，從而盡量減少后續(xù)比較次數(shù)呢？ 答：能！請看錦標賽排序和堆排序！,44,2） 錦標賽排序 (又稱樹形選擇排序),基本思想：與體育比賽時的淘汰賽類

22、似。 首先對 n 個記錄的關(guān)鍵字進行兩兩比較，得到 n/2 個優(yōu)勝者(關(guān)鍵字小者)，作為第一步比較的結(jié)果保留下來。然后在這 n/2 個較小者之間再進行兩兩比較，如此重復(fù)，直到選出最小關(guān)鍵字的記錄為止。 優(yōu)點：減少比較次數(shù)，加快排序速度 缺點：空間效率低,例：關(guān)鍵字序列T= （21，25，49，25*，16，08，63），請給出錦標賽排序的具體實現(xiàn)過程。,45,Winner (勝者),r1,注：為便于自動處理，建議每個記錄多開兩個特殊分量：,初態(tài)：,補足2k( k=log2n )個葉子結(jié)點,勝者樹,第一趟：,46,第二趟：,16,16,16,r2,Winner (勝者),求次小值16時,只需比較

23、2次，即只比較log2n -1次。,令其Tag0,不參與比較,47,令其Tag0,不參與比較,第三趟：,r3,Winner (勝者),63,21,48,第四趟：,r4,Winner (勝者),25,25,25,49,第五趟：,r5,Winner (勝者),25*,25*,50,第六趟：,r6,Winner (勝者),49,49,49,51,第七趟：,r7,Winner (勝者),63,52,算法分析：,錦標賽排序構(gòu)成的樹是滿(完全）二叉樹，其深度為 log2n +1，其中 n 為待排序元素個數(shù)。 時間復(fù)雜度：O(nlog2n) n個記錄各自比較約log2n次 空間效率： O(n） 勝者樹的附加

24、內(nèi)結(jié)點共有n-1個！ 穩(wěn)定性：穩(wěn)定 左右結(jié)點相同者左為先,討論： 在簡單選擇排序過程中，每當(dāng)我們從表中選出最小元素之后，再選次最小元素時，必須把表中剩余元素再掃描一次。這樣，同一個元素會被掃描多次，浪費！ 能否利用上次掃描的結(jié)果定出下一次的選擇結(jié)果呢？ 答：能！請看堆排序算法,n =2k = 葉子總數(shù),53,3） 堆排序,1. 什么是堆？,堆的定義：設(shè)有n個元素的序列 k1，k2，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時，稱之為堆。,或者,i=1, 2, n/2,解釋：如果讓滿足以上條件的元素序列 （k1，k2，kn）順次排成一棵完全二叉樹，則此樹的特點是： 樹中所有結(jié)點的值均大于（或小于）其左右孩子

25、，此樹的根結(jié)點（即堆頂）必最大（或最?。?。,2. 怎樣建堆？,3. 怎樣堆排序？,54,（大根堆）,例：,有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判斷它們是否 “堆”？,（小根堆）,（小頂堆） （最小堆）,（大頂堆） （最大堆）,55,步驟：從最后一個非終端結(jié)點開始往前逐步調(diào)整，讓每個雙親大于（或小于）子女，直到根結(jié)點為止。,例：關(guān)鍵字序列T= (21，25，49，25*，16，08），請建大根堆。,2. 怎樣建堆？,解：為便于理解，先將原始序列畫成完全二叉樹的形式：,完全二叉樹的第一個非終端結(jié)點編號必為

26、n/2 ！(性質(zhì)5),注：終端結(jié)點（即葉子）沒有任何子女，無需單獨調(diào)整。,21,i=3: 49大于08，不必調(diào)整； i=2: 25大于25*和16，也不必調(diào)整； i=1: 21小于25和49，要調(diào)整！,49,而且21還應(yīng)當(dāng)向下比較！,56,void HeapSort (HeapType /使rilength成為大根堆 ,建堆算法 (其實是堆排序算法中的第一步）,這是針對結(jié)點 i 的堆調(diào)整函數(shù)，其含義是：從結(jié)點i開始到堆尾為止，自上向下比較，如果子女的值大于雙親結(jié)點的值，則互相交換，即把局部調(diào)整為大根堆。,57,針對結(jié)點 i 的堆調(diào)整函數(shù)HeapAdjust如下：,HeapAdjust(r, i

27、, m ) current=i; child=2*i; temp=ri; while(child=rchild.key)breack; else rcurrent=rchild; current= child; child=2* child; rcurrent=temp; / HeapAdjust,/temp是根，child是其左孩子,/檢查是否到達當(dāng)前堆尾,/讓child指向兩子女中的大者,/根大則不必調(diào)整，結(jié)束整個函數(shù),/否則子女中的大者上移,/并繼續(xù)向下整理！,/直到自下而上都滿足堆定義，再安置老根,從結(jié)點i開始到當(dāng)前堆尾m為止，自上向下比較，如果子女的值大于雙親結(jié)點的值，則互相交換，即

28、把局部調(diào)整為大根堆。,/將根下降到子女位置,58,關(guān)鍵：將堆的當(dāng)前頂點輸出后，如何將剩余序列重新調(diào)整為堆？ 方法：將當(dāng)前頂點與堆尾記錄交換，然后仿建堆動作重新調(diào)整，如此反復(fù)直至排序結(jié)束。,3. 怎樣進行堆排序？,59,交換 1號與 6 號記錄,例：對剛才建好的大根堆進行排序：,60,08 25 21 25* 16 49,從 1 號到 5 號 重新 調(diào)整為最大堆,08,25,25*,25 08 21 25* 16 49,08,25 25* 21 08 16 49,61,從 1號到 4號 重新 調(diào)整為最大堆,62,從 1 號到 3號 重新 調(diào)整為最大堆,63,16 08 21 25* 25 49,

29、從 1 號到 2 號 重新 調(diào)整為最大堆,64,堆排序的算法,參見教材P281-282,這是針對結(jié)點i 的堆調(diào)整函數(shù)（也是建堆函數(shù)），每次調(diào)用耗時O(log2n),65,附1：基于初始堆進行堆排序的算法步驟：,堆的第一個對象V0具有最大的關(guān)鍵碼，將V0與Vn對調(diào)，把具有最大關(guān)鍵碼的對象交換到最后，再對前面的n-1個對象，使用堆的調(diào)整算法，重新建立堆。結(jié)果具有次最大關(guān)鍵碼的對象又上浮到堆頂，即V0位置。 再對調(diào)V0和Vn-1，調(diào)用對前n-2個對象重新調(diào)整，如此反復(fù)，最后得到全部排序好的對象序列。,66,比較左右孩子大小，j指向大者,比較大孩子與rc的大小 若大向上浮,附2：算法流程,67,堆排序

30、算法分析：,時間效率： O(nlog2n)。因為整個排序過程中需要調(diào)用n-1次HeapAdjust( )算法，而算法本身耗時為log2n； 空間效率：O(1)。僅在第二個for循環(huán)中交換記錄時用到一個臨時變量temp。 穩(wěn)定性： 不穩(wěn)定。 優(yōu)點：對小文件效果不明顯，但對大文件有效。,68,9.5 歸并排序,歸并排序的基本思想是：將兩個（或以上）的有序表組成新的有序表。 更實際的意義：可以把一個長度為n 的無序序列看成是 n 個長度為 1 的有序子序列 ，首先做兩兩歸并，得到 n / 2 個長度為 2 的子序列 ；再做兩兩歸并，如此重復(fù)，直到最后得到一個長度為 n 的有序序列。,例：關(guān)鍵字序列T

31、= （21，25，49，25*，93，62，72，08，37，16，54），請給出歸并排序的具體實現(xiàn)過程。,69,len=1,len=2,len=4,len=8,len=16,整個歸并排序僅需log2n 趟,70,一趟歸并排序算法: (兩路有序并為一路) 參見教材P283,void Merge (SR， / 將剩余的SRjn復(fù)制到TR / Merge,71,void MSort (SR， / 將TR2 sm和TR2 m+1t歸并到TR1 st / MSort,遞歸形式的兩路歸并排序算法: 參見教材P284 (一路無序變?yōu)橛行?,簡言之，先由“長”無序變成“短”有序，再從“短”有序歸并為“長”有

32、序。,初次調(diào)用時為（L, L, 1, length）,72,歸并排序算法分析：,時間效率： O(nlog2n) 因為在遞歸的歸并排序算法中，函數(shù)Merge( )做一趟兩路歸并排序，需要調(diào)用merge ( )函數(shù) n/(2*len) O(n/len) 次，函數(shù)Merge( )調(diào)用Merge( )正好log2n 次，而每次merge( )要執(zhí)行比較O(len)次，所以算法總的時間復(fù)雜度為O(nlog2n)。 空間效率： O(n) 因為需要一個與原始序列同樣大小的輔助序列（TR）。這正是此算法的缺點。 穩(wěn)定性：穩(wěn)定,73,9.6 基數(shù)排序 (Radix Sort),要討論的問題： 1. 什么是“多關(guān)

33、鍵字”排序？實現(xiàn)方法？ 2. 單邏輯關(guān)鍵字怎樣“按位值”排序？,基數(shù)排序的基本思想是：,借助多關(guān)鍵字排序的思想對單邏輯關(guān)鍵字進行排序。即：用關(guān)鍵字不同的位值進行排序。,74,1. 什么是“多關(guān)鍵字”排序？實現(xiàn)方法？,例1：對一副撲克牌該如何排序？ 若規(guī)定花色和面值的順序關(guān)系為： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 則可以先按花色排序，花色相同者再按面值排序； 也可以先按面值排序，面值相同者再按花色排序。,例2：職工分房該如何排序？ 華工規(guī)定：先以總分排序（職稱分工齡分）； 總分相同者，再按配偶總分排序，其次按配偶職稱、工齡、人口等等排序。,以上兩例都是典型的多關(guān)

34、鍵字排序！,75,多關(guān)鍵字排序的實現(xiàn)方法通常有兩種：,最高位優(yōu)先法MSD (Most Significant Digit first),例：對一副撲克牌該如何排序？ 答：若規(guī)定花色為第一關(guān)鍵字（高位），面值為第二關(guān)鍵字（低位），則使用MSD和LSD方法都可以達到排序目的。 MSD方法的思路：先設(shè)立4個花色“箱”，將全部牌按花色分別歸入4個箱內(nèi)（每個箱中有13張牌）；然后對每個箱中的牌按面值進行插入排序（或其它穩(wěn)定算法）。 LSD方法的思路：先按面值分成13堆（每堆4張牌），然后對每堆中的牌按花色進行排序（用插入排序等穩(wěn)定的算法）。,想一想：用哪種方法更快些？,最低位優(yōu)先法LSD (Least

35、Significant Digit first),76,2. 單邏輯關(guān)鍵字怎樣“按位值”排序？,設(shè)n 個記錄的序列為：V0, V1, , Vn-1 ，可以把每個記錄Vi 的單關(guān)鍵碼 Ki 看成是一個d元組（Ki1, Ki2, , Kid），則其中的每一個分量Kij ( 1 j d ) 也可看成是一個關(guān)鍵字。,4,注1： Ki1最高位，Kid最低位；Ki共有d位，可看成d元組； 注2： 每個分量Kij (1 j d ) 有radix種取值，則稱radix為基數(shù)。,26,(9, 8, 4),(0, 1, , 9),（a, b, , z）,(d, i, a, n),3,10,思路：,77,因為有分組

36、，故此算法需遞歸實現(xiàn)。,討論：是借用MSD方式來排序呢，還是借用LSD方式？,例：初始關(guān)鍵字序列T=（32, 13, 27, 32*, 19，33），請分別用MSD和LSD進行排序，并討論其優(yōu)缺點。,法1（MSD）：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33,法2（LSD）： 原始序列： 32, 13, 27, 32*, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13

37、, 19 , 27, 32, 32*, 33,無需分組，易編程實現(xiàn)！,78,例：T=（02，77，70，54，64，21，55，11），用LSD排序。 分析： 各關(guān)鍵字可視為2元組；每位的取值范圍是：0-9；即基數(shù)radix 10 。因此，特設(shè)置10個隊列，并編號為0-9。,計算機怎樣實現(xiàn)LSD算法？,分配過程,收集過程,77,55,54，64,21，11,70,02,又稱散列過程！,79,小結(jié)：排序時經(jīng)過了反復(fù)的“分配”和“收集”過程。當(dāng)對關(guān)鍵字所有的位進行掃描排序后，整個序列便從無序變?yōu)橛行蛄恕?70，77,64,54，55,21,11,02,再次分配,再次收集,這種LSD排序方法稱為：,

38、基數(shù)排序,80,討論：所用隊列是順序結(jié)構(gòu)，浪費空間，能否改用鏈式結(jié)構(gòu)？,用鏈隊列來實現(xiàn)基數(shù)排序,鏈式基數(shù)排序,實現(xiàn)思路：,針對 d 元組中的每一位分量，把原始鏈表中的所有記錄, 按Kij的取值，讓 j = d, d-1, , 1， 先“分配”到radix個鏈隊列中去； 然后再按各鏈隊列的順序，依次把記錄從鏈隊列中“收集”起來； 分別用這種“分配”、“收集”的運算逐趟進行排序； 在最后一趟“分配”、“收集” 完成后，所有記錄就按其關(guān)鍵碼的值從小到大排好序了。,81,請實現(xiàn)以下關(guān)鍵字序列的鏈式基數(shù)排序： T=（614，738，921，485，637， 101，215，530，790，306）,例:

39、,第一趟分配,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,原始序列鏈表：,r0,（從最低位 i = 3開始排序，f 是隊首指針，e 為隊尾指針）,第一趟收集（讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 即可）,r0,82,第一趟收集的結(jié)果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f3 f4 f5 f6 f7 f8 f9,第二趟分配（按次低位 i = 2 ）,第二趟收集（讓隊尾指針ei 鏈接到下一非空隊首指針fi+1 ）,r0,r0,83,第二趟收集的結(jié)果：,e0 e1 e2 e3 e4 e5 e6 e7 e8 e9,614,738,921,485,637,101,215,530,790,306,f0 f1 f2 f