《算法與數(shù)據(jù)結(jié)構(gòu)》第8章排序及基本算法ppt.ppt

算法與數(shù)據(jù)結(jié)構(gòu),第8章 排序及基本算法,排序及基本算法,為了便于檢索，人們通常希望能在計算機中保存的數(shù)據(jù)是按關(guān)鍵字值大小排列的有序表。 這是因為對于有序表可以采用檢索效率較高的二分法檢索算法，其平均檢索長度為log2(n+1)-1;而對于無序表只能進行順序檢索，其平均檢索長度為(n+1)/2。 又如為了方便檢索，需要構(gòu)造二叉檢索樹、B樹和B+樹等樹表，構(gòu)造這些樹表的過程本身就是一個排序的過程。 在現(xiàn)今的計算機系統(tǒng)中，有相當(dāng)大的一部分CPU時間開銷是用于對數(shù)據(jù)的排序整理上的。 因此，學(xué)習(xí)和研究各種排序算法，分析并設(shè)計出高效適用的排序算法，是擺在計算機科學(xué)工作者面前的重要課題之一。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,8.1 排序的基本概念,排序是數(shù)據(jù)處理中的重要運算，其功能是將一組數(shù)據(jù)元素（或記錄）的任意序列，經(jīng)重新排列整理成為按關(guān)鍵字值大小有序的序列。 排序的實際應(yīng)用領(lǐng)域也是非常廣泛的。例如在實際問題的數(shù)據(jù)處理中常會遇到這樣的情況，需要把若干名字如人名、地名、國名、書名、校名、物名等按字母順序列表；需要把若干數(shù)值如各種考試分數(shù)、田賽的長度、徑賽的時間等按成績次序排名；需要把若干不同屬性的記錄按照某種方法排列次序。所有這些都是排序問題，都需要把一組數(shù)據(jù)元素或記錄按照某種特定的次序排列起來。,排序的基本概念（續(xù)）,排序的確切定義可以描述為： 設(shè)（R1，R2 Rn）是某文件的n個記錄，其相應(yīng)的關(guān)鍵字為（K1，K2 Kn）。 排序（sort）是這樣一種操作，它確定文件中n個記錄的一種排列（Rj1，Rj2 Rjn），使得其相應(yīng)關(guān)鍵字滿足遞增（即不減）關(guān)系Kj1Kj2Kjn或遞減（即不增）關(guān)系Kj1Kj2Kjn。 若關(guān)鍵字滿足遞增（即不減）關(guān)系時，稱作按關(guān)鍵字升序排序(ascending sort)； 若關(guān)鍵字滿足遞減（即不增）關(guān)系時，稱作按關(guān)鍵字降序排序(descending sort)。,排序的基本概念（續(xù)）,在前面定義中，關(guān)鍵字Ki(i=1，2 n)稱作排序碼（sort code）。 排序碼可以是記錄的主關(guān)鍵字，也可以是次關(guān)鍵字，或者是多個關(guān)鍵字的組合（即組合關(guān)鍵字）。 當(dāng)排序碼是主關(guān)鍵字時，由于主關(guān)鍵字可以惟一標識一個記錄，所以排序結(jié)果是惟一的。 當(dāng)排序碼是次關(guān)鍵字時，同一關(guān)鍵字值可能標識了兩個或兩個以上的記錄，所以排序結(jié)果不惟一。,排序的基本概念（續(xù)）,若相同關(guān)鍵字值的記錄在排序前后的相對位置不會發(fā)生改變，即若Ri與Rj的關(guān)鍵字相同（Ki=Kj）且在排序前Ri在Rj之前，排序后的Ri仍在Rj之前，則稱所用的排序算法是穩(wěn)定的(stable)； 否則，若排序前后相同關(guān)鍵字值的記錄其相對位置可能發(fā)生改變，即排序之后的序列中有可能出現(xiàn)Rj在Ri之前的情況，則稱所用的排序算法是不穩(wěn)定的。 當(dāng)排序碼是組合關(guān)鍵字時，通常稱作多關(guān)鍵字排序，其排序結(jié)果的惟一性取決于組合關(guān)鍵字是否能惟一標識一個記錄。,排序的分類,根據(jù)排序過程中待排序文件存放的位置不同，可以把排序分為內(nèi)部和外部排序兩大類。 內(nèi)部排序是指待排序文件放在內(nèi)存中進行排序的排序；內(nèi)部排序適用于記錄個數(shù)不很多的較小待排序文件的排序； 外部排序是指在待排序文件很大時，內(nèi)存中不能一次容納全部記錄，還要借助于外存存放待排序文件，在排序過程中需要對外存進行訪問的排序；外部排序則適用于記錄個數(shù)太多不能一次全部放入內(nèi)存的較大待排序文件的排序。,排序的分類（續(xù)）,按排序中所用策略的不同： 內(nèi)部排序通常可以分為插入排序、選擇排序、交換排序、歸并排序和分配排序這五類，每一類中不同的排序算法都是基于同一策略的不同方法。 外部排序多是采用多路歸并方法進行排序。,內(nèi)部排序文件的組織形式,每種內(nèi)部排序方法均可在不同的存儲結(jié)構(gòu)上實現(xiàn)。通常待排序文件的組織形式有三種方式： 以一維數(shù)組作為組織形式，排序過程是對記錄本身進行物理重排，通過比較和判定把記錄移動到合適的位置； 以鏈表（動態(tài)鏈表或靜態(tài)鏈表）作為組織形式，排序過程中無需移動記錄，僅需修改指針即可，通常把這類排序稱為表排序； 為待排序文件組織一個輔助表，如組織一張含關(guān)鍵字和指向記錄指針的索引表，在排序過程中只需對輔助表的表目進行物理重排，不需移動記錄本身，在排序結(jié)束后按輔助表調(diào)整記錄位置。,排序的基本概念（續(xù)）,排序的方法很多，每一種方法都有自己的優(yōu)缺點，適用于在不同的環(huán)境下使用，很難說哪一種方法是最好的方法。 由于所需的輔助空間的量一般都不大，所以排序的時間代價是衡量排序算法的最重要的因素。 內(nèi)部排序的時間代價主要用關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)來衡量； 而外部排序的時間代價主要用訪問外存儲器的次數(shù)來衡量。,排序的基本概念（續(xù)）,在本章主要討論內(nèi)部排序算法，以記錄數(shù)組作為待排序文件的組織形式，并假定關(guān)鍵字均為整數(shù)，按遞增次序討論排序算法（即討論升序排序問題）。 待排序文件中記錄結(jié)構(gòu)類型定義如下： typedef struct int key; /*關(guān)鍵字*/ elemtype otheritems; /*其它域*/ recordtype /*記錄類型標識符*/,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,插入排序,插入排序的基本方法是：每次將一個待排序的記錄Ri，按其關(guān)鍵字Ki的大小插入到前面已經(jīng)排好序的部分文件中的適當(dāng)位置，直到全部記錄插完整個文件已排好序為止。 本節(jié)介紹的插入排序方法有直接插入排序和希爾排序；并簡介二分法插入排序、二路插入排序和共享棧插入排序。,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希爾排序 8.2.3 其它插入排序簡介,直接插入排序,直接插入排序（straight insertion sort）是一種最簡單的排序方法。 它的基本思路是： 依次把待排序的記錄逐個插入已排好序的序列中。 一開始，第一個記錄是一個長度為1的有序序列； 從第二個記錄起，每次用第i(i=2，3 n)個記錄的關(guān)鍵字Ki與前面有序序列中記錄的關(guān)鍵字Ki-1、Ki-2 K1進行比較，從而找到Ki所在記錄應(yīng)該插入的位置并依次后移各記錄后插入之，使得有序序列的長度加1； 這樣插入n-1次就會得到n個記錄的有序序列，從而完成整個文件的排序工作。,直接插入排序舉例,例如，已知待排序文件中記錄的關(guān)鍵字序列為（23，48，32，107，86，75，68），直接插入排序的過程可示意如下：,其中，方括號表示已排好序的序列，i表示插入第i個記錄。,直接插入排序（續(xù)）,在插入第i個記錄時，用Ki和前面已排好序記錄的關(guān)鍵字比較，若Ki小則后移一個記錄，直到Ki不小于時插入位置找到了，直接插入Ki完成第i個記錄的插入。 由于后移操作會覆蓋第i個記錄，在算法描述中可在進行第i個記錄插入之前，先保存其于R0中再進行比較后移操作；這個附加的R0還可起到“監(jiān)視哨”的作用，即當(dāng)Ki小于前面有序序列中的每一個關(guān)鍵字時，在和R0中關(guān)鍵字（它本身）比較時不會小于，既找到了正確的插入位置，又避免了循環(huán)控制變量的越界檢查。 設(shè)置監(jiān)視哨是一種程序設(shè)計技巧，既使程序控制簡單，又節(jié)省了測試時間提高了檢索效率。,直接插入排序的算法描述,直接插入排序的算法描述如下： 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)完成一趟的關(guān)鍵字比較、記錄后移和確定位置后的插入操作。 算法中的主要時間開銷在于關(guān)鍵字的比較和記錄的后移操作上。 在最好的情況下是待排序文件中各記錄已經(jīng)按關(guān)鍵字遞增有序，每一趟只需一次比較操作和兩次移動操作（即Ri=R0和R0=Ri）,無需記錄后移；其比較次數(shù)為n-1次，移動操作次數(shù)為2（n-1）次，算法的時間復(fù)雜度為O(n)。,直接插入排序的算法分析(續(xù)),在最壞的情況下是待排序文件中各記錄為關(guān)鍵字的逆序排列（即遞減序列），每一趟中需要和前面已排好序的i-1個記錄以及監(jiān)視哨中R0進行關(guān)鍵字值的比較，即第i趟中需進行i次比較操作； 向后移動次數(shù)為i-1次，加上與監(jiān)視哨之間的兩次移 動，第i趟需要移動記錄i+1次；總的比較次數(shù)為 次，總的移動次數(shù)為 次，算法的時間復(fù)雜度為O(n2)。,直接插入排序的算法分析(續(xù)),若初始文件中各記錄是隨機排列，即關(guān)鍵字的各種排列的出現(xiàn)概率相同時，我們可取上述最好與最壞情況的平均值作為比較和移動的平均次數(shù)，約為n2/4,由此可得直接插入排序的時間復(fù)雜度為O(n2)。 由于直接插入排序在整個排序過程中只需一個記錄的輔助空間（即R0），所以其空間復(fù)雜度為O(1)。由于對于相同關(guān)鍵字值的記錄在排序前后相對位置不會發(fā)生變化（如上例中的48和 ），所以直接插入排序是一種穩(wěn)定的排序方法。,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希爾排序 8.2.3 其它插入排序簡介,希爾排序,希爾排序（shells method），又稱作縮小增量排序（diminishing increatment）。它是1959年由D.L.Shell提出來的對直接插入排序的一種改進方法。 希爾排序是不穩(wěn)定的排序算法。 由直接插入排序的分析可知，在待排序文件已按關(guān)鍵字值遞增有序時的時間復(fù)雜度為O(n)，在逆序時的時間復(fù)雜度為O(n2)。 換句話說，如果待排序文件能夠基本有序，則文件中的大多數(shù)記錄都不需要進行插入（即后移）操作，整個排序的時間開銷就可以大大減少。 另外，當(dāng)n的值很小時，n2的值受n的值的影響也不太大，直接插入排序的效率也比較高。希爾排序正是基于這兩點考慮而得到的對直接插入排序的一種改進方法。,希爾排序的方法,希爾排序的方法是： 先選取一個小于n的整數(shù)d1作為第一個增量，把待排序文件中的全部記錄分成d1個組，將所有距離為d1倍數(shù)的記錄放在同一個組中，在各組內(nèi)進行直接插入排序； 然后選取第二個增量d2<d1，重復(fù)上述的分組和排序工作；如此不斷地選取更小的增量d3，d4 并重復(fù)上述的分組和排序工作， 直到所選取增量di=1(di<di-1<<d2<d1)時所有記錄放在同一組中進行直接插入排序后為止。,希爾排序的方法（續(xù)）,希爾排序方法的一開始組數(shù)較多而組中記錄較少，各組中記錄的直接插入排序是處在n值很小的情況下進行，有著較高的效率；并且在不滿足次序時的移動，是用較少的移動次數(shù)而得到了記錄的較大移動距離。 隨著di減小，組數(shù)變少組中記錄個數(shù)變多的同時，組中記錄也逐步變得基本有序，使得在一趟中進行直接插入排序時的效率大大地提高。 所以希爾排序始終是在較高的效率下工作。希爾排序中增量di的選擇可以有不同的取法，一般是采用希爾在最早時提出的方法，即d1=,di+1=(i=2，3，4 )。 但也有人提出不同的di選取方法，如克努特（Knuth）提出的方法是d1=,di+1=(i=2，3，4 )。如何選取增量序列才能產(chǎn)生最好的排序效果，至今仍無法從數(shù)學(xué)角度得出圓滿的結(jié)論；然而逐步縮小增量和最后一次增量為1是大家不爭的事實。,希爾排序舉例,設(shè)待排序文件中有10個記錄，初始關(guān)鍵字序列為(52,38,66,87,77,16,30,62,07)，增量序列依次為5,3,1，排序過程如下：,希爾排序舉例（續(xù)）,希爾排序舉例（續(xù)）,第一趟排序時d1=5，把待排序文件分成五組，即（R1，R6）、（R2，R7）、（R3，R8）、（R4，R9）和（R5，R10），各組中第一個記錄都自成長度為1的有序區(qū)，依次把各組的第二個記錄插入有序區(qū)中得到第一趟排序結(jié)果； 第二趟排序時d2=3，把待排序文件分成三組，即（R1，R4，R7，R10）、（R2，R5，R8）和（R3，R6，R9），對各組進行直接插入排序后得到第二趟排序結(jié)果； 第三趟排序時d3=1，整個待排序文件為一組，對整個文件做直接插入排序得到的第三趟排序結(jié)果，使整個待排序文件按關(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，而是獨立設(shè)計直接插入排序的部分；這是因為希爾排序中距離為d的倍數(shù)的記錄為一組，組中成員記錄之間有間隔不連續(xù)不能直接調(diào)用的緣故。 另外，在for循環(huán)中的分組執(zhí)行直接插入排序的過程，是依次先插入d個組中的第二個記錄，再插入d個組中的第三個記錄最后插入d個組中的最后一個記錄；是d個組的交替插入過程，而不是一個組的直接插入排序完成后再進行下一組，這樣有利于算法設(shè)計的簡潔性和算法描述的方便性。,希爾排序（續(xù)）,如果考慮設(shè)置監(jiān)視哨，很自然地會考慮到仿照直接插入排序算法中的監(jiān)視哨設(shè)置辦法。對于增量為d的一趟希爾排序，待排序文件被分成d 組，各組中記錄之間的距離為d；需要在R1到Rd處設(shè)置監(jiān)視哨，而在Rd+1到Rd+n處安排待排序文件中的n個記錄。由于在各趟排序中的增量d1,d2 di是逐次縮小的，而待排序文件中各記錄的位置空間安排好之后不宜變動（移動需時間開銷），所以d可選為di中的最大值d1，即一次性安排監(jiān)視哨空間并固定不變； 另外，監(jiān)視哨中的值應(yīng)在不同組中的不同記錄插入時安排不同的值（即待插入記錄的值），但是多次更換監(jiān)視哨中的值既繁瑣又影響效率，我們可以考慮在排序之前一次性設(shè)置各監(jiān)視哨的值，可設(shè)置為不超過待排序文件中最小關(guān)鍵字值的某一個值如-maxint。這種監(jiān)視哨的設(shè)置方法，沒有在監(jiān)視哨中保存各組中的一個個待插入記錄，但可以統(tǒng)一保存待插入記錄于R0中。,希爾排序的算法描述(設(shè)置監(jiān)視哨),設(shè)置監(jiān)視哨的希爾排序算法可描述如下： void shellsort(recordtype R,int n) int i,j,d; for(i=1;i 1); /*shellsort end*/,希爾排序的算法分析,在前面給出的兩個算法，除了是否設(shè)置監(jiān)視哨外，排序的方法是相同的，其時間復(fù)雜度也是相同的；其增量序列為d1= ，di= (i2)。算法中的主要時間開銷在于三重循環(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)確定各組中每個記錄的插入位置，進行關(guān)鍵字的比較和記錄的移動操作；,希爾排序的算法分析（續(xù)）,在最好的情況下只執(zhí)行一次比較而無記錄移動，其一趟中總的比較次數(shù)與中層for循環(huán)的執(zhí)行次數(shù)相同，為 ； 而一趟中執(zhí)行插入的次數(shù)為n-di，即平均比較次數(shù)不超過 ,更不會超過log2n次； 由于希爾排序算法中開始時兩個記錄一組，以后隨著組數(shù)的減少組中記錄增多也逐步基本有序，所以在n較大時的其它情況下的平均比較次數(shù)也是接近于最好情況下的次數(shù)log2n或是它的線性函數(shù)，而移動次數(shù)或平均移動次數(shù)是遠遠小于比較次數(shù)和平均比較次數(shù)的； 由此得內(nèi)層while循環(huán)的平均執(zhí)行次數(shù)為O(log2n)階函數(shù)。由算法分析的乘法法則可知，前面給出的兩個希爾排序算法，shellsorting和shellsort的時間復(fù)雜度為O(n(log2n)2)。,8.2 插入排序,8.2.1 直接插入排序 8.2.2 希爾排序 8.2.3 其它插入排序簡介,1.二分法插入排序,由第七章的討論我們知道，對有序表采用二分法檢索，檢索性能大大優(yōu)于順序檢索。 如果我們把直接插入排序中的由后向前順序檢索尋找插入位置的方法改為用二分法檢索來實現(xiàn)，當(dāng)n較大時就可以大幅度地降低關(guān)鍵字的比較次數(shù)。我們把經(jīng)過這種改進后的插入排序方法，稱作二分法插入排序（binary insertion sort）。 二分法插入排序與直接插入排序相比較，僅是減少了尋找插入位置時的關(guān)鍵字比較次數(shù)，記錄的移動次數(shù)沒有改變，其時間復(fù)雜度仍為O(n2)； 所需的輔助存儲空間也與直接插入排序相同，也是穩(wěn)定的排序方法（在檢索位置出現(xiàn)關(guān)鍵字值相等時需后移插入位置指示器變量，否則為不穩(wěn)定方法）。,2.二路插入排序,二路插入排序（2-way insertion sort）是在二分法插入排序基礎(chǔ)上的進一步改進，改進的目標是減少排序過程中記錄的移動次數(shù)，但為此多開銷了n個記錄大小的輔助存儲空間。 其具體方法是： 另設(shè)一個和R同類型的數(shù)組S，先將R1賦給S1，并將S1看成是在已排好序序列中處于中間位置的記錄； 然后從R中第二個記錄起，依次插入到S1之前或S1之后的有序序列中去， 若待插記錄的關(guān)鍵字小于S1.key則插入S1之前的有序表中，否則插入S1之后的有序表中。 在算法實現(xiàn)時，把S數(shù)組看成是一個循環(huán)數(shù)組，并設(shè)兩個指針first和final分別指示排序過程中得到的有序序列中的第一個記錄和最后一個記錄在S中的位置。,二路插入排序舉例,二路插入排序舉例（續(xù)）,二路插入排序（續(xù)）,在二路插入排序中，記錄的移動次數(shù)約為n2/8，比直接插入排序減少移動次數(shù)約一半。它只能減少移動次數(shù)而不能絕對避免移動記錄，若要大幅度降低移動次數(shù)，可改變存儲結(jié)構(gòu)為靜態(tài)鏈表，進行表插入排序。 此外，二路插入排序中，當(dāng)R1為待排序文件中最小或最大關(guān)鍵字的記錄時，完全失去優(yōu)越性退化為直接插入排序的時間效率。 二路插入排序，是一種穩(wěn)定的排序方法。,3.共享棧插入排序,共享棧插入排序（shared stack insertion sort）也是對直接插入排序的一種改進方法。 其基本思想是： 把待排序的記錄數(shù)組R看作是一個靜態(tài)的共享棧（棧1和棧2），棧1按數(shù)組下標由小到大方向增長，棧2按數(shù)組下標由大到小方向增長；棧1中按關(guān)鍵字升序排列壓入待排序記錄，棧2中按關(guān)鍵字降序排列壓入待排序記錄。 一開始先比較R1和Rn的關(guān)鍵字值大小，若R1Rn則交換；top1=1,top2=n； 然后把R2到Rn-1逐一插入兩個棧中，插入的過程中始終保證棧1的棧頂記錄的關(guān)鍵字值都不大于棧2 的棧頂記錄的關(guān)鍵字值。,共享棧插入排序（續(xù)）,為此需要區(qū)分以下三種情況并作相應(yīng)處理： 當(dāng)待插入記錄Ri的關(guān)鍵字值不小于棧1 的棧頂記錄的關(guān)鍵字值且不大于棧2的棧頂記錄的關(guān)鍵字值時，將待插記錄壓入棧1中。即Ri.keyRtop1.key且Ri.keyRtop2.key時進棧1，只須改變top1的值為top1+1即可。 當(dāng)Ri.keytop2.key時，由棧2反復(fù)傳送記錄到棧1，直到Ri.keytop2.key時將Ri插入棧2。由棧2傳送到棧1一個記錄，需要把Ri+1到Rtop2-1的記錄后移一個位置。,共享棧插入排序舉例,共享棧插入排序舉例（續(xù)）,共享棧插入排序（續(xù)）,共享棧插入排序不需要增加額外的存儲開銷，在時間性能上與二路插入排序相當(dāng)，而且有效地避免了因R1為待排序記錄中關(guān)鍵字值為最大或最小記錄時完全失去優(yōu)越性的不足。 若增加存儲開銷另設(shè)與R相同類型的數(shù)組作為共享棧，則可以進一步減少移動次數(shù)，且排序結(jié)果不象二路插入排序那樣要使用循環(huán)數(shù)組解釋。 共享棧插入排序是一種穩(wěn)定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,交換排序,交換排序的基本方法是，兩兩比較待排序記錄的關(guān)鍵字值，并交換那些不滿足順序要求的記錄對，直到全部待排序記錄都已滿足順序要求時為止。 本節(jié)介紹兩種交換排序的方法： 一種是冒泡排序， 一種是快速排序。,8.3 交換排序,8.3.1 冒泡排序 8.3.2 快速排序,冒泡排序,冒泡排序（bubble sort）也稱作起泡排序，是一種簡單的排序方法。 它是通過相鄰記錄之間的關(guān)鍵字比較和記錄交換，使關(guān)鍵字值較小的記錄由底部向上移動，而關(guān)鍵字值較大的記錄由頂部向下移動，就象水中的氣泡向上飄浮（冒泡）一樣。,冒泡排序算法,冒泡排序的具體做法是： 將關(guān)鍵字縱向排列，然后自下而上地對相鄰兩個記錄的關(guān)鍵字進行比較，若為逆序（即Rj-1.keyRj.key，j=n,n-12）則交換兩個記錄，直到全部記錄都比較和交換完畢（即j=2），第一趟冒泡排序結(jié)束； 此時最小關(guān)鍵字值的記錄上浮到了R1的位置上。然后對n-1個記錄重復(fù)類似的操作，次小關(guān)鍵字值的記錄上浮到R2的位置上。 重復(fù)進行這樣的過程，直到?jīng)]有記錄需要交換為止（最多需n-1趟冒泡排序），整個待排序文件就按關(guān)鍵字值升序排列完畢。,冒泡排序算法舉例,例如，對于8個記錄的關(guān)鍵字序列（46，26，43，18，74，21, ,57），冒泡排序的過程如下圖所示：,冒泡排序算法（續(xù)）,由該冒泡排序的實例，也證實了至多需要n-1趟冒泡排序即可完成整個排序。 事實上存在不需要n-1趟就可以完全排好序的情況，如上例的第五趟排序后就已經(jīng)排好序了； 其識別辦法是，若某一趟冒泡排序過程中沒有進行記錄的位置交換，則說明待排序文件已經(jīng)完全排好序了。 為此，需在算法中引入一個交換狀態(tài)變量flag，在每一趟排序之前置flag為0，每次交換時給flag加1，若一趟結(jié)束時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; /*置已交換標志*/ if(flag=0) break; /*bubblesort end */,冒泡排序算法分析,冒泡排序也是一種穩(wěn)定的排序方法。 其時間復(fù)雜度可以如下分析： 在最好的情況下，是初始記錄的關(guān)鍵字已遞增有序時，只需一趟排序，比較次數(shù)為n-1，沒有交換記錄即記錄的移動次數(shù)為0； 在最壞的情況下，是初始記錄遞減有序（即逆序）時，需進行n-1趟排序，比較次數(shù)為 ，交換次數(shù)為 ，每次交換需三次移動記錄，其移動次數(shù)為 。 在平均情況下，關(guān)鍵字的比較次數(shù)和記錄的移動次數(shù)大約為最壞情況下的一半，因此冒泡排序算法的時間復(fù)雜度為O(n2)。,冒泡排序算法分析（續(xù)）,上述的冒泡排序算法還可以作一些改進來提高排序速度，比如： 在每趟排序中記住最后一次發(fā)生交換記錄的位置K，因為位置K之前的記錄都已排好了序，下一趟的排序可以終止于位置K而不必進行到預(yù)定的下界位置i。 在排序過程中交替變化掃描比較的方向，即前一趟由后向前掃描，后一趟則由前向后掃描，而不是一直都由后向前掃描。由后向前掃描比較交換一趟，可使最輕的氣泡上浮到頂部，但只能使最重的氣泡下沉一個位置；由前向后掃描比較交換一趟，可使最重的氣泡下沉到底部，但只能使最輕的氣泡上浮一個位置。交替變化掃描方向可以加速最輕和最重的氣泡向兩端迅速沉浮，有利于加速排序過程。,8.3 交換排序,8.3.1 冒泡排序 8.3.2 快速排序,快速排序,快速排序（quick sort）也稱作分區(qū)交換排序，是對冒泡排序的一種改進排序方法。它是目前各種內(nèi)部排序方法中較快的方法，故稱之為快速排序。 快速排序的基本思想是： 在待排序文件的n個記錄中，任取一個記錄（通常是選取第一個記錄）作為基準； 經(jīng)過一趟排序后以基準記錄的關(guān)鍵字把全部記錄分為兩部分，所有關(guān)鍵字值比基準記錄關(guān)鍵字值小的記錄都排列在基準記錄之前，而所有關(guān)鍵字值比基準記錄關(guān)鍵字值大的記錄都排列在基準記錄之后； 然后對基準記錄前后的這兩個部分分別重復(fù)這樣的過程，得到本趟排序的兩個新到位的基準和四個部分如此重復(fù)上述過程，直到每一個部分只剩下一個記錄（即全部到位）時為止。,快速排序算法,設(shè)兩個指示器變量i和j，分別指向待排序區(qū)間的第一個記錄和最后一個記錄； 先將第一個記錄移到暫存變量temp中，然后j從區(qū)間的最后一個記錄起向前掃描，直到找到滿足Rj.keytemp.key的記錄時，將Ri移入Rj中； 就這樣j自j-1從后向前掃描一次移入一個Rj于Ri中，i自i+1從前向后掃描一次移入一個Ri于Rj中，反復(fù)交替的掃描和移動記錄； 直到i=j時把temp移入Ri中（區(qū)間中第一個記錄應(yīng)在的位置），它把整個待排序區(qū)間分割為相互獨立的兩個更小的區(qū)間。,快速排序的算法描述,這種把一個待排序區(qū)間通過基準記錄（第一個記錄）分割成為兩個區(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<=temp.key) /*divideareasort end*/,快速排序的算法描述（續(xù)）,對于待排序文件R利用一次分割區(qū)間排序算法時，令s=1和t=n即可完成第一趟排序；由此得到的兩個更小的區(qū)間R1i-1和Ri+1n，繼續(xù)利用算法divideareasort分割為更小的四個區(qū)間；如此一直進行下去，直到都分割為只有一個記錄時排序結(jié)束。調(diào)用divideareasort對R 進行快速排序的遞歸算法可描述如下： void quicksort(recordtype R,int s,int t) int i; if(s<t) i=divideareasort(R,s,t); quicksort(R,s,i-1); quicksort(R,i+1,t); /*quicksort end*/,快速排序的算法舉例,下面我們使用快速排序算法對關(guān)鍵字序列（36，73，65，97，13，27， ，29）排序，在下面的排序過程示例中，先給出第一趟中的區(qū)間分割的整個過程，然后給出各趟的排序結(jié)果；用方括號表示區(qū)間，用方框表示暫存變量temp的關(guān)鍵字值（并未參加交換，在分割完成后才放入最終位置上）。,快速排序的算法舉例（續(xù)）,快速排序的算法舉例（續(xù)）,快速排序的算法舉例（續(xù)）,快速排序的算法分析,快速排序過程中各趟中所選擇的基準可以用一棵二叉樹來表示，如上例中的基準二叉樹如右圖所示?；鶞识鏄浞从沉丝焖倥判虻倪f歸調(diào)用過程，也便于我們對快速排序算法進行性能分析。,快速排序的基準二叉樹是關(guān)鍵字的一棵二叉檢索樹，其中序遍歷序列就是關(guān)鍵字的升序排列。 在最好的情況下，基準二叉樹是一棵理想的平衡二叉檢索樹，深度為 ，遞歸所需棧的存儲開銷為O(log2n)，時間開銷為結(jié)點數(shù)乘平均檢索長度，即O(nlog2n)。,快速排序的算法分析（續(xù)）,在最壞情況下，基準二叉樹是一棵單枝二叉檢索樹，深度為n，存儲開銷為O(n)，時間開銷為O(n2)。 在平均情況下，基準二叉樹是一棵隨機的二叉檢索樹，由于二叉檢索樹的平均檢索長度為O(log2n)，故時間開銷也是O(nlog2n)。 為了避免初始關(guān)鍵字序列有序或基本有序時快速排序蛻化為冒泡排序（即基準二叉樹為單枝或近似單枝二叉樹）的情況，通常采取“三者取中”的基準記錄選取辦法改進之。 所謂三者取中是指在Rs、Rt和R(s+t)/2三者中選取關(guān)鍵字值居中的記錄作為分割區(qū)間的基準，這種選取基準記錄的方法可以大大改善快速排序在最壞情況下的性能。 快速排序算法是一種不穩(wěn)定的排序方法。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,選擇排序,選擇排序的基本方法是，每次從待排序文件的各個記錄中，依次選出關(guān)鍵字值最小的記錄放在已排好序的序列中，直到選完為止。 本節(jié)介紹： 直接選擇排序 樹型選擇排序 堆排序。,8.4 選擇排序,8.4.1 直接選擇排序 8.4.2 樹形選擇排序 8.4.3 堆排序,直接選擇排序,直接選擇排序（direct selection sort）也稱作簡單選擇排序。 其具體做法是： 對于待排序文件R1.n，通過比較首先選出關(guān)鍵字值最小的記錄與R1交換， 然后在其余記錄中選出次小關(guān)鍵字的記錄與R2交換 如此進行n-1次的選擇與交換，R1.n中所有記錄就按關(guān)鍵字升序次序排列完畢。,直接選擇排序舉例,直接選擇排序的過程可示例如下：,直接選擇排序舉例（續(xù)）,直接選擇排序的算法描述,直接選擇排序的算法可描述如下： 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.key<Rm.key) m=j; if(m!=i) temp=Ri; Ri=Rm; Rm=temp; /*selectsort end*/,直接選擇排序的算法分析,直接選擇排序只需要一個記錄大小的輔助存儲空間用于記錄交換，其空間復(fù)雜度為O(1)。 在排序過程中至多進行n-1趟排序，即至多交換記錄n-1次，做3(n-1)次記錄移動；然而不論初始狀態(tài)如何，在每一趟中都需要和所有記錄的關(guān)鍵字進行比較； 為了選出第i趟的最小關(guān)鍵字，需要的比較次數(shù)為n-i，總的比較次數(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）也稱作錦標賽排序（tournament sort），這種排序方法是按照錦標賽的思路進行的。 錦標賽是將n個參賽選手兩兩之間進行比賽（余下的一個輪空直接進入下一輪比賽），勝出者再兩兩之間比賽，經(jīng)過 輪比賽后產(chǎn)生出第一名。 樹形選擇排序是將待排序的n個記錄的關(guān)鍵字作為完全二叉樹的葉子結(jié)點，依次兩兩之間比較，關(guān)鍵字值小者作為其雙親結(jié)點，最后若余下一個則輪空參加下一輪比較；然后對得到的這些雙親結(jié)點再兩兩之間比較產(chǎn)生其雙親結(jié)點（小者）如此經(jīng)過 輪比較后，關(guān)鍵字值最小的記錄就在根結(jié)點位置。,樹形選擇排序舉例,選擇關(guān)鍵字值最小的記錄放在根結(jié)點位置的過程如下圖(a)的二叉樹所示。接下來將最小關(guān)鍵字值改為，然后沿該結(jié)點到樹根的路徑依次進行各分枝結(jié)點子女之間的比較，上升到根結(jié)點的是次小關(guān)鍵字值的記錄，如下圖(b)所示；如此繼續(xù)進行下去，直到所有記錄都已選出時為止。,樹形選擇排序算法分析,在樹形選擇排序中，除第一次選出最小關(guān)鍵字需n-1次比較外，選出次小關(guān)鍵字和其它關(guān)鍵字都需經(jīng)過從葉到根的路徑，即需進行 次比較。 總的比較次數(shù)至多為 ，所以其時間復(fù)雜度為O(nlog2n)。 樹形選擇排序的缺點是需要的輔助空間較多，需要用n-1個記錄大小的空間來保存各層次的比較結(jié)果；此外，與進行多余的比較也是其缺點之一。,8.4 選擇排序,8.4.1 直接選擇排序 8.4.2 樹形選擇排序 8.4.3 堆排序,堆排序,為了克服樹形選擇排序需要較多輔助空間保存比較結(jié)果和與進行多余比較的缺點； 在1964年威洛姆斯（J.Willioms）和弗洛伊德（Floyd）對樹形選擇排序進行了改進，提出了新的排序方法堆排序（heap sort）方法，使其比較次數(shù)達到樹形選擇排序的水平，同時又不會增加額外的存儲開銷，只需一個記錄大小的空間用于記錄間的交換。,堆的定義,堆的定義為，對于一個關(guān)鍵字序列（k1，k2 kn），當(dāng)且僅當(dāng)對于所有的i=1，2，都滿足下面的關(guān)系或都滿足下面的關(guān)系時，稱之為堆； 都滿足關(guān)系時稱之為最小值根堆； 都滿足關(guān)系時稱之為最大值根堆。 如果將與此序列對應(yīng)的一維數(shù)組看成是一棵完全二叉樹，則堆的含義表明完全二叉樹中任一非終端結(jié)點上的數(shù)據(jù)值均不大于（或不小于）其左孩子和右孩子結(jié)點的值。 因此在一個堆中，堆頂元素（完全二叉樹的根）必為堆中的最小（或最大）元素，并且堆中的每一棵子樹也都是堆。,堆排序舉例,例如關(guān)鍵字序列（12，15，35，25，39，67）和序列（75，38，62，28，18，49）都是堆，前者是最小值根堆而后者是最大值根堆，其對應(yīng)的完全二叉樹分別如下圖的(a)和(b)所示。,堆排序的基本思想,堆排序的基本思想是，對待排序文件中的n個記錄，依它們的關(guān)鍵字值大小按堆的定義排成一個序列（稱之為建堆），從而輸出堆頂?shù)淖钚￡P(guān)鍵字（用最小值根堆排序）的記錄，然后對剩余的關(guān)鍵字再次建堆，便得到次小關(guān)鍵字的記錄，如此反復(fù)進行輸出和建堆，直到全部記錄按關(guān)鍵字排成有序序列時為止。 由以上分析可知，要實現(xiàn)堆排序需要解決如下兩個問題： 如何由關(guān)鍵字值的無序序列建成一個堆？即建初始堆問題； 如何在輸出堆頂記錄之后調(diào)整剩余記錄為一個新堆？即堆調(diào)整問題。,創(chuàng)建初始堆,先討論建初始堆問題。在1964年弗洛伊德（Floyd）提出了篩選法，其具體方法是 將待排序記錄的關(guān)鍵字分放到一棵完全二叉樹的各個結(jié)點中，此時的完全二叉樹一般不具備堆的特性。 然而所有i 的結(jié)點Ki都沒有孩子結(jié)點，以這樣的Ki為根的子樹已經(jīng)是堆了； 因此建初始堆可以從完全二叉樹的最后一個分枝結(jié)點Ki(i= )開始，通過調(diào)整逐步使以Ki、Ki-1、K1為根的子樹滿足堆的定義，直到以K1為根的樹滿足堆定義時初始堆建成。,創(chuàng)建初始堆（續(xù)）,在對Ki（i= ， -1 1）為根的子樹建堆的過程中，可能需要對記錄的位置進行調(diào)整； 若在調(diào)整過程中使下一層已建成堆的子樹不滿足堆的定義，則要繼續(xù)向下層進行調(diào)整，直到某一個下層滿足堆的定義時為止，最壞的情況下是這種調(diào)整可能一直延伸到樹的葉子結(jié)點。 這種方法就像過篩子一樣，把最小關(guān)鍵字值的記錄一層一層地篩選出來，最后輸出堆頂?shù)淖钚￡P(guān)鍵字記錄。,建初始堆（最小根堆）過程舉例,下圖給出了完全二叉樹表示的一組關(guān)鍵字值建初始堆的示例，所用關(guān)鍵字序列為（47，33，61，82，72，11，25， ）；由于n=8，故從第4個結(jié)點開始進行調(diào)整。,建初始堆(最小根堆)過程舉例(續(xù)),堆排序過程舉例,現(xiàn)在討論堆調(diào)整的問題。在輸出堆頂記錄之后，用堆中的最后一個記錄替代原堆頂記錄。 由于除根結(jié)點K1之外的所有子樹仍然具有堆的性質(zhì)，故只需要對根結(jié)點自上而下調(diào)整即可。 例如對上例所給的關(guān)鍵字序列，經(jīng)初始建堆后得到圖(a)所示的堆，同時得到堆頂?shù)淖钚￡P(guān)鍵字11所在的記錄； 然后輸出堆頂記錄（key=11）并用最后一個記錄（key=82）替代堆頂，如圖(b)所示。此時由于以K2和K3為根的子樹仍具有堆的特性，只需對根自上而下按堆的定義調(diào)整。 首先將堆頂元素K1與左右孩子K2和K3比較，若K1< K2且K1< K3不需調(diào)整已滿足堆定義；否則選擇K2和K3中關(guān)鍵字值小的記錄與堆頂記錄交換。,堆排序過程舉例（續(xù)）,由于K3<K2且K3<K1，則82與25所在的兩個記錄交換位置； 又由于交換破壞了右子樹的堆，則需再次進行類似的調(diào)整，直至進行到葉子結(jié)點； 調(diào)整后的狀態(tài)如圖 (c)所示，即得到一個有n-1個記錄的新堆，同時得到次小關(guān)鍵字25所在的記錄。 反復(fù)重復(fù)以上過程，即可實現(xiàn)上例所給關(guān)鍵字序列所對應(yīng)的待排序文件的堆排序，其堆排序過程如下圖所示。,堆排序過程舉例（續(xù)）,堆排序過程舉例（續(xù)）,堆排序過程舉例（續(xù)）,由前面的討論我們知道，堆調(diào)整是從根結(jié)點向下的一個篩選過程； 而建初始堆是從最后一個分枝結(jié)點開始到根結(jié)點結(jié)束的多次向下的篩選過程。 所以設(shè)計一個篩選算法，完成對Rs.t（只有Rs不滿足堆特性，其它結(jié)點均滿足堆特性）進行篩選是至關(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è)計完整的堆排序算法如下： void heapsort(recordtype R,int n) int i; recordtype 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ù)不會超過4n次，因此堆排序在最壞情況下的時間復(fù)雜度為O(nlog2n)。 此外，堆排序所需的輔助存儲空間少。 堆排序是一種不穩(wěn)定的排序方法。 堆排序適宜用于待排序文件中記錄較多的情況，因為其主要時間開銷在于建堆和調(diào)整堆，記錄較少時不合算。,第8章 排序及基本算法,8.1 排序的基本概念 8.2 插入排序 8.3 交換排序 8.4 選擇排序 8.5 歸并排序 8.6 基數(shù)排序 8.7 各種內(nèi)部排序方法的比較和選擇 8.8 外部排序簡介,歸并排序,歸并排序（merge sort）的基本思想是： 將一些已排序的子文件進行合并而得到一個完整的有序文件。 歸并時只要比較各子文件的第一個記錄的關(guān)鍵字，其最小者就是全局最小者；取出它后繼續(xù)比較各子文件的第一個記錄的關(guān)鍵碼，就可以得到全局的次小者如此下去就可完成排序任務(wù)。 假設(shè)待排序文件中含有n個記錄，我們可以把它看作是n個有序的子序列，每個有序子序列的長度為1；然后兩兩歸并得到個長度為2（其中最后一個長度可能為1）的有序子序列；再兩兩歸并得到長度為4的若干有序子序列如此這樣反復(fù)歸并，直到得到一個長度為n的有序序列時為止。這種排序方法稱為二路歸并排序（two-way merge sort）。,歸并排序舉例,例如，對于待排序文件的關(guān)鍵字序列（22，36，06，78，25，43，73，18，39，62，27，66，13），利用二路歸并排序的過程如下：,歸并排序舉例,由上述歸并排序過程可以看出，二路歸并的主要操作是把相鄰兩個有序序列歸并成為一個有序序列；對于n個記錄的待排序文件，需要歸并趟才能完成排序；每趟歸并使有序子序列的長度增加一倍，而使有序子序列的個數(shù)減少約一半。 下面，我們給出對相鄰兩個有序序列的歸并算法，并給出歸并排序的遞歸算法和非遞歸算法。,8.5 歸并排序,8.5.1 歸并相鄰兩個有序序列 8.5.2 二路歸并排序的遞歸算法 8.5.3 二路歸并排序的非遞歸算法,歸并相鄰兩個有序序列,在前面分析的基礎(chǔ)上，歸并相鄰兩個有序序列為一個有序序列的算法merge可描述如下： void merge(recordtype R,int L,int m,int h,recordtype R1) int i,j,k; i=L; /*i指向第一個有序子序列的第一個記錄*/ j=m+1; /*j指向第二個有序子序列的第一個記錄*/ k=L; /*k指向結(jié)果有序序列的第一個位置*/ while(i<=m),歸并相鄰兩個有序序列（續(xù)）,while(im，要么jh，使得最后的兩個while循環(huán)總有一個相當(dāng)于空語句，而另一個while循環(huán)把剩余記錄傳送到R1中。,8.5 歸并排序,8.5.1 歸并相鄰兩個有序序列 8.5.2 二路歸并排序的遞歸算法 8.5.3 二路歸并排序的非遞歸算法,二路歸并排序的遞歸算法,在前述算法merge的基礎(chǔ)上，可給出二路歸并排序的遞歸算法如下： void mergesortrecalg(recordtype R,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個記錄排序，只須用參數(shù)R、1、n調(diào)用該遞歸算法，即mergesortrecalg(R,1,n,R1)即可。,8.5 歸并排序,8.5.1 歸并相鄰兩個有序序列 8.5.2 二路歸并排序的遞歸算法 8.5.3 二路歸并排序的非遞歸算法,二路歸并排序的非遞歸算法,在給出二路歸并排序的非遞歸算法之前，我們先討論一趟歸并排序的實現(xiàn)算法。 設(shè)R1.n中的有序子序列長度為len，只有最后一個有序子序列的長度有可能小于len，進行兩兩有序的子序列歸并后的結(jié)果依次存放在R11.n中。 進行一趟歸并排序時調(diào)用算法merge，依次對相鄰的兩個長度為len的有序子序列歸并；當(dāng)有序子序列為奇數(shù)個或雖為偶數(shù)個但最后一個有序子序列長度小于len時的兩種情況做特殊處理。,二路歸并排序的非遞歸算法(續(xù)),一趟歸并排序算法可描述如下： void mergepass(recordtype R,int len,int n,recordtype R1) int i=1; while(i+2*len-1<=n) merge(R1,i,i+len-1,i+2*len-1,R1); i=i+2*len; if(i+len-1<n) 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(len<n) mergepass(R,len,n,R1); len=2*len; mergepass(R1,len,n,R); len=2*len; /*mergesort end*/,二路歸并排序的算法分析,如果把待排序文件R中的n個記錄看作葉子結(jié)點，把兩兩歸并得到的有序子序列看成是兩個歸并對象有序子序列的雙親結(jié)點，則歸并過程對應(yīng)由葉向根生成一棵二叉樹的過程，所以歸并排序的趟數(shù)為 ； 而每趟歸并需移動記錄n次（關(guān)鍵字比較約n次），由乘法準則知二路歸并排序的時間復(fù)雜度為O(nlog2n)。 由于二路歸并排序過程中需要一個與待排序文件大小相同的輔助數(shù)組，所以其空間復(fù)雜度為O(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ù)排序（radix sort）方法則不同，它不用進行關(guān)鍵字值的大小比較，而是借助于多關(guān)鍵字排序的思想，通過對待排序記錄按單邏輯關(guān)鍵字進行分配和收集來實現(xiàn)的一種排序方法。,8.6 基數(shù)排序,8.6.1 多關(guān)鍵字排序 8.6.2 鏈式基數(shù)排序,多關(guān)鍵字排序,我們先通過一個大家都熟悉的整理撲克牌的例子來說明多關(guān)鍵字排序的思想和方法。 撲克牌有兩個關(guān)鍵字，即花色和點力；其次序定義為 花色：梅花<方塊<紅桃<黑桃 點力：2<3<4<5<6<7<8<9<10<J<Q<K<A 并且花色的優(yōu)先級別高于點力，即高一級花色的最小點力2大于低一級花色的最大點力A。 因此，要比較任意兩張撲克牌的大小，方法是先比較花色，若花色相同時再比較點力。,多關(guān)鍵字排序（續(xù)）,如果要根據(jù)上述關(guān)系把一幅撲克牌整理為升序次序，即梅花2、梅花3 梅花A、方塊2 方塊A、紅桃2 紅桃A、黑桃2 黑桃A的次序，通常有如下兩種整理方法： 先按花色分成四堆，然后再按點力把每堆整理有序，最后按花色由低級花色到高級花色疊加在一起。 先按點力分成十三堆，然后按點力由小到大的順序收集在一起；再按花色不同分成四堆，最后按花色順序收集起來。,多關(guān)鍵字排序（續(xù)）,前面兩種理牌的方法便是兩種多關(guān)鍵字排序的方法。上述的例子可以推廣到一般情況下： 設(shè)待排序文件R的n個記錄（R1,R2 Rn）中，每個記錄Ri都含有d個關(guān)鍵字位（ ），稱其中兩個記錄有序（即Ri<Rj）是指滿足條件 < ； 若對于任意記錄都滿足Ri<Rj（1ijn），則稱待排序文件R有序；利用d個關(guān)鍵字位整理待排序文件R有序的過程，稱作多關(guān)鍵字排序。,多關(guān)鍵字排序（續(xù)）,多關(guān)鍵字排序的方法通常有兩種： 最高位優(yōu)先法（most significant digit first），簡稱MSD法。 它是先按最高關(guān)鍵字位 對待排序文件中的n個記錄排序，把待排序文件中n個記錄分為若干堆，每個堆中都具有相同的 值； 然后在各個堆中再按關(guān)鍵字位 進行排序，每個堆中的記錄又按 的值分成若干更小的堆 如此不斷地按d個關(guān)鍵字位把較大地堆分為較小的堆，直到用 對各個堆排序后，各個堆中的記錄依次排在一起便形成一個有序文件。,多關(guān)鍵字排序（續(xù)）, 是低位優(yōu)先法（least significant digit first），簡稱LSD法。 它是先按最低關(guān)鍵字位 對待排序文件中的n個記錄進行排序，按 的值把待排序文件中的n個記錄分配到具有不同 值的若干個堆， 然后按 值從小到大的次序收集在一起；下一次再按高一位關(guān)鍵字位 的值進行分配和收集，如此不斷地按更高一位關(guān)鍵字位進行分配和收集； 直到用 分配和收集之后，整個文件按多關(guān)鍵字位 有序。,多關(guān)鍵字排序（續(xù)）,顯然前述的撲克牌排序中， 第一種理排過程采用的是最高位優(yōu)先法（MSD法）， 而第二種理牌過程是采用最低位優(yōu)先法（LSD法）。 通過對上述兩種方法的比較可以看出其不同的特點： MSD法排序，是將待排序文件中所有記錄分成若干獨立的子堆，每個堆中記錄的排序是獨立進行的； 而LSD 法排序時將待排序文件中所有記錄分成的若干子堆不獨立，堆中記錄的排序不能獨立進行，需要進行d趟的分配和收集來完成整個文件中記錄的排序。,8.6 基數(shù)排序,8.6.1 多關(guān)鍵字排序 8.6.2 鏈式基數(shù)排序,鏈式基數(shù)排序,基數(shù)排序就是按照LSD法，對待排序文件中各記錄用單邏輯關(guān)鍵字進行分配和收集的一種排序方法。 假設(shè)含有n個記錄的待排序文件中，每個記錄的關(guān)鍵字由d 個關(guān)鍵字位 組成，并且每個關(guān)鍵字位的取值范圍都相同，即c1 crd（1jd）； 關(guān)鍵字位可能的取值個數(shù)rd稱為基數(shù)?；鶖?shù)的選擇和關(guān)鍵字位的分解因關(guān)鍵字的類型而異。 若關(guān)鍵字是十進制整數(shù)時，則基數(shù)rd為10，c1=0，c1