《《算法與數(shù)據(jù)結(jié)構(gòu)》第8章排序及基本算法ppt.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》第8章排序及基本算法ppt.ppt（151頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、算法與數(shù)據(jù)結(jié)構(gòu),第8章 排序及基本算法,排序及基本算法,為了便于檢索，人們通常希望能在計(jì)算機(jī)中保存的數(shù)據(jù)是按關(guān)鍵字值大小排列的有序表。 這是因?yàn)閷τ谟行虮砜梢圆捎脵z索效率較高的二分法檢索算法，其平均檢索長度為log2(n+1)-1;而對于無序表只能進(jìn)行順序檢索，其平均檢索長度為(n+1)/2。 又如為了方便檢索，需要構(gòu)造二叉檢索樹、B樹和B+樹等樹表，構(gòu)造這些樹表的過程本身就是一個(gè)排序的過程。 在現(xiàn)今的計(jì)算機(jī)系統(tǒng)中，有相當(dāng)大的一部分CPU時(shí)間開銷是用于對數(shù)據(jù)的排序整理上的。 因此，學(xué)習(xí)和研究各種排序算法，分析并設(shè)計(jì)出高效適用的排序算法，是擺在計(jì)算機(jī)科學(xué)工作者面前的重要課題之一。,第8章 排序及

2、基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,8.1 排序的基本概念,排序是數(shù)據(jù)處理中的重要運(yùn)算，其功能是將一組數(shù)據(jù)元素（或記錄）的任意序列，經(jīng)重新排列整理成為按關(guān)鍵字值大小有序的序列。 排序的實(shí)際應(yīng)用領(lǐng)域也是非常廣泛的。例如在實(shí)際問題的數(shù)據(jù)處理中常會遇到這樣的情況，需要把若干名字如人名、地名、國名、書名、校名、物名等按字母順序列表；需要把若干數(shù)值如各種考試分?jǐn)?shù)、田賽的長度、徑賽的時(shí)間等按成績次序排名；需要把若干不同屬性的記錄按照某種方法排列次序。所有這些都

3、是排序問題，都需要把一組數(shù)據(jù)元素或記錄按照某種特定的次序排列起來。,排序的基本概念（續(xù)）,排序的確切定義可以描述為： 設(shè)（R1，R2 Rn）是某文件的n個(gè)記錄，其相應(yīng)的關(guān)鍵字為（K1，K2 Kn）。 排序（sort）是這樣一種操作，它確定文件中n個(gè)記錄的一種排列（Rj1，Rj2 Rjn），使得其相應(yīng)關(guān)鍵字滿足遞增（即不減）關(guān)系Kj1Kj2Kjn或遞減（即不增）關(guān)系Kj1Kj2Kjn。 若關(guān)鍵字滿足遞增（即不減）關(guān)系時(shí)，稱作按關(guān)鍵字升序排序(ascending sort)； 若關(guān)鍵字滿足遞減（即不增）關(guān)系時(shí)，稱作按關(guān)鍵字降序排序(descending sort)。,排序的基本概念（續(xù)）,在前面定

4、義中，關(guān)鍵字Ki(i=1，2 n)稱作排序碼（sort code）。 排序碼可以是記錄的主關(guān)鍵字，也可以是次關(guān)鍵字，或者是多個(gè)關(guān)鍵字的組合（即組合關(guān)鍵字）。 當(dāng)排序碼是主關(guān)鍵字時(shí)，由于主關(guān)鍵字可以惟一標(biāo)識一個(gè)記錄，所以排序結(jié)果是惟一的。 當(dāng)排序碼是次關(guān)鍵字時(shí)，同一關(guān)鍵字值可能標(biāo)識了兩個(gè)或兩個(gè)以上的記錄，所以排序結(jié)果不惟一。,排序的基本概念（續(xù)）,若相同關(guān)鍵字值的記錄在排序前后的相對位置不會發(fā)生改變，即若Ri與Rj的關(guān)鍵字相同（Ki=Kj）且在排序前Ri在Rj之前，排序后的Ri仍在Rj之前，則稱所用的排序算法是穩(wěn)定的(stable)； 否則，若排序前后相同關(guān)鍵字值的記錄其相對位置可能發(fā)生改變，即

5、排序之后的序列中有可能出現(xiàn)Rj在Ri之前的情況，則稱所用的排序算法是不穩(wěn)定的。 當(dāng)排序碼是組合關(guān)鍵字時(shí)，通常稱作多關(guān)鍵字排序，其排序結(jié)果的惟一性取決于組合關(guān)鍵字是否能惟一標(biāo)識一個(gè)記錄。,排序的分類,根據(jù)排序過程中待排序文件存放的位置不同，可以把排序分為內(nèi)部和外部排序兩大類。 內(nèi)部排序是指待排序文件放在內(nèi)存中進(jìn)行排序的排序；內(nèi)部排序適用于記錄個(gè)數(shù)不很多的較小待排序文件的排序； 外部排序是指在待排序文件很大時(shí)，內(nèi)存中不能一次容納全部記錄，還要借助于外存存放待排序文件，在排序過程中需要對外存進(jìn)行訪問的排序；外部排序則適用于記錄個(gè)數(shù)太多不能一次全部放入內(nèi)存的較大待排序文件的排序。,排序的分類（續(xù)）,按

6、排序中所用策略的不同： 內(nèi)部排序通?？梢苑譃椴迦肱判?、選擇排序、交換排序、歸并排序和分配排序這五類，每一類中不同的排序算法都是基于同一策略的不同方法。 外部排序多是采用多路歸并方法進(jìn)行排序。,內(nèi)部排序文件的組織形式,每種內(nèi)部排序方法均可在不同的存儲結(jié)構(gòu)上實(shí)現(xiàn)。通常待排序文件的組織形式有三種方式： 以一維數(shù)組作為組織形式，排序過程是對記錄本身進(jìn)行物理重排，通過比較和判定把記錄移動到合適的位置； 以鏈表（動態(tài)鏈表或靜態(tài)鏈表）作為組織形式，排序過程中無需移動記錄，僅需修改指針即可，通常把這類排序稱為表排序； 為待排序文件組織一個(gè)輔助表，如組織一張含關(guān)鍵字和指向記錄指針的索引表，在排序過程中只需對輔助

7、表的表目進(jìn)行物理重排，不需移動記錄本身，在排序結(jié)束后按輔助表調(diào)整記錄位置。,排序的基本概念（續(xù)）,排序的方法很多，每一種方法都有自己的優(yōu)缺點(diǎn)，適用于在不同的環(huán)境下使用，很難說哪一種方法是最好的方法。 由于所需的輔助空間的量一般都不大，所以排序的時(shí)間代價(jià)是衡量排序算法的最重要的因素。 內(nèi)部排序的時(shí)間代價(jià)主要用關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)來衡量； 而外部排序的時(shí)間代價(jià)主要用訪問外存儲器的次數(shù)來衡量。,排序的基本概念（續(xù)）,在本章主要討論內(nèi)部排序算法，以記錄數(shù)組作為待排序文件的組織形式，并假定關(guān)鍵字均為整數(shù)，按遞增次序討論排序算法（即討論升序排序問題）。 待排序文件中記錄結(jié)構(gòu)類型定義如下： ty

8、pedef struct int key; /*關(guān)鍵字*/ elemtype otheritems; /*其它域*/ recordtype /*記錄類型標(biāo)識符*/,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,插入排序,插入排序的基本方法是：每次將一個(gè)待排序的記錄Ri，按其關(guān)鍵字Ki的大小插入到前面已經(jīng)排好序的部分文件中的適當(dāng)位置，直到全部記錄插完整個(gè)文件已排好序?yàn)橹埂?本節(jié)介紹的插入排序方法有直接插入排序和希爾排序；并簡介二分法插入排序、二路

9、插入排序和共享?xiàng)２迦肱判颉?8.2 插入排序,8.2.1 直接插入排序 8.2.2 希爾排序 8.2.3 其它插入排序簡介,直接插入排序,直接插入排序（straight insertion sort）是一種最簡單的排序方法。 它的基本思路是： 依次把待排序的記錄逐個(gè)插入已排好序的序列中。 一開始，第一個(gè)記錄是一個(gè)長度為1的有序序列； 從第二個(gè)記錄起，每次用第i(i=2，3 n)個(gè)記錄的關(guān)鍵字Ki與前面有序序列中記錄的關(guān)鍵字Ki-1、Ki-2 K1進(jìn)行比較，從而找到Ki所在記錄應(yīng)該插入的位置并依次后移各記錄后插入之，使得有序序列的長度加1； 這樣插入n-1次就會得到n個(gè)記錄的有序序列，從而完成整

10、個(gè)文件的排序工作。,直接插入排序舉例,例如，已知待排序文件中記錄的關(guān)鍵字序列為（23，48，32，107，86，75，68），直接插入排序的過程可示意如下：,其中，方括號表示已排好序的序列，i表示插入第i個(gè)記錄。,直接插入排序（續(xù)）,在插入第i個(gè)記錄時(shí)，用Ki和前面已排好序記錄的關(guān)鍵字比較，若Ki小則后移一個(gè)記錄，直到Ki不小于時(shí)插入位置找到了，直接插入Ki完成第i個(gè)記錄的插入。 由于后移操作會覆蓋第i個(gè)記錄，在算法描述中可在進(jìn)行第i個(gè)記錄插入之前，先保存其于R0中再進(jìn)行比較后移操作；這個(gè)附加的R0還可起到“監(jiān)視哨”的作用，即當(dāng)Ki小于前面有序序列中的每一個(gè)關(guān)鍵字時(shí)，在和R0中關(guān)鍵字（它本身）

11、比較時(shí)不會小于，既找到了正確的插入位置，又避免了循環(huán)控制變量的越界檢查。 設(shè)置監(jiān)視哨是一種程序設(shè)計(jì)技巧，既使程序控制簡單，又節(jié)省了測試時(shí)間提高了檢索效率。,直接插入排序的算法描述,直接插入排序的算法描述如下： void insertsorting(recordtype R,int n) int i,j; for(i=2;i=n;i+) R0=Ri; j=i-1; while(R0.key Rj.key) Rj+1 = Rj; j-; Rj+1=R0; /*insertsorting end*/,直接插入排序的算法分析,在上面的算法中，外層for循環(huán)控制n-1趟插入，內(nèi)層while循環(huán)完成一趟的

12、關(guān)鍵字比較、記錄后移和確定位置后的插入操作。 算法中的主要時(shí)間開銷在于關(guān)鍵字的比較和記錄的后移操作上。 在最好的情況下是待排序文件中各記錄已經(jīng)按關(guān)鍵字遞增有序，每一趟只需一次比較操作和兩次移動操作（即Ri=R0和R0=Ri）,無需記錄后移；其比較次數(shù)為n-1次，移動操作次數(shù)為2（n-1）次，算法的時(shí)間復(fù)雜度為O(n)。,直接插入排序的算法分析(續(xù)),在最壞的情況下是待排序文件中各記錄為關(guān)鍵字的逆序排列（即遞減序列），每一趟中需要和前面已排好序的i-1個(gè)記錄以及監(jiān)視哨中R0進(jìn)行關(guān)鍵字值的比較，即第i趟中需進(jìn)行i次比較操作； 向后移動次數(shù)為i-1次，加上與監(jiān)視哨之間的兩次移 動，第i趟需要移動記錄

13、i+1次；總的比較次數(shù)為 次，總的移動次數(shù)為 次，算法的時(shí)間復(fù)雜度為O(n2)。,直接插入排序的算法分析(續(xù)),若初始文件中各記錄是隨機(jī)排列，即關(guān)鍵字的各種排列的出現(xiàn)概率相同時(shí)，我們可取上述最好與最壞情況的平均值作為比較和移動的平均次數(shù)，約為n2/4,由此可得直接插入排序的時(shí)間復(fù)雜度為O(n2)。 由于直接插入排序在整個(gè)排序過程中只需一個(gè)記錄的輔助空間（即R0），所以其空間復(fù)雜度為O(1)。由于對于相同關(guān)鍵字值的記錄在排序前后相對位置不會發(fā)生變化（如上例中的48和 ），所以直接插入排序是一種穩(wěn)定的排序方法。,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希爾排序 8.2.3 其它插入

14、排序簡介,希爾排序,希爾排序（shells method），又稱作縮小增量排序（diminishing increatment）。它是1959年由D.L.Shell提出來的對直接插入排序的一種改進(jìn)方法。 希爾排序是不穩(wěn)定的排序算法。 由直接插入排序的分析可知，在待排序文件已按關(guān)鍵字值遞增有序時(shí)的時(shí)間復(fù)雜度為O(n)，在逆序時(shí)的時(shí)間復(fù)雜度為O(n2)。 換句話說，如果待排序文件能夠基本有序，則文件中的大多數(shù)記錄都不需要進(jìn)行插入（即后移）操作，整個(gè)排序的時(shí)間開銷就可以大大減少。 另外，當(dāng)n的值很小時(shí)，n2的值受n的值的影響也不太大，直接插入排序的效率也比較高。希爾排序正是基于這兩點(diǎn)考慮而得到的對直

15、接插入排序的一種改進(jìn)方法。,希爾排序的方法,希爾排序的方法是： 先選取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把待排序文件中的全部記錄分成d1個(gè)組，將所有距離為d1倍數(shù)的記錄放在同一個(gè)組中，在各組內(nèi)進(jìn)行直接插入排序； 然后選取第二個(gè)增量d2d1，重復(fù)上述的分組和排序工作；如此不斷地選取更小的增量d3，d4 并重復(fù)上述的分組和排序工作， 直到所選取增量di=1(didi-1d2d1)時(shí)所有記錄放在同一組中進(jìn)行直接插入排序后為止。,希爾排序的方法（續(xù)）,希爾排序方法的一開始組數(shù)較多而組中記錄較少，各組中記錄的直接插入排序是處在n值很小的情況下進(jìn)行，有著較高的效率；并且在不滿足次序時(shí)的移動，是用較少的移

16、動次數(shù)而得到了記錄的較大移動距離。 隨著di減小，組數(shù)變少組中記錄個(gè)數(shù)變多的同時(shí)，組中記錄也逐步變得基本有序，使得在一趟中進(jìn)行直接插入排序時(shí)的效率大大地提高。 所以希爾排序始終是在較高的效率下工作。希爾排序中增量di的選擇可以有不同的取法，一般是采用希爾在最早時(shí)提出的方法，即d1=,di+1=(i=2，3，4 )。 但也有人提出不同的di選取方法，如克努特（Knuth）提出的方法是d1=,di+1=(i=2，3，4 )。如何選取增量序列才能產(chǎn)生最好的排序效果，至今仍無法從數(shù)學(xué)角度得出圓滿的結(jié)論；然而逐步縮小增量和最后一次增量為1是大家不爭的事實(shí)。,希爾排序舉例,設(shè)待排序文件中有10個(gè)記錄，初始

17、關(guān)鍵字序列為(52,38,66,87,77,16,30,62,07)，增量序列依次為5,3,1，排序過程如下：,希爾排序舉例（續(xù)）,希爾排序舉例（續(xù)）,第一趟排序時(shí)d1=5，把待排序文件分成五組，即（R1，R6）、（R2，R7）、（R3，R8）、（R4，R9）和（R5，R10），各組中第一個(gè)記錄都自成長度為1的有序區(qū)，依次把各組的第二個(gè)記錄插入有序區(qū)中得到第一趟排序結(jié)果； 第二趟排序時(shí)d2=3，把待排序文件分成三組，即（R1，R4，R7，R10）、（R2，R5，R8）和（R3，R6，R9），對各組進(jìn)行直接插入排序后得到第二趟排序結(jié)果； 第三趟排序時(shí)d3=1，整個(gè)待排序文件為一組，對整個(gè)文件做直

18、接插入排序得到的第三趟排序結(jié)果，使整個(gè)待排序文件按關(guān)鍵字值有序，即得到最終的排序結(jié)果。,希爾排序的算法描述(不設(shè)置監(jiān)視哨),若不設(shè)置監(jiān)視哨，希爾排序的算法可描述如下： void shellsorting(recordtype R,int n) int i,j,d; d = n; do d = (d+1)/2; for(i = d+1;i d) /*shellsorting end*/,希爾排序（續(xù)）,需要說明的是，算法中沒有調(diào)用直接插入排序算法insertsorting，而是獨(dú)立設(shè)計(jì)直接插入排序的部分；這是因?yàn)橄柵判蛑芯嚯x為d的倍數(shù)的記錄為一組，組中成員記錄之間有間隔不連續(xù)不能直接調(diào)用的緣故

19、。 另外，在for循環(huán)中的分組執(zhí)行直接插入排序的過程，是依次先插入d個(gè)組中的第二個(gè)記錄，再插入d個(gè)組中的第三個(gè)記錄最后插入d個(gè)組中的最后一個(gè)記錄；是d個(gè)組的交替插入過程，而不是一個(gè)組的直接插入排序完成后再進(jìn)行下一組，這樣有利于算法設(shè)計(jì)的簡潔性和算法描述的方便性。,希爾排序（續(xù)）,如果考慮設(shè)置監(jiān)視哨，很自然地會考慮到仿照直接插入排序算法中的監(jiān)視哨設(shè)置辦法。對于增量為d的一趟希爾排序，待排序文件被分成d 組，各組中記錄之間的距離為d；需要在R1到Rd處設(shè)置監(jiān)視哨，而在Rd+1到Rd+n處安排待排序文件中的n個(gè)記錄。由于在各趟排序中的增量d1,d2 di是逐次縮小的，而待排序文件中各記錄的位置空間安

20、排好之后不宜變動（移動需時(shí)間開銷），所以d可選為di中的最大值d1，即一次性安排監(jiān)視哨空間并固定不變； 另外，監(jiān)視哨中的值應(yīng)在不同組中的不同記錄插入時(shí)安排不同的值（即待插入記錄的值），但是多次更換監(jiān)視哨中的值既繁瑣又影響效率，我們可以考慮在排序之前一次性設(shè)置各監(jiān)視哨的值，可設(shè)置為不超過待排序文件中最小關(guān)鍵字值的某一個(gè)值如-maxint。這種監(jiān)視哨的設(shè)置方法，沒有在監(jiān)視哨中保存各組中的一個(gè)個(gè)待插入記錄，但可以統(tǒng)一保存待插入記錄于R0中。,希爾排序的算法描述(設(shè)置監(jiān)視哨),設(shè)置監(jiān)視哨的希爾排序算法可描述如下： void shellsort(recordtype R,int n) int i,j,d

21、; for(i=1;i 1); /*shellsort end*/,希爾排序的算法分析,在前面給出的兩個(gè)算法，除了是否設(shè)置監(jiān)視哨外，排序的方法是相同的，其時(shí)間復(fù)雜度也是相同的；其增量序列為d1= ，di= (i2)。算法中的主要時(shí)間開銷在于三重循環(huán)： 外層do-while循環(huán)控制排序趟數(shù)，共執(zhí)行l(wèi)og2n次。 中層的for循環(huán)控制一趟中各組記錄的直接插入排序，執(zhí)行次數(shù)依次為 次；其平均次數(shù)為 ；即中層for循環(huán)的平均執(zhí)行次數(shù)不超過n。 內(nèi)層的while循環(huán)確定各組中每個(gè)記錄的插入位置，進(jìn)行關(guān)鍵字的比較和記錄的移動操作；,希爾排序的算法分析（續(xù)）,在最好的情況下只執(zhí)行一次比較而無記錄移動，其一趟

22、中總的比較次數(shù)與中層for循環(huán)的執(zhí)行次數(shù)相同，為 ； 而一趟中執(zhí)行插入的次數(shù)為n-di，即平均比較次數(shù)不超過 ,更不會超過log2n次； 由于希爾排序算法中開始時(shí)兩個(gè)記錄一組，以后隨著組數(shù)的減少組中記錄增多也逐步基本有序，所以在n較大時(shí)的其它情況下的平均比較次數(shù)也是接近于最好情況下的次數(shù)log2n或是它的線性函數(shù)，而移動次數(shù)或平均移動次數(shù)是遠(yuǎn)遠(yuǎn)小于比較次數(shù)和平均比較次數(shù)的； 由此得內(nèi)層while循環(huán)的平均執(zhí)行次數(shù)為O(log2n)階函數(shù)。由算法分析的乘法法則可知，前面給出的兩個(gè)希爾排序算法，shellsorting和shellsort的時(shí)間復(fù)雜度為O(n(log2n)2)。,8.2 插入排序,

23、8.2.1 直接插入排序 8.2.2 希爾排序 8.2.3 其它插入排序簡介,1.二分法插入排序,由第七章的討論我們知道，對有序表采用二分法檢索，檢索性能大大優(yōu)于順序檢索。 如果我們把直接插入排序中的由后向前順序檢索尋找插入位置的方法改為用二分法檢索來實(shí)現(xiàn)，當(dāng)n較大時(shí)就可以大幅度地降低關(guān)鍵字的比較次數(shù)。我們把經(jīng)過這種改進(jìn)后的插入排序方法，稱作二分法插入排序（binary insertion sort）。 二分法插入排序與直接插入排序相比較，僅是減少了尋找插入位置時(shí)的關(guān)鍵字比較次數(shù)，記錄的移動次數(shù)沒有改變，其時(shí)間復(fù)雜度仍為O(n2)； 所需的輔助存儲空間也與直接插入排序相同，也是穩(wěn)定的排序方法（

24、在檢索位置出現(xiàn)關(guān)鍵字值相等時(shí)需后移插入位置指示器變量，否則為不穩(wěn)定方法）。,2.二路插入排序,二路插入排序（2-way insertion sort）是在二分法插入排序基礎(chǔ)上的進(jìn)一步改進(jìn)，改進(jìn)的目標(biāo)是減少排序過程中記錄的移動次數(shù)，但為此多開銷了n個(gè)記錄大小的輔助存儲空間。 其具體方法是： 另設(shè)一個(gè)和R同類型的數(shù)組S，先將R1賦給S1，并將S1看成是在已排好序序列中處于中間位置的記錄； 然后從R中第二個(gè)記錄起，依次插入到S1之前或S1之后的有序序列中去， 若待插記錄的關(guān)鍵字小于S1.key則插入S1之前的有序表中，否則插入S1之后的有序表中。 在算法實(shí)現(xiàn)時(shí)，把S數(shù)組看成是一個(gè)循環(huán)數(shù)組，并設(shè)兩個(gè)指

25、針first和final分別指示排序過程中得到的有序序列中的第一個(gè)記錄和最后一個(gè)記錄在S中的位置。,二路插入排序舉例,二路插入排序舉例（續(xù)）,二路插入排序（續(xù)）,在二路插入排序中，記錄的移動次數(shù)約為n2/8，比直接插入排序減少移動次數(shù)約一半。它只能減少移動次數(shù)而不能絕對避免移動記錄，若要大幅度降低移動次數(shù)，可改變存儲結(jié)構(gòu)為靜態(tài)鏈表，進(jìn)行表插入排序。 此外，二路插入排序中，當(dāng)R1為待排序文件中最小或最大關(guān)鍵字的記錄時(shí)，完全失去優(yōu)越性退化為直接插入排序的時(shí)間效率。 二路插入排序，是一種穩(wěn)定的排序方法。,3.共享?xiàng)２迦肱判?共享?xiàng)２迦肱判颍╯hared stack insertion sort）也是

26、對直接插入排序的一種改進(jìn)方法。 其基本思想是： 把待排序的記錄數(shù)組R看作是一個(gè)靜態(tài)的共享?xiàng)＃?和棧2），棧1按數(shù)組下標(biāo)由小到大方向增長，棧2按數(shù)組下標(biāo)由大到小方向增長；棧1中按關(guān)鍵字升序排列壓入待排序記錄，棧2中按關(guān)鍵字降序排列壓入待排序記錄。 一開始先比較R1和Rn的關(guān)鍵字值大小，若R1Rn則交換；top1=1,top2=n； 然后把R2到Rn-1逐一插入兩個(gè)棧中，插入的過程中始終保證棧1的棧頂記錄的關(guān)鍵字值都不大于棧2 的棧頂記錄的關(guān)鍵字值。,共享?xiàng)２迦肱判颍ɡm(xù)）,為此需要區(qū)分以下三種情況并作相應(yīng)處理： 當(dāng)待插入記錄Ri的關(guān)鍵字值不小于棧1 的棧頂記錄的關(guān)鍵字值且不大于棧2的棧頂記錄的關(guān)

27、鍵字值時(shí)，將待插記錄壓入棧1中。即Ri.keyRtop1.key且Ri.keyRtop2.key時(shí)進(jìn)棧1，只須改變top1的值為top1+1即可。 當(dāng)Ri.keytop2.key時(shí)，由棧2反復(fù)傳送記錄到棧1，直到Ri.keytop2.key時(shí)將Ri插入棧2。由棧2傳送到棧1一個(gè)記錄，需要把Ri+1到Rtop2-1的記錄后移一個(gè)位置。,共享?xiàng)２迦肱判蚺e例,共享?xiàng)２迦肱判蚺e例（續(xù)）,共享?xiàng)２迦肱判颍ɡm(xù)）,共享?xiàng)２迦肱判虿恍枰黾宇~外的存儲開銷，在時(shí)間性能上與二路插入排序相當(dāng)，而且有效地避免了因R1為待排序記錄中關(guān)鍵字值為最大或最小記錄時(shí)完全失去優(yōu)越性的不足。 若增加存儲開銷另設(shè)與R相同類型的數(shù)組作

28、為共享?xiàng)＃瑒t可以進(jìn)一步減少移動次數(shù)，且排序結(jié)果不象二路插入排序那樣要使用循環(huán)數(shù)組解釋。 共享?xiàng)２迦肱判蚴且环N穩(wěn)定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,交換排序,交換排序的基本方法是，兩兩比較待排序記錄的關(guān)鍵字值，并交換那些不滿足順序要求的記錄對，直到全部待排序記錄都已滿足順序要求時(shí)為止。 本節(jié)介紹兩種交換排序的方法： 一種是冒泡排序， 一種是快速排序。,8.3 交換排序,8.3.1 冒泡排序 8.3.2 快速排序,冒泡排序

29、,冒泡排序（bubble sort）也稱作起泡排序，是一種簡單的排序方法。 它是通過相鄰記錄之間的關(guān)鍵字比較和記錄交換，使關(guān)鍵字值較小的記錄由底部向上移動，而關(guān)鍵字值較大的記錄由頂部向下移動，就象水中的氣泡向上飄?。芭荩┮粯?。,冒泡排序算法,冒泡排序的具體做法是： 將關(guān)鍵字縱向排列，然后自下而上地對相鄰兩個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序（即Rj-1.keyRj.key，j=n,n-12）則交換兩個(gè)記錄，直到全部記錄都比較和交換完畢（即j=2），第一趟冒泡排序結(jié)束； 此時(shí)最小關(guān)鍵字值的記錄上浮到了R1的位置上。然后對n-1個(gè)記錄重復(fù)類似的操作，次小關(guān)鍵字值的記錄上浮到R2的位置上。 重復(fù)進(jìn)行這

30、樣的過程，直到?jīng)]有記錄需要交換為止（最多需n-1趟冒泡排序），整個(gè)待排序文件就按關(guān)鍵字值升序排列完畢。,冒泡排序算法舉例,例如，對于8個(gè)記錄的關(guān)鍵字序列（46，26，43，18，74，21, ,57），冒泡排序的過程如下圖所示：,冒泡排序算法（續(xù)）,由該冒泡排序的實(shí)例，也證實(shí)了至多需要n-1趟冒泡排序即可完成整個(gè)排序。 事實(shí)上存在不需要n-1趟就可以完全排好序的情況，如上例的第五趟排序后就已經(jīng)排好序了； 其識別辦法是，若某一趟冒泡排序過程中沒有進(jìn)行記錄的位置交換，則說明待排序文件已經(jīng)完全排好序了。 為此，需在算法中引入一個(gè)交換狀態(tài)變量flag，在每一趟排序之前置flag為0，每次交換時(shí)給fla

31、g加1，若一趟結(jié)束時(shí)flag為0則終止算法。,冒泡排序的算法描述,void bubblesort(recordtype R,int n) int i,j,flag; recordtype temp; for(i=1;i= i+1;j-) if(Rj-1.key Rj.key) temp=Rj-1; Rj-1=Rj; Rj=temp; flag=flag+1; /*置已交換標(biāo)志*/ if(flag=0) break; /*bubblesort end */,冒泡排序算法分析,冒泡排序也是一種穩(wěn)定的排序方法。 其時(shí)間復(fù)雜度可以如下分析： 在最好的情況下，是初始記錄的關(guān)鍵字已遞增有序時(shí)，只需一趟排序

32、，比較次數(shù)為n-1，沒有交換記錄即記錄的移動次數(shù)為0； 在最壞的情況下，是初始記錄遞減有序（即逆序）時(shí)，需進(jìn)行n-1趟排序，比較次數(shù)為 ，交換次數(shù)為 ，每次交換需三次移動記錄，其移動次數(shù)為 。 在平均情況下，關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)大約為最壞情況下的一半，因此冒泡排序算法的時(shí)間復(fù)雜度為O(n2)。,冒泡排序算法分析（續(xù)）,上述的冒泡排序算法還可以作一些改進(jìn)來提高排序速度，比如： 在每趟排序中記住最后一次發(fā)生交換記錄的位置K，因?yàn)槲恢肒之前的記錄都已排好了序，下一趟的排序可以終止于位置K而不必進(jìn)行到預(yù)定的下界位置i。 在排序過程中交替變化掃描比較的方向，即前一趟由后向前掃描，后一趟則由前

33、向后掃描，而不是一直都由后向前掃描。由后向前掃描比較交換一趟，可使最輕的氣泡上浮到頂部，但只能使最重的氣泡下沉一個(gè)位置；由前向后掃描比較交換一趟，可使最重的氣泡下沉到底部，但只能使最輕的氣泡上浮一個(gè)位置。交替變化掃描方向可以加速最輕和最重的氣泡向兩端迅速沉浮，有利于加速排序過程。,8.3 交換排序,8.3.1 冒泡排序 8.3.2 快速排序,快速排序,快速排序（quick sort）也稱作分區(qū)交換排序，是對冒泡排序的一種改進(jìn)排序方法。它是目前各種內(nèi)部排序方法中較快的方法，故稱之為快速排序。 快速排序的基本思想是： 在待排序文件的n個(gè)記錄中，任取一個(gè)記錄（通常是選取第一個(gè)記錄）作為基準(zhǔn)； 經(jīng)過一

34、趟排序后以基準(zhǔn)記錄的關(guān)鍵字把全部記錄分為兩部分，所有關(guān)鍵字值比基準(zhǔn)記錄關(guān)鍵字值小的記錄都排列在基準(zhǔn)記錄之前，而所有關(guān)鍵字值比基準(zhǔn)記錄關(guān)鍵字值大的記錄都排列在基準(zhǔn)記錄之后； 然后對基準(zhǔn)記錄前后的這兩個(gè)部分分別重復(fù)這樣的過程，得到本趟排序的兩個(gè)新到位的基準(zhǔn)和四個(gè)部分如此重復(fù)上述過程，直到每一個(gè)部分只剩下一個(gè)記錄（即全部到位）時(shí)為止。,快速排序算法,設(shè)兩個(gè)指示器變量i和j，分別指向待排序區(qū)間的第一個(gè)記錄和最后一個(gè)記錄； 先將第一個(gè)記錄移到暫存變量temp中，然后j從區(qū)間的最后一個(gè)記錄起向前掃描，直到找到滿足Rj.keytemp.key的記錄時(shí)，將Ri移入Rj中； 就這樣j自j-1從后向前掃描一次移入

35、一個(gè)Rj于Ri中，i自i+1從前向后掃描一次移入一個(gè)Ri于Rj中，反復(fù)交替的掃描和移動記錄； 直到i=j時(shí)把temp移入Ri中（區(qū)間中第一個(gè)記錄應(yīng)在的位置），它把整個(gè)待排序區(qū)間分割為相互獨(dú)立的兩個(gè)更小的區(qū)間。,快速排序的算法描述,這種把一個(gè)待排序區(qū)間通過基準(zhǔn)記錄（第一個(gè)記錄）分割成為兩個(gè)區(qū)間的一次分割排序算法如下： int divideareasort(recordtype R,int s,int t) int i,j; recordtype temp; i=s; j=t; temp=Rs; do while(Rj.key=temp.key),快速排序的算法描述（續(xù)）,while(Ri.key

36、=temp.key) /*divideareasort end*/,快速排序的算法描述（續(xù)）,對于待排序文件R利用一次分割區(qū)間排序算法時(shí)，令s=1和t=n即可完成第一趟排序；由此得到的兩個(gè)更小的區(qū)間R1i-1和Ri+1n，繼續(xù)利用算法divideareasort分割為更小的四個(gè)區(qū)間；如此一直進(jìn)行下去，直到都分割為只有一個(gè)記錄時(shí)排序結(jié)束。調(diào)用divideareasort對R 進(jìn)行快速排序的遞歸算法可描述如下： void quicksort(recordtype R,int s,int t) int i; if(st) i=divideareasort(R,s,t); quicksort(R,s,

37、i-1); quicksort(R,i+1,t); /*quicksort end*/,快速排序的算法舉例,下面我們使用快速排序算法對關(guān)鍵字序列（36，73，65，97，13，27， ，29）排序，在下面的排序過程示例中，先給出第一趟中的區(qū)間分割的整個(gè)過程，然后給出各趟的排序結(jié)果；用方括號表示區(qū)間，用方框表示暫存變量temp的關(guān)鍵字值（并未參加交換，在分割完成后才放入最終位置上）。,快速排序的算法舉例（續(xù)）,快速排序的算法舉例（續(xù)）,快速排序的算法舉例（續(xù)）,快速排序的算法分析,快速排序過程中各趟中所選擇的基準(zhǔn)可以用一棵二叉樹來表示，如上例中的基準(zhǔn)二叉樹如右圖所示。基準(zhǔn)二叉樹反映了快速排序的遞

38、歸調(diào)用過程，也便于我們對快速排序算法進(jìn)行性能分析。,快速排序的基準(zhǔn)二叉樹是關(guān)鍵字的一棵二叉檢索樹，其中序遍歷序列就是關(guān)鍵字的升序排列。 在最好的情況下，基準(zhǔn)二叉樹是一棵理想的平衡二叉檢索樹，深度為 ，遞歸所需棧的存儲開銷為O(log2n)，時(shí)間開銷為結(jié)點(diǎn)數(shù)乘平均檢索長度，即O(nlog2n)。,快速排序的算法分析（續(xù)）,在最壞情況下，基準(zhǔn)二叉樹是一棵單枝二叉檢索樹，深度為n，存儲開銷為O(n)，時(shí)間開銷為O(n2)。 在平均情況下，基準(zhǔn)二叉樹是一棵隨機(jī)的二叉檢索樹，由于二叉檢索樹的平均檢索長度為O(log2n)，故時(shí)間開銷也是O(nlog2n)。 為了避免初始關(guān)鍵字序列有序或基本有序時(shí)快速排序

39、蛻化為冒泡排序（即基準(zhǔn)二叉樹為單枝或近似單枝二叉樹）的情況，通常采取“三者取中”的基準(zhǔn)記錄選取辦法改進(jìn)之。 所謂三者取中是指在Rs、Rt和R(s+t)/2三者中選取關(guān)鍵字值居中的記錄作為分割區(qū)間的基準(zhǔn)，這種選取基準(zhǔn)記錄的方法可以大大改善快速排序在最壞情況下的性能。 快速排序算法是一種不穩(wěn)定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,選擇排序,選擇排序的基本方法是，每次從待排序文件的各個(gè)記錄中，依次選出關(guān)鍵字值最小的記錄放在已排好

40、序的序列中，直到選完為止。 本節(jié)介紹： 直接選擇排序 樹型選擇排序 堆排序。,8.4 選擇排序,8.4.1 直接選擇排序 8.4.2 樹形選擇排序 8.4.3 堆排序,直接選擇排序,直接選擇排序（direct selection sort）也稱作簡單選擇排序。 其具體做法是： 對于待排序文件R1.n，通過比較首先選出關(guān)鍵字值最小的記錄與R1交換， 然后在其余記錄中選出次小關(guān)鍵字的記錄與R2交換 如此進(jìn)行n-1次的選擇與交換，R1.n中所有記錄就按關(guān)鍵字升序次序排列完畢。,直接選擇排序舉例,直接選擇排序的過程可示例如下：,直接選擇排序舉例（續(xù)）,直接選擇排序的算法描述,直接選擇排序的算法可描述如

41、下： void selectsort(recordtype R,int n) int i,j,m; recordtype temp; for(i=1;i=n-1;i+) m=i; for(j=i+1;i=n;j+) if(Rj.keyRm.key) m=j; if(m!=i) temp=Ri; Ri=Rm; Rm=temp; /*selectsort end*/,直接選擇排序的算法分析,直接選擇排序只需要一個(gè)記錄大小的輔助存儲空間用于記錄交換，其空間復(fù)雜度為O(1)。 在排序過程中至多進(jìn)行n-1趟排序，即至多交換記錄n-1次，做3(n-1)次記錄移動；然而不論初始狀態(tài)如何，在每一趟中都需要和所

42、有記錄的關(guān)鍵字進(jìn)行比較； 為了選出第i趟的最小關(guān)鍵字，需要的比較次數(shù)為n-i，總的比較次數(shù)為 。由此得到直接選擇排序的時(shí)間復(fù)雜度為O(n2)。 由于在直接選擇排序中存在著任意位置上的記錄互換的可能性，所以有可能改變具有相同關(guān)鍵字值的記錄的相對位置次序，如（5, ,2）的直接選擇排序結(jié)果為（2, ,5）； 因此直接選擇排序方法是不穩(wěn)定的。,8.4 選擇排序,8.4.1 直接選擇排序 8.4.2 樹形選擇排序 8.4.3 堆排序,樹形選擇排序,樹形選擇排序（tree selection sort）也稱作錦標(biāo)賽排序（tournament sort），這種排序方法是按照錦標(biāo)賽的思路進(jìn)行的。 錦標(biāo)賽是將

43、n個(gè)參賽選手兩兩之間進(jìn)行比賽（余下的一個(gè)輪空直接進(jìn)入下一輪比賽），勝出者再兩兩之間比賽，經(jīng)過 輪比賽后產(chǎn)生出第一名。 樹形選擇排序是將待排序的n個(gè)記錄的關(guān)鍵字作為完全二叉樹的葉子結(jié)點(diǎn)，依次兩兩之間比較，關(guān)鍵字值小者作為其雙親結(jié)點(diǎn)，最后若余下一個(gè)則輪空參加下一輪比較；然后對得到的這些雙親結(jié)點(diǎn)再兩兩之間比較產(chǎn)生其雙親結(jié)點(diǎn)（小者）如此經(jīng)過 輪比較后，關(guān)鍵字值最小的記錄就在根結(jié)點(diǎn)位置。,樹形選擇排序舉例,選擇關(guān)鍵字值最小的記錄放在根結(jié)點(diǎn)位置的過程如下圖(a)的二叉樹所示。接下來將最小關(guān)鍵字值改為，然后沿該結(jié)點(diǎn)到樹根的路徑依次進(jìn)行各分枝結(jié)點(diǎn)子女之間的比較，上升到根結(jié)點(diǎn)的是次小關(guān)鍵字值的記錄，如下圖(b)

44、所示；如此繼續(xù)進(jìn)行下去，直到所有記錄都已選出時(shí)為止。,樹形選擇排序算法分析,在樹形選擇排序中，除第一次選出最小關(guān)鍵字需n-1次比較外，選出次小關(guān)鍵字和其它關(guān)鍵字都需經(jīng)過從葉到根的路徑，即需進(jìn)行 次比較。 總的比較次數(shù)至多為 ，所以其時(shí)間復(fù)雜度為O(nlog2n)。 樹形選擇排序的缺點(diǎn)是需要的輔助空間較多，需要用n-1個(gè)記錄大小的空間來保存各層次的比較結(jié)果；此外，與進(jìn)行多余的比較也是其缺點(diǎn)之一。,8.4 選擇排序,8.4.1 直接選擇排序 8.4.2 樹形選擇排序 8.4.3 堆排序,堆排序,為了克服樹形選擇排序需要較多輔助空間保存比較結(jié)果和與進(jìn)行多余比較的缺點(diǎn)； 在1964年威洛姆斯（J.Wi

45、llioms）和弗洛伊德（Floyd）對樹形選擇排序進(jìn)行了改進(jìn)，提出了新的排序方法堆排序（heap sort）方法，使其比較次數(shù)達(dá)到樹形選擇排序的水平，同時(shí)又不會增加額外的存儲開銷，只需一個(gè)記錄大小的空間用于記錄間的交換。,堆的定義,堆的定義為，對于一個(gè)關(guān)鍵字序列（k1，k2 kn），當(dāng)且僅當(dāng)對于所有的i=1，2，都滿足下面的關(guān)系或都滿足下面的關(guān)系時(shí)，稱之為堆； 都滿足關(guān)系時(shí)稱之為最小值根堆； 都滿足關(guān)系時(shí)稱之為最大值根堆。 如果將與此序列對應(yīng)的一維數(shù)組看成是一棵完全二叉樹，則堆的含義表明完全二叉樹中任一非終端結(jié)點(diǎn)上的數(shù)據(jù)值均不大于（或不小于）其左孩子和右孩子結(jié)點(diǎn)的值。 因此在一個(gè)堆中，堆頂元

46、素（完全二叉樹的根）必為堆中的最?。ɑ蜃畲螅┰?，并且堆中的每一棵子樹也都是堆。,堆排序舉例,例如關(guān)鍵字序列（12，15，35，25，39，67）和序列（75，38，62，28，18，49）都是堆，前者是最小值根堆而后者是最大值根堆，其對應(yīng)的完全二叉樹分別如下圖的(a)和(b)所示。,堆排序的基本思想,堆排序的基本思想是，對待排序文件中的n個(gè)記錄，依它們的關(guān)鍵字值大小按堆的定義排成一個(gè)序列（稱之為建堆），從而輸出堆頂?shù)淖钚￡P(guān)鍵字（用最小值根堆排序）的記錄，然后對剩余的關(guān)鍵字再次建堆，便得到次小關(guān)鍵字的記錄，如此反復(fù)進(jìn)行輸出和建堆，直到全部記錄按關(guān)鍵字排成有序序列時(shí)為止。 由以上分析可知，要實(shí)現(xiàn)

47、堆排序需要解決如下兩個(gè)問題： 如何由關(guān)鍵字值的無序序列建成一個(gè)堆？即建初始堆問題； 如何在輸出堆頂記錄之后調(diào)整剩余記錄為一個(gè)新堆？即堆調(diào)整問題。,創(chuàng)建初始堆,先討論建初始堆問題。在1964年弗洛伊德（Floyd）提出了篩選法，其具體方法是 將待排序記錄的關(guān)鍵字分放到一棵完全二叉樹的各個(gè)結(jié)點(diǎn)中，此時(shí)的完全二叉樹一般不具備堆的特性。 然而所有i 的結(jié)點(diǎn)Ki都沒有孩子結(jié)點(diǎn)，以這樣的Ki為根的子樹已經(jīng)是堆了； 因此建初始堆可以從完全二叉樹的最后一個(gè)分枝結(jié)點(diǎn)Ki(i= )開始，通過調(diào)整逐步使以Ki、Ki-1、K1為根的子樹滿足堆的定義，直到以K1為根的樹滿足堆定義時(shí)初始堆建成。,創(chuàng)建初始堆（續(xù)）,在對K

48、i（i= ， -1 1）為根的子樹建堆的過程中，可能需要對記錄的位置進(jìn)行調(diào)整； 若在調(diào)整過程中使下一層已建成堆的子樹不滿足堆的定義，則要繼續(xù)向下層進(jìn)行調(diào)整，直到某一個(gè)下層滿足堆的定義時(shí)為止，最壞的情況下是這種調(diào)整可能一直延伸到樹的葉子結(jié)點(diǎn)。 這種方法就像過篩子一樣，把最小關(guān)鍵字值的記錄一層一層地篩選出來，最后輸出堆頂?shù)淖钚￡P(guān)鍵字記錄。,建初始堆（最小根堆）過程舉例,下圖給出了完全二叉樹表示的一組關(guān)鍵字值建初始堆的示例，所用關(guān)鍵字序列為（47，33，61，82，72，11，25， ）；由于n=8，故從第4個(gè)結(jié)點(diǎn)開始進(jìn)行調(diào)整。,建初始堆(最小根堆)過程舉例(續(xù)),堆排序過程舉例,現(xiàn)在討論堆調(diào)整的問

49、題。在輸出堆頂記錄之后，用堆中的最后一個(gè)記錄替代原堆頂記錄。 由于除根結(jié)點(diǎn)K1之外的所有子樹仍然具有堆的性質(zhì)，故只需要對根結(jié)點(diǎn)自上而下調(diào)整即可。 例如對上例所給的關(guān)鍵字序列，經(jīng)初始建堆后得到圖(a)所示的堆，同時(shí)得到堆頂?shù)淖钚￡P(guān)鍵字11所在的記錄； 然后輸出堆頂記錄（key=11）并用最后一個(gè)記錄（key=82）替代堆頂，如圖(b)所示。此時(shí)由于以K2和K3為根的子樹仍具有堆的特性，只需對根自上而下按堆的定義調(diào)整。 首先將堆頂元素K1與左右孩子K2和K3比較，若K1 K2且K1 K3不需調(diào)整已滿足堆定義；否則選擇K2和K3中關(guān)鍵字值小的記錄與堆頂記錄交換。,堆排序過程舉例（續(xù)）,由于K3K2且

50、K3K1，則82與25所在的兩個(gè)記錄交換位置； 又由于交換破壞了右子樹的堆，則需再次進(jìn)行類似的調(diào)整，直至進(jìn)行到葉子結(jié)點(diǎn)； 調(diào)整后的狀態(tài)如圖 (c)所示，即得到一個(gè)有n-1個(gè)記錄的新堆，同時(shí)得到次小關(guān)鍵字25所在的記錄。 反復(fù)重復(fù)以上過程，即可實(shí)現(xiàn)上例所給關(guān)鍵字序列所對應(yīng)的待排序文件的堆排序，其堆排序過程如下圖所示。,堆排序過程舉例（續(xù)）,堆排序過程舉例（續(xù)）,堆排序過程舉例（續(xù)）,由前面的討論我們知道，堆調(diào)整是從根結(jié)點(diǎn)向下的一個(gè)篩選過程； 而建初始堆是從最后一個(gè)分枝結(jié)點(diǎn)開始到根結(jié)點(diǎn)結(jié)束的多次向下的篩選過程。 所以設(shè)計(jì)一個(gè)篩選算法，完成對Rs.t（只有Rs不滿足堆特性，其它結(jié)點(diǎn)均滿足堆特性）進(jìn)行

51、篩選是至關(guān)重要的。,篩選算法的算法描述,void heapadjust(recordtype R,int s,int t) int i,j; recordtype temp; temp=Rs; i=s; j=2*i; while(jRj+1.key) j+; if(temp.keyRj.key) Ri=Rj; i=j; j=2*i; else j=t+1; Ri=temp; /*heapadjust end*/,堆排序的算法描述,有了上述調(diào)整堆的篩選算法，就可以很方便地設(shè)計(jì)完整的堆排序算法如下： void heapsort(recordtype R,int n) int i; recordty

52、pe temp; for(i=n/2;i=1;i-) heapadjust(R,i,n); for(i=n;i1;i-) temp=R1; R1=Ri; Ri=temp; heapadjust(R,1,i-1); /*heapadjust end*/,堆排序的算法分析,堆排序的性能分析如下：設(shè)表示堆的完全二叉樹深度為h，h= ，從根到葉的篩選過程中，關(guān)鍵字的比較次數(shù)至多為2（k-1）次，至多交換記錄k次。所以在建好堆后，排序過程的n-1次篩選中的比較次數(shù)不會超過下式的值： 而在建立初始堆時(shí)的比較次數(shù)不會超過4n次，因此堆排序在最壞情況下的時(shí)間復(fù)雜度為O(nlog2n)。 此外，堆排序所需的輔助

53、存儲空間少。 堆排序是一種不穩(wěn)定的排序方法。 堆排序適宜用于待排序文件中記錄較多的情況，因?yàn)槠渲饕獣r(shí)間開銷在于建堆和調(diào)整堆，記錄較少時(shí)不合算。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,歸并排序,歸并排序（merge sort）的基本思想是： 將一些已排序的子文件進(jìn)行合并而得到一個(gè)完整的有序文件。 歸并時(shí)只要比較各子文件的第一個(gè)記錄的關(guān)鍵字，其最小者就是全局最小者；取出它后繼續(xù)比較各子文件的第一個(gè)記錄的關(guān)鍵碼，就可以得到全局的次小者如此下去

54、就可完成排序任務(wù)。 假設(shè)待排序文件中含有n個(gè)記錄，我們可以把它看作是n個(gè)有序的子序列，每個(gè)有序子序列的長度為1；然后兩兩歸并得到個(gè)長度為2（其中最后一個(gè)長度可能為1）的有序子序列；再兩兩歸并得到長度為4的若干有序子序列如此這樣反復(fù)歸并，直到得到一個(gè)長度為n的有序序列時(shí)為止。這種排序方法稱為二路歸并排序（two-way merge sort）。,歸并排序舉例,例如，對于待排序文件的關(guān)鍵字序列（22，36，06，78，25，43，73，18，39，62，27，66，13），利用二路歸并排序的過程如下：,歸并排序舉例,由上述歸并排序過程可以看出，二路歸并的主要操作是把相鄰兩個(gè)有序序列歸并成為一個(gè)有序

55、序列；對于n個(gè)記錄的待排序文件，需要?dú)w并趟才能完成排序；每趟歸并使有序子序列的長度增加一倍，而使有序子序列的個(gè)數(shù)減少約一半。 下面，我們給出對相鄰兩個(gè)有序序列的歸并算法，并給出歸并排序的遞歸算法和非遞歸算法。,8.5 歸并排序,8.5.1 歸并相鄰兩個(gè)有序序列 8.5.2 二路歸并排序的遞歸算法 8.5.3 二路歸并排序的非遞歸算法,歸并相鄰兩個(gè)有序序列,在前面分析的基礎(chǔ)上，歸并相鄰兩個(gè)有序序列為一個(gè)有序序列的算法merge可描述如下： void merge(recordtype R,int L,int m,int h,recordtype R1) int i,j,k; i=L; /*i指向第

56、一個(gè)有序子序列的第一個(gè)記錄*/ j=m+1; /*j指向第二個(gè)有序子序列的第一個(gè)記錄*/ k=L; /*k指向結(jié)果有序序列的第一個(gè)位置*/ while(i=m),歸并相鄰兩個(gè)有序序列（續(xù)）,while(im，要么jh，使得最后的兩個(gè)while循環(huán)總有一個(gè)相當(dāng)于空語句，而另一個(gè)while循環(huán)把剩余記錄傳送到R1中。,8.5 歸并排序,8.5.1 歸并相鄰兩個(gè)有序序列 8.5.2 二路歸并排序的遞歸算法 8.5.3 二路歸并排序的非遞歸算法,二路歸并排序的遞歸算法,在前述算法merge的基礎(chǔ)上，可給出二路歸并排序的遞歸算法如下： void mergesortrecalg(recordtype R,

57、intL,int h,recordtype R1) int m; if(L=h) R1L=RL; else m=(L+h)/2; mergesortrecalg(R,L,m,R1); mergesortrecalg(R,m+1,h,R1); merge(R1,L,m,h,R); /*mergesortrecalg end*/ 對待排序文件R1.n中的n個(gè)記錄排序，只須用參數(shù)R、1、n調(diào)用該遞歸算法，即mergesortrecalg(R,1,n,R1)即可。,8.5 歸并排序,8.5.1 歸并相鄰兩個(gè)有序序列 8.5.2 二路歸并排序的遞歸算法 8.5.3 二路歸并排序的非遞歸算法,二路歸并排序

58、的非遞歸算法,在給出二路歸并排序的非遞歸算法之前，我們先討論一趟歸并排序的實(shí)現(xiàn)算法。 設(shè)R1.n中的有序子序列長度為len，只有最后一個(gè)有序子序列的長度有可能小于len，進(jìn)行兩兩有序的子序列歸并后的結(jié)果依次存放在R11.n中。 進(jìn)行一趟歸并排序時(shí)調(diào)用算法merge，依次對相鄰的兩個(gè)長度為len的有序子序列歸并；當(dāng)有序子序列為奇數(shù)個(gè)或雖為偶數(shù)個(gè)但最后一個(gè)有序子序列長度小于len時(shí)的兩種情況做特殊處理。,二路歸并排序的非遞歸算法(續(xù)),一趟歸并排序算法可描述如下： void mergepass(recordtype R,int len,int n,recordtype R1) int i=1; w

59、hile(i+2*len-1=n) merge(R1,i,i+len-1,i+2*len-1,R1); i=i+2*len; if(i+len-1n) merge(R,i,i+len-1,n,R1); else while(i=n) R1i=Ri; i+; /*mergepass end*/,二路歸并排序的非遞歸算法(續(xù)),在一趟歸并排序的基礎(chǔ)上，可以很方便地得到二路歸并排序的非遞歸算法如下： void mergesort(recordtype R,int n) int len=1; recordtype R1; while(lenn) mergepass(R,len,n,R1); len=2

60、*len; mergepass(R1,len,n,R); len=2*len; /*mergesort end*/,二路歸并排序的算法分析,如果把待排序文件R中的n個(gè)記錄看作葉子結(jié)點(diǎn)，把兩兩歸并得到的有序子序列看成是兩個(gè)歸并對象有序子序列的雙親結(jié)點(diǎn)，則歸并過程對應(yīng)由葉向根生成一棵二叉樹的過程，所以歸并排序的趟數(shù)為 ； 而每趟歸并需移動記錄n次（關(guān)鍵字比較約n次），由乘法準(zhǔn)則知二路歸并排序的時(shí)間復(fù)雜度為O(nlog2n)。 由于二路歸并排序過程中需要一個(gè)與待排序文件大小相同的輔助數(shù)組，所以其空間復(fù)雜度為O(n)。 二路歸并排序是一種穩(wěn)定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念

61、 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,二路歸并排序的算法分析,前面介紹的各種排序方法，都是通過對待排序文件中記錄的關(guān)鍵字值大小的比較來進(jìn)行的。 基數(shù)排序（radix sort）方法則不同，它不用進(jìn)行關(guān)鍵字值的大小比較，而是借助于多關(guān)鍵字排序的思想，通過對待排序記錄按單邏輯關(guān)鍵字進(jìn)行分配和收集來實(shí)現(xiàn)的一種排序方法。,8.6 基數(shù)排序,8.6.1 多關(guān)鍵字排序 8.6.2 鏈?zhǔn)交鶖?shù)排序,多關(guān)鍵字排序,我們先通過一個(gè)大家都熟悉的整理撲克牌的例子來說明多關(guān)鍵字排序的思想和方法。 撲克牌有兩

62、個(gè)關(guān)鍵字，即花色和點(diǎn)力；其次序定義為 花色：梅花方塊紅桃黑桃 點(diǎn)力：2345678910JQKA 并且花色的優(yōu)先級別高于點(diǎn)力，即高一級花色的最小點(diǎn)力2大于低一級花色的最大點(diǎn)力A。 因此，要比較任意兩張撲克牌的大小，方法是先比較花色，若花色相同時(shí)再比較點(diǎn)力。,多關(guān)鍵字排序（續(xù)）,如果要根據(jù)上述關(guān)系把一幅撲克牌整理為升序次序，即梅花2、梅花3 梅花A、方塊2 方塊A、紅桃2 紅桃A、黑桃2 黑桃A的次序，通常有如下兩種整理方法： 先按花色分成四堆，然后再按點(diǎn)力把每堆整理有序，最后按花色由低級花色到高級花色疊加在一起。 先按點(diǎn)力分成十三堆，然后按點(diǎn)力由小到大的順序收集在一起；再按花色不同分成四堆，最

63、后按花色順序收集起來。,多關(guān)鍵字排序（續(xù)）,前面兩種理牌的方法便是兩種多關(guān)鍵字排序的方法。上述的例子可以推廣到一般情況下： 設(shè)待排序文件R的n個(gè)記錄（R1,R2 Rn）中，每個(gè)記錄Ri都含有d個(gè)關(guān)鍵字位（ ），稱其中兩個(gè)記錄有序（即RiRj）是指滿足條件 ； 若對于任意記錄都滿足RiRj（1ijn），則稱待排序文件R有序；利用d個(gè)關(guān)鍵字位整理待排序文件R有序的過程，稱作多關(guān)鍵字排序。,多關(guān)鍵字排序（續(xù)）,多關(guān)鍵字排序的方法通常有兩種： 最高位優(yōu)先法（most significant digit first），簡稱MSD法。 它是先按最高關(guān)鍵字位 對待排序文件中的n個(gè)記錄排序，把待排序文件中n個(gè)

64、記錄分為若干堆，每個(gè)堆中都具有相同的 值； 然后在各個(gè)堆中再按關(guān)鍵字位 進(jìn)行排序，每個(gè)堆中的記錄又按 的值分成若干更小的堆 如此不斷地按d個(gè)關(guān)鍵字位把較大地堆分為較小的堆，直到用 對各個(gè)堆排序后，各個(gè)堆中的記錄依次排在一起便形成一個(gè)有序文件。,多關(guān)鍵字排序（續(xù)）, 是低位優(yōu)先法（least significant digit first），簡稱LSD法。 它是先按最低關(guān)鍵字位 對待排序文件中的n個(gè)記錄進(jìn)行排序，按 的值把待排序文件中的n個(gè)記錄分配到具有不同 值的若干個(gè)堆， 然后按 值從小到大的次序收集在一起；下一次再按高一位關(guān)鍵字位 的值進(jìn)行分配和收集，如此不斷地按更高一位關(guān)鍵字位進(jìn)行分配和收

65、集； 直到用 分配和收集之后，整個(gè)文件按多關(guān)鍵字位 有序。,多關(guān)鍵字排序（續(xù)）,顯然前述的撲克牌排序中， 第一種理排過程采用的是最高位優(yōu)先法（MSD法）， 而第二種理牌過程是采用最低位優(yōu)先法（LSD法）。 通過對上述兩種方法的比較可以看出其不同的特點(diǎn)： MSD法排序，是將待排序文件中所有記錄分成若干獨(dú)立的子堆，每個(gè)堆中記錄的排序是獨(dú)立進(jìn)行的； 而LSD 法排序時(shí)將待排序文件中所有記錄分成的若干子堆不獨(dú)立，堆中記錄的排序不能獨(dú)立進(jìn)行，需要進(jìn)行d趟的分配和收集來完成整個(gè)文件中記錄的排序。,8.6 基數(shù)排序,8.6.1 多關(guān)鍵字排序 8.6.2 鏈?zhǔn)交鶖?shù)排序,鏈?zhǔn)交鶖?shù)排序,基數(shù)排序就是按照LSD法，對待排序文件中各記錄用單邏輯關(guān)鍵字進(jìn)行分配和收集的一種排序方法。 假設(shè)含有n個(gè)記錄的待排序文件中，每個(gè)記錄的關(guān)鍵字由d 個(gè)關(guān)鍵字位 組成，并且每個(gè)關(guān)鍵字位的取值范圍都相同，即c1 crd（1jd）； 關(guān)鍵字位可能的取值個(gè)數(shù)rd稱為基數(shù)?；鶖?shù)的選擇和關(guān)鍵字位的分解因關(guān)鍵字的類型而異。 若關(guān)鍵字是十進(jìn)制整數(shù)時(shí)，則基數(shù)rd為10，c1=0，c1