數(shù)據(jù)結(jié)構(gòu)第9章排序-課件

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

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

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

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

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)位置插入，把原來(lái)位置上的元素向后順移。最簡(jiǎn)單的排序法！8例2：關(guān)鍵字序列T= （21，25，49，25*，16，08），請(qǐng)寫(xiě)出直接插入排序的具體實(shí)現(xiàn)過(guò)程。*表示后一個(gè)25i=121254925*16080 1 2 3 4 5 6暫存2

6、1i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組V7中，將V0作為緩沖或暫存單元（Temp）。則程序執(zhí)行過(guò)程為：21254925*21初態(tài)：164925*25211608完成!時(shí)間效率： O(n2)因?yàn)樵谧顗那闆r下，所有元素的比較次數(shù)總和為（01n-1)O(n2)。其他情況下還要加上移動(dòng)元素的次數(shù)。 空間效率：O（1）因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：穩(wěn)定因?yàn)?5*排序后仍然在25的后面。 對(duì)應(yīng)程序參見(jiàn)教材P265。9若設(shè)待排序的對(duì)象個(gè)數(shù)為n，則算法需要進(jìn)行n-1次插入。最好情況下，排序前對(duì)象已經(jīng)按關(guān)鍵碼大小從小到

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

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

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

10、入排序的具體實(shí)現(xiàn)過(guò)程。解：假設(shè)該序列（結(jié)構(gòu)類(lèi)型)已存入一維數(shù)組V7中，將V0作為表頭結(jié)點(diǎn)。則算法執(zhí)行過(guò)程為：i關(guān)鍵字 Vi.key指針 Vi.link0 MaxNum1212253494 25*516608指向第1個(gè)元素指向頭結(jié)點(diǎn)初態(tài)i=1i=2i=3i=4i=5i=603456503102*表示后一個(gè)2516int LinkInsertSort ( staticlinklis & list ) list.v0.Key = MaxNum; list.v0. Link = 1; list.v1.Link = 0; /形成循環(huán)鏈表表插入排序的算法for ( int i = 2; i = list.

11、length; i+ ) int current = list.v0. Link; /current=當(dāng)前記錄指針 int pre = 0; /pre=當(dāng)前記錄current的前驅(qū)指針 while ( list.vcurrent. Key link)list.vi. Link = current; /新記錄vi找到合適序位開(kāi)始插入 list.vpre. Link = i; /在pre與current之間鏈入 17表插入排序算法分析： 無(wú)需移動(dòng)記錄，只需修改2n次指針值。但由于比較次數(shù)沒(méi)有減少，故時(shí)間效率仍為O(n2) 。 空間效率肯定低，因?yàn)樵鲩_(kāi)了指針?lè)至浚ǖ谶\(yùn)算過(guò)程中沒(méi)有用到更多的輔助單元

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

13、的元素能很快前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。1938例：關(guān)鍵字序列 T=(49，38，65，97, 76, 13, 27, 49*，55, 04），請(qǐng)寫(xiě)出希爾排序的具體實(shí)現(xiàn)過(guò)程。0123456789104938659776132749*5504初態(tài)：第1趟 (dk=5)第2趟 (dk=3)第3趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97

14、算法分析：開(kāi)始時(shí)dk 的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，dk 值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。ri20void ShellSort(SqList &L，int dlta ，int t) /按增量序列dlta0t-1對(duì)順序表L作Shell排序 for(k=0；kt；+k) ShellSort(L，dltak)； /增量為dltak的一趟插入排序 / ShellSort時(shí)間效率：空間效率：O（1）因?yàn)閮H占用1個(gè)緩沖單元算法的穩(wěn)定性：不穩(wěn)定因?yàn)?9*排序后卻到了49的前面希爾排序算法（主程序）參見(jiàn)教材P27

15、2O(n1.25）O（1.6n1.25）經(jīng)驗(yàn)公式dk值依次裝在dltat中21附：希爾排序算法分析對(duì)特定的待排序?qū)ο笮蛄?，可以?zhǔn)確地估算關(guān)鍵碼的比較次數(shù)和對(duì)象移動(dòng)次數(shù)。但想要弄清關(guān)鍵碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)與增量選擇之間的依賴(lài)關(guān)系，并給出完整的數(shù)學(xué)分析，還沒(méi)有人能夠做到。Knuth利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出，當(dāng)n很大時(shí)，關(guān)鍵碼平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在 n1.25 到 1.6n1.25 的范圍內(nèi)。這是在利用直接插入排序作為子序列排序方法的情況下得到的。22void ShellInsert(SqList &L，int dk) for(i=dk+1；i=L.length； + i) if

16、(ri.key 0 &(r0.keyrj.key); j=j-dk) rj+dk=rj； rj+dk=r0； 希爾排序算法（其中某一趟的排序操作）參見(jiàn)教材P272/對(duì)順序表L進(jìn)行一趟增量為dk的Shell排序，dk為步長(zhǎng)因子/開(kāi)始將ri 插入有序增量子表/暫存在r0/關(guān)鍵字較大的記錄在子表中后移/在本趟結(jié)束時(shí)將ri插入到正確位置23課堂練習(xí)：1. 欲將序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母升序重排，則初始步長(zhǎng)為4的希爾排序一趟的結(jié)果是？答：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shell一趟后：2

17、. 以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，分別寫(xiě)出執(zhí)行以下算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)，并說(shuō)明這些排序方法中，哪些易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？ 直接插入排序 希爾排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X ,Y答：顯然，直接插入排序方法易于在鏈表上實(shí)現(xiàn)；但希爾排序方法因?yàn)槭前丛隽窟x擇記錄，不易于在鏈表上實(shí)現(xiàn)。 兩種排序方法的中間狀態(tài)分別描述如后：24原始序列： 256，301，751，129，937，863，742，694，076，438256，301，751，129，937，8

18、63，742，694，076，438256，301，751，129，937，863，742，694，076，438129，256，301，751，937，863，742，694，076，438129，256，301，751，937，863，742，694，076，438129，256，301，751，863，937，742，694，076，438129，256，301，742，751，863，937，694，076，438129，256，301，694，742，751，863，937，076，438076，129，256，301，694，742，751，863，937，438076，129，2

19、56，301，438，694，742，751，863，937直接插入排序第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟第9趟25原始序列： 256，301，751，129，937，863，742，694，076，438希爾排序(取dk=5,3,1)256，301，751，129，937，863，742，694，076，438256，301，751，129，937，863，742，694，076，438256，301，694，129，937，863，742，751，076，438256，301，694，076，937，863，742，751，129，438256，301，694，076，438

20、，863，742，751，129，937第1趟dk=5第2趟dk=3第3趟dk=1256，301，694，076，438，863，742，751，129，937256，301，694，076，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，694，256，438，863，742，751，129，937076，301，129，256，438，694，742，751，863，937076，301，129，256，438，694，7

21、42，751，863，937076，301，129，256，438，694，742，751，863，937076，129，256，301，438，694，742，751，863，937269.3 交換排序 兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有： 1) 冒泡排序 2) 快速排序交換排序的基本思想是：27 1) 冒泡排序基本思路：每趟不斷將記錄兩兩比較，并按“前小后大”（或“前大后小”）規(guī)則交換。優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦下趟沒(méi)有交換發(fā)生，還可以

22、提前結(jié)束排序。前提：順序存儲(chǔ)結(jié)構(gòu) 例：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出冒泡排序的具體實(shí)現(xiàn)過(guò)程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初態(tài)：第1趟第2趟第3趟第4趟第5趟28冒泡排序的算法分析時(shí)間效率：O（n2) 因?yàn)橐紤]最壞情況空間效率：O（1） 只在交換時(shí)用到一個(gè)緩沖單元穩(wěn) 定 性： 穩(wěn)定 25和25*在排序前后的次序未改變?cè)敿?xì)分析：最好情況：初始排

23、列已經(jīng)有序，只執(zhí)行一趟起泡，做 n-1 次關(guān)鍵碼比較，不移動(dòng)對(duì)象。最壞情形：初始排列逆序，算法要執(zhí)行n-1趟起泡，第i趟(1 i n) 做了n- i 次關(guān)鍵碼比較，執(zhí)行了n-i 次對(duì)象交換。此時(shí)的比較總次數(shù)KCN和記錄移動(dòng)次數(shù)RMN為：292） 快速排序 從待排序列中任取一個(gè)元素 (例如取第一個(gè)) 作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了?；舅枷耄簝?yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別快！ 前提：順序存儲(chǔ)結(jié)構(gòu) 30( )，設(shè)以首元素為

24、樞軸中心例1：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出快速排序的算法步驟。21， 25， 49， 25*，16， 08初態(tài)：第1趟：第2趟：第3趟：討論：1. 這種不斷劃分子表的過(guò)程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？2. “快速排序”是否真的比任何排序算法都快？08，16，21，25， 25*，(49)2116，08，( )25，25*，49(08)，16，21，25，(25*，49)311.這種不斷劃分子表的過(guò)程，計(jì)算機(jī)如何自動(dòng)實(shí)現(xiàn)？編程時(shí)：每一趟的子表的形成是采用從兩頭向中間交替式逼近法；由于每趟中對(duì)各子表的操作都相似，主程序可采用遞歸算法。見(jiàn)教材P275int Partiti

25、on(SqList &L,int low,int high) /一趟快排/交換子表 rlowhigh的記錄，使支點(diǎn)（樞軸）記錄到位，并返回其位置。返回時(shí)，在支點(diǎn)之前的記錄均不大于它，支點(diǎn)之后的記錄均不小于它。 r0=rlow; /以子表的首記錄作為支點(diǎn)記錄，放入r0單元（續(xù)下頁(yè)）一趟快速排序算法（針對(duì)一個(gè)子表的操作）32pivotkey=rlow.key; /取支點(diǎn)的關(guān)鍵碼存入pivotkey變量while(low high) /從表的兩端交替地向中間掃描while(low=pivotkey ) - -high; rlow=rhigh; /將比支點(diǎn)小的記錄交換到低端；while(lowhigh

26、 & rlow.key=pivotkey) + +low; rhigh=rlow; /將比支點(diǎn)大的記錄交換到高端；rlow=r0; /支點(diǎn)記錄到位；return low; /返回支點(diǎn)記錄所在位置。/Partition33Low=high=3，本趟停止，將支點(diǎn)定位并返回位置信息例2：關(guān)鍵字序列 T=(21，25，49，25*，16，08），請(qǐng)寫(xiě)出快速排序算法的一趟實(shí)現(xiàn)過(guò)程。ri0123456初態(tài)21254925*1608第1趟highlow210825164925*321pivotkey=2108251649( 08 ，16 ） 21 （ 25* ， 49， 25 ）25*跑到了前面，不穩(wěn)定！3

27、4j從高端掃描尋找小于pivot的元素i從低端掃描尋找大于pivot的元素i=low; j=high;r0=rlow; pivot=rlow.key;i ji =pivot-j;ri = rj;i j &ri.key=pivot-i;rj = ri;ri = r0;return ok;YYYNNN一趟快速排序算法流程圖35void QSort ( SqList &L, int low, int high ) if ( low 1/對(duì)順序表L中的子序列r lowhigh 作快速排序/一趟快排，將r 一分為二/在左子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為1/在右子區(qū)間進(jìn)行遞歸快排，直到長(zhǎng)度為1/QSort新

28、的lowvoid QuickSort ( SqList &L) QSort (L, 1, L.length );對(duì)順序表L進(jìn)行快速排序的操作函數(shù)為：36例3：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫(xiě)出執(zhí)行快速算法的各趟排序結(jié)束時(shí)，關(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，438076，129，256，751，937，863，742，694，301，438要求模擬算法

29、實(shí)現(xiàn)步驟256076301129751256076，129，256，438，301，694，742，694，863，937751076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937438076，129，256，301，438，694，742，751，863，937時(shí)間效率：O(nlog2n) 因?yàn)槊刻舜_定的元素呈指數(shù)增加空間效率：O（log2n）因?yàn)樗惴ǖ倪f歸性，要用到?？臻g穩(wěn) 定 性： 不穩(wěn)定 因?yàn)榭蛇x任一元素為支點(diǎn)。37快速排序算法詳細(xì)分析：快速排序是遞歸的，需要有一個(gè)棧存放每層遞歸調(diào)用

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

31、列。這樣，必須經(jīng)過(guò) n-1 趟才能把所有對(duì)象定位，而且第 i 趟需要經(jīng)過(guò) n-i 次關(guān)鍵碼比較才能找到第 i 個(gè)對(duì)象的安放位置，總的關(guān)鍵碼比較次數(shù)將達(dá)到n2/2 快速排序是一個(gè)不穩(wěn)定的排序方法39討論2. “快速排序”是否真的比任何排序算法都快？設(shè)每個(gè)子表的支點(diǎn)都在中間（比較均衡），則：第1趟比較，可以確定1個(gè)元素的位置；第2趟比較（2個(gè)子表），可以再確定2個(gè)元素的位置；第3趟比較（4個(gè)子表），可以再確定4個(gè)元素的位置；第4趟比較（8個(gè)子表），可以再確定8個(gè)元素的位置； 只需log2n 1趟便可排好序?；旧鲜?！因?yàn)槊刻丝梢源_定的數(shù)據(jù)元素是呈指數(shù)增加的！而且，每趟需要比較和移動(dòng)的元素也呈指數(shù)下

32、降，加上編程時(shí)使用了交替逼近技巧，更進(jìn)一步減少了移動(dòng)次數(shù)，所以速度特別快。教材P276有證明：快速排序的平均排序效率為O(nlog2n)；但最壞情況(例如已經(jīng)有序)下仍為O(n2),改進(jìn)措施見(jiàn)P277。40 基本思想是: 每一趟 (例如第 i 趟, i = 0, 1, , n-2) 在后面 n-i 個(gè)待排序?qū)ο笾羞x出排序碼最小的對(duì)象, 作為有序?qū)ο笮蛄械牡?i 個(gè)對(duì)象。待到第 n-2 趟作完, 待排序?qū)ο笾皇Ｏ?個(gè), 就不用再選了。9.4 選擇排序41 若它不是這組對(duì)象中的第一個(gè)對(duì)象, 則將它與這組對(duì)象中的第一個(gè)對(duì)象對(duì)調(diào); 在這組對(duì)象中剔除這個(gè)具有最小排序碼的對(duì)象。在剩下的對(duì)象Vi+1Vn-1

33、中重復(fù)執(zhí)行第、步, 直到剩余對(duì)象只有一個(gè)為止。直接選擇排序是一種簡(jiǎn)單的排序方法, 它的基本步驟是： 在一組對(duì)象 ViVn-1 中選擇具有最小排序碼的對(duì)象；直接選擇排序 (Select Sort)4221254925*16080 1 2 3 4 52125*i = 0492516251608490825*4921i = 1i = 2081625*2521初始最小者 08交換21,08最小者 16交換25,16最小者 21交換49,21434925*0 1 2 3 4 525*i = 42516084925*4921結(jié)果i = 308162521最小者 25*無(wú)交換最小者 25無(wú)交換2521160

34、8各趟排序后的結(jié)果44 直接選擇排序的算法typedef int SortData;void SelectSort ( SortData V , int n ) for ( int i = 0; i n-1; i+ ) int k = i; /選擇具有最小排序碼的對(duì)象 for ( int j = i+1; j n; j+) if ( Vj Vk ) k = j; /當(dāng)前具最小排序碼的對(duì)象 if ( k != i ) /對(duì)換到第 i 個(gè)位置 Swap ( Vi, Vk ); 450 1 2 3 4 549160825*49210825*2521i =1時(shí)選擇排序的過(guò)程i k j 49250825

35、*1621i k j 49 2525* 251625i k j 16 254649250825*16210 1 2 3 4 5i k j 21 16k 指示當(dāng)前序列中最小者直接選擇排序的排序碼比較次數(shù) KCN 與對(duì)象的初始排列無(wú)關(guān)。設(shè)整個(gè)待排序?qū)ο笮蛄杏?n 個(gè)對(duì)象, 則第 i 趟選擇具有最小排序碼對(duì)象所需的比較次數(shù)總是 n-i-1 次?？偟呐判虼a比較次數(shù)為47錦標(biāo)賽排序 (Tournament Tree Sort)它的思想與體育比賽時(shí)的淘汰賽類(lèi)似。首先取得 n 個(gè)對(duì)象的關(guān)鍵碼，進(jìn)行兩兩比較，得到 n/2 個(gè)比較的優(yōu)勝者(關(guān)鍵碼小者)，作為第一步比較的結(jié)果保留下來(lái)。然后對(duì)這 n/2 個(gè)對(duì)象再進(jìn)

36、行關(guān)鍵碼的兩兩比較，如此重復(fù)，直到選出一個(gè)關(guān)鍵碼最小的對(duì)象為止。在圖例中，最下面是對(duì)象排列的初始狀態(tài)，相當(dāng)于一棵滿二叉樹(shù)的葉結(jié)點(diǎn)，它存放的是所有參加排序的對(duì)象的關(guān)鍵碼。48如果 n 不是2的 k 次冪，則讓葉結(jié)點(diǎn)數(shù)補(bǔ)足到滿足 2k-1 n 2k 的2k個(gè)。葉結(jié)點(diǎn)上面一層的非葉結(jié)點(diǎn)是葉結(jié)點(diǎn)關(guān)鍵碼兩兩比較的結(jié)果。最頂層是樹(shù)的根。08Winner 2108086325*2121254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree1449勝者樹(shù)的概念每次兩兩比較的結(jié)果是把關(guān)鍵碼小者作為優(yōu)勝者上升到雙親結(jié)點(diǎn)，稱(chēng)這種比賽樹(shù)為勝者樹(shù)。

37、位于最底層的葉結(jié)點(diǎn)叫做勝者樹(shù)的外結(jié)點(diǎn)，非葉結(jié)點(diǎn)稱(chēng)為勝者樹(shù)的內(nèi)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)除了存放對(duì)象的關(guān)鍵碼 data 外，還存放了此對(duì)象是否要參選的標(biāo)志 Active 和此對(duì)象在滿二叉樹(shù)中的序號(hào)index。勝者樹(shù)最頂層是樹(shù)的根，表示最后選擇出來(lái)的具有最小關(guān)鍵碼的對(duì)象。5008Winner (勝者)2108086325*2121254925*160863tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14 形成初始勝者樹(shù)（最小關(guān)鍵碼上升到根）a0關(guān)鍵碼比較次數(shù) : 6 5116Winner (勝者)2116166325*2121254925*1663tre

38、e7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出冠軍并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài)a1關(guān)鍵碼比較次數(shù) : 2 5221Winner (勝者)21636325*2121254925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出亞軍并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài)a2關(guān)鍵碼比較次數(shù) : 2 5325Winner (勝者)25636325*25254925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出第三名并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài)a

39、3關(guān)鍵碼比較次數(shù) : 2 5425*Winner (勝者)25*636325*4925*63tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14輸出第四名并調(diào)整勝者樹(shù)后樹(shù)的狀態(tài)a4關(guān)鍵碼比較次數(shù) : 2 5563Winner (勝者)636363tree7 tree8 tree9 tree10 tree11 tree12 tree13 tree14全部比賽結(jié)果輸出時(shí)樹(shù)的狀態(tài)a6關(guān)鍵碼比較次數(shù) : 2 56勝者樹(shù)數(shù)據(jù)結(jié)點(diǎn)類(lèi)的定義template class DataNode public: Type data; /數(shù)據(jù)值 int index;

40、/結(jié)點(diǎn)在滿二叉樹(shù)中順序號(hào) int active; /參選標(biāo)志：=1, 參選, =0, 不參選錦標(biāo)賽排序的算法 template void TournamentSort ( Type a , int n ) DataNode *tree; DataNode item; 57 int bottomRowSize = PowerOfTwo ( n ); /乘冪值 int TreeSize = 2*bottomRowSize-1; /總結(jié)點(diǎn)個(gè)數(shù) int loadindex = bottomRowSize-1; /內(nèi)結(jié)點(diǎn)個(gè)數(shù) tree = new DataNodeTreeSize; int j = 0;

41、 /從 a 向勝者樹(shù)外結(jié)點(diǎn)復(fù)制數(shù)據(jù) for ( int i = loadindex; i TreeSize; i+) treei.index = i; if ( j n ) treei.active = 1; treei.data = aj+; else treei.active = 0; i = loadindex; /進(jìn)行初始比較選擇最小的項(xiàng) while ( i ) 58 j = i; while ( j 2*i ) if ( !treej+1.active| /勝者送入雙親 treej.data = treej+1.data ) tree(j-1)/2 = treej; else tre

42、e(j-1)/2 = treej+1; j += 2; i = (i-1)/2; / i 退到雙親, 直到 i=0為止 for ( i = 0; i n-1; i+) /處理其它n-1個(gè)數(shù)據(jù) ai = tree0.data; /送出最小數(shù)據(jù) treetree0.index.active = 0; /失去參選資格 59 UpdateTree ( tree, tree0.index ); /調(diào)整 an-1 = tree0.data; 錦標(biāo)賽排序中的調(diào)整算法template void UpdateTree ( DataNode *tree, int i ) if ( i % 2 = 0 ) tree

43、(i-1)/2 = treei-1; /i偶數(shù), 對(duì)手左結(jié)點(diǎn) else tree(i-1)/2 = treei+1; /i奇數(shù), 對(duì)手右結(jié)點(diǎn) i = (i-1) / 2; /向上調(diào)整 60 while ( i ) /直到 i=0 if ( i %2 = 0) j = i-1; else j = i+1; if ( !treei.active | !treej.active ) if ( treei.active ) tree(i-1)/2 = treei; /i可參選, i上 else tree(i-1)/2 = treej; /否則, j上 else/兩方都可參選 if ( treei.da

44、ta treej.data ) tree(i-1)/2 = treei; /關(guān)鍵碼小者上 else tree(i-1)/2 = treej; i = (i-1) / 2; / i上升到雙親 61算法分析錦標(biāo)賽排序構(gòu)成的樹(shù)是滿的完全二叉樹(shù)，其深度為 log2(n+1)，其中 n 為待排序元素個(gè)數(shù)。除第一次選擇具有最小關(guān)鍵碼的對(duì)象需要進(jìn)行 n-1 次關(guān)鍵碼比較外，重構(gòu)勝者樹(shù)選擇具有次小、再次小關(guān)鍵碼對(duì)象所需的關(guān)鍵碼比較次數(shù)均為 O(log2n)?？傟P(guān)鍵碼比較次數(shù)為O(nlog2n)。對(duì)象的移動(dòng)次數(shù)不超過(guò)關(guān)鍵碼的比較次數(shù)，所以錦標(biāo)賽排序總的時(shí)間復(fù)雜度為O(nlog2n)。這種排序方法雖然減少了許多排

45、序時(shí)間，但是使用了較多的附加存儲(chǔ)。62如果有 n 個(gè)對(duì)象，必須使用至少 2n-1 個(gè)結(jié)點(diǎn)來(lái)存放勝者樹(shù)。最多需要找到滿足 2k-1 n 2k 的k，使用 2*2k-1 個(gè)結(jié)點(diǎn)。每個(gè)結(jié)點(diǎn)包括關(guān)鍵碼、對(duì)象序號(hào)和比較標(biāo)志三種信息。錦標(biāo)賽排序是一個(gè)穩(wěn)定的排序方法。63堆排序 (Heap Sort)利用堆及其運(yùn)算，可以很容易地實(shí)現(xiàn)選擇排序的思路。堆排序分為兩個(gè)步驟：第一步，根據(jù)初始輸入數(shù)據(jù)，利用堆的調(diào)整算法 HeapAdjust( ) 形成初始堆，第二步，通過(guò)一系列的對(duì)象交換和重新調(diào)整堆進(jìn)行排序。64建立初始的最大堆212525*491608123456i212525*164908136542i21 25

46、 49 25* 16 08初始關(guān)鍵碼集合21 25 49 25* 16 08i = 2 時(shí)的局部調(diào)整65212525*491608123456i492525*16210813654221 25 49 25* 16 0849 25 21 25* 16 08i = 0 時(shí)的局部調(diào)整形成最大堆i = 1 時(shí)的局部調(diào)整66最大堆的向下調(diào)整算法Type SqList HeapType;Void HeapAdjust (HeapType & H, int s,int m) rc = H.rs ; for (j = 2*s; j=m ;j* =2) if (j0 ;-i)（從最下層的分支結(jié)點(diǎn)向上） Heap

47、Adjust (H,i,H.length);68基于初始堆進(jìn)行堆排序最大堆的第一個(gè)對(duì)象H0具有最大的關(guān)鍵碼，將H0與Hn對(duì)調(diào)，把具有最大關(guān)鍵碼的對(duì)象交換到最后，再對(duì)前面的n-1個(gè)對(duì)象，使用堆的調(diào)整算法HeapAdjust(H,0, n-1)，重新建立最大堆。結(jié)果具有次最大關(guān)鍵碼的對(duì)象又上浮到堆頂，即H0位置。再對(duì)調(diào)V0和Vn-1，調(diào)用HeapAdjust(H,0, n-2)，對(duì)前n-2個(gè)對(duì)象重新調(diào)整，。如此反復(fù)執(zhí)行，最后得到全部排序好的對(duì)象序列。這個(gè)算法即堆排序算法，其細(xì)節(jié)在下面的程序中給出。69492525*211608123456082525*16214913654249 25 21 25

48、* 16 0808 25 21 25* 16 49交換 0 號(hào)與 5 號(hào)對(duì)象,5 號(hào)對(duì)象就位初始最大堆702525*082116491234561625*0825214913654225 25* 21 08 16 4916 25* 21 08 25 49交換 0 號(hào)與 4 號(hào)對(duì)象,4 號(hào)對(duì)象就位從 0 號(hào)到 4 號(hào) 重新調(diào)整為最大堆7125*1608212549123456081625*25214913654225* 16 21 08 25 4908 16 21 25* 25 49交換 0 號(hào)與 3 號(hào)對(duì)象,3 號(hào)對(duì)象就位從 0 號(hào)到 3 號(hào) 重新調(diào)整為最大堆72211625*08254912

49、3456081625*25214913654221 16 08 25* 25 4908 16 21 25* 25 49交換 0 號(hào)與 2 號(hào)對(duì)象,2 號(hào)對(duì)象就位從 0 號(hào)到 2 號(hào) 重新調(diào)整為最大堆73160825*212549123456081625*25214913654216 08 21 25* 25 4908 16 21 25* 25 49交換 0 號(hào)與 1 號(hào)對(duì)象,1 號(hào)對(duì)象就位從 0 號(hào)到 1 號(hào) 重新調(diào)整為最大堆74堆排序的算法/對(duì)表H1到Hn進(jìn)行排序, 使得表中各/個(gè)對(duì)象按其關(guān)鍵碼非遞減有序。 Void HeapSort (HeapType & H ) for (i= H.le

50、ngth/2; i0 ;-i)（從最下層的分支結(jié)點(diǎn)向上） HeapAdjust (H,i,H.length); for (i= H.length; i1 ; -i ) H.r1 H.ri ; HeapAdjust( H, 1, i-1);（從根結(jié)點(diǎn)向下） 75算法分析若設(shè)堆中有 n 個(gè)結(jié)點(diǎn)，且 2k-1 n 2k，則對(duì)應(yīng)的完全二叉樹(shù)有 k 層。在第 i 層上的結(jié)點(diǎn)數(shù) 2i (i = 0, 1, , k-1)。在第一個(gè)形成初始堆的for循環(huán)中對(duì)每一個(gè)非葉結(jié)點(diǎn)調(diào)用了一次堆調(diào)整算法HeapAdjust( )，因此該循環(huán)所用的計(jì)算時(shí)間為：其中，i 是層序號(hào)，2i 是第 i 層的最大結(jié)點(diǎn)數(shù)，(k-i-1

51、)是第 i 層結(jié)點(diǎn)能夠移動(dòng)的最大距離。76在第二個(gè)for循環(huán)中，調(diào)用了n-1次HeapAdjust( )算法，該循環(huán)的計(jì)算時(shí)間為O(nlog2n)。因此，堆排序的時(shí)間復(fù)雜性為O(nlog2n)。該算法的附加存儲(chǔ)主要是在第二個(gè)for循環(huán)中用來(lái)執(zhí)行對(duì)象交換時(shí)所用的一個(gè)臨時(shí)對(duì)象。因此，該算法的空間復(fù)雜性為O(1)。堆排序是一個(gè)不穩(wěn)定的排序方法。77對(duì)象的移動(dòng)次數(shù)與對(duì)象序列的初始排列有關(guān)。當(dāng)這組對(duì)象的初始狀態(tài)是按其排序碼從小到大有序的時(shí)候, 對(duì)象的移動(dòng)次數(shù)RMN = 0，達(dá)到最少。最壞情況是每一趟都要進(jìn)行交換，總的對(duì)象移動(dòng)次數(shù)為 RMN = 3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。789.5

52、 歸并排序 (Merge Sort)歸并，是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。原始序列initList 中兩個(gè)有序表 initListl initListm和initListm+1 initListn。它們可歸并成一個(gè)有序表, 存于另一對(duì)象序列mergedList的 l n 中。這種歸并方法稱(chēng)為兩路歸并 (2-way merging)。設(shè)變量 i 和 j 是表initListl m和initList m+1 n的當(dāng)前檢測(cè)指針。k 是存放指針。歸并7908 21 25 25* 49 62 72 93 16 37 54 left mid mid+1 rightinitListi j08

53、 16 21 25 25* 37 49 54 62 72 93 left rightkmergeList當(dāng) i 和 j 都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí), 根據(jù)對(duì)應(yīng)項(xiàng)的排序碼的大小, 依次把排序碼小的對(duì)象排放到新表 k 所指位置中；當(dāng) i 與 j 中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一 個(gè)表中的剩余部分照抄到新表中。80迭代的歸并排序算法迭代的歸并排序算法就是利用兩路歸并過(guò)程進(jìn)行排序的。其基本思想是：假設(shè)初始對(duì)象序列有 n 個(gè)對(duì)象，首先把它看成是 n 個(gè)長(zhǎng)度為 1 的有序子序列 (歸并項(xiàng))，先做兩兩歸并，得到 n / 2 個(gè)長(zhǎng)度為 2 的歸并項(xiàng) (如果 n 為奇數(shù)，則最后一個(gè)有序子序列的長(zhǎng)度為1)；再做兩兩歸

54、并，如此重復(fù)，最后得到一個(gè)長(zhǎng)度為 n 的有序序列。81兩路歸并算法typedef int SortData;void merge ( SortData InitList , SortData mergedList , int left, int mid, int right ) int i = left, j = mid+1, k = left; while ( i = mid & j = right ) /兩兩比較 if ( InitListi = InitListj ) mergedList k = InitListi; i+; k+; else mergedList k = InitLi

55、stj; j+; k+; 82 while ( i = mid ) mergedListk = InitListi; i+; k+; while ( j = right ) mergedListk = InitListj; j+; k+; 83一趟歸并排序的情形設(shè)initList0到initListn-1中 n 個(gè)對(duì)象已經(jīng)分為一些長(zhǎng)度為 len 的歸并項(xiàng), 將這些歸并項(xiàng)兩兩歸并, 歸并成長(zhǎng)度為 2len 的歸并項(xiàng), 結(jié)果放到mergedList 中。如果n不是2len的整數(shù)倍, 則一趟歸并到最后,可能遇到兩種情形： 剩下一個(gè)長(zhǎng)度為len的歸并項(xiàng)和另一個(gè)長(zhǎng)度不足len的歸并項(xiàng), 可用merge算

56、法將它們歸并成一個(gè)長(zhǎng)度小于 2len 的歸并項(xiàng)。 只剩下一個(gè)歸并項(xiàng)，其長(zhǎng)度小于或等于 len, 將它直接抄到MergedList 中。84void MergePass ( SortData initList , SortData mergedList , int len ) int i = 0; while (i+2*len-1 = n-1) merge( initList, mergedList, i, i+len-1, i+2*len-1); i += 2 * len; /循環(huán)兩兩歸并 if ( i+len = n-1 ) merge( initList, mergedList, i, i

57、+len-1, n-1); else for ( int j = i; j = n-1; j+) mergedList j = initListj; 85迭代的歸并排序算法212525*25*936272083716544921254962930872163754212525*490862729316375408082116252125*254925*623772499354163754627293len=1len=2len=4len=8len=1686(兩路)歸并排序的主算法void MergeSort ( SortData initList , int n ) /按對(duì)象排序碼非遞減的順序?qū)?/p>

58、表中對(duì)象排序 SortData tempListn; int len = 1; while ( len n ) MergePass ( initList, tempList, len ); len *= 2;MergePass ( tempList, initList, len ); len *= 2; 87在迭代的歸并排序算法中, 函數(shù)MergePass( ) 做一趟兩路歸并排序, 要調(diào)用merge ( )函數(shù) n/(2*len) O(n/len) 次, 函數(shù)MergeSort( )調(diào)用MergePass( )正好log2n 次,而每次merge( )要執(zhí)行比較O(len)次, 所以算法總的

59、時(shí)間復(fù)雜度為O(nlog2n)。歸并排序占用附加存儲(chǔ)較多, 需要另外一個(gè)與原待排序?qū)ο髷?shù)組同樣大小的輔助數(shù)組。這是這個(gè)算法的缺點(diǎn)。歸并排序是一個(gè)穩(wěn)定的排序方法。88只需要一個(gè)附加存儲(chǔ)的兩路歸并算法設(shè)算法中參加歸并的兩個(gè)歸并段是 Aleft Amid 和 Amid+1Aright，歸并后結(jié)果歸并段放在原地。 08 21 25 49 62 72 16 37 54 left mid mid+1 rightA08 1608 21 25 49 6216 37 54 Atemp = 7289left mid mid+1 right08 16 21 25 49 6216 37 54 Atemp = 7208

60、 16 21 25 49 6237 54 Atemp = 7208 16 21 25 49 6237 54 72 A 08 16 21 25 49 62 37 54 72 A21 37 08 16 21 25 49 62 37 54 72 A25 3790left mid mid+1 right08 16 21 25 4937 54 72 Atemp = 6208 16 21 25 37 4937 54 72Atemp = 6208 16 21 25 37 4954 62 72 A08 16 21 25 37 4954 62 72 A49 5408 16 21 25 37 4954 62 72