排序算法及算法分析(續(xù))

排序算法及算法分析（續(xù)）2008/05/131期末考試：6月12號（周四）上午8:00。地點待定。2建立初始的最大堆初始序列為21，25，49，25*，16，083建立初始的最大堆4算法復雜度建堆的算法復雜度：二叉樹深度h=log2n第m層結(jié)點個數(shù)：2m到葉子共h-m層每層最多與兩個結(jié)點比較m層結(jié)點建堆最多比較次數(shù)為2(h-m)*2m因此:C1=hM=1M=0j=h-m5

66堆排序78內(nèi)容提要歸并排序快速排序分配排序8歸并排序（mergesort）歸并排序的基本操作是將兩個或兩個以上的記錄有序序列歸并為一個有序序列。最簡單的情況是:只含一個記錄的序列顯然是個有序序列，經(jīng)過"逐趟歸并"使整個序列中的有序子序列的長度逐趟增大，直至整個記錄序列為有序序列止。

9歸并排序（mergesort）88149825625279302331DivideandConquer10MergeSort88149825625279302331SplitSetintoTwo

(norealwork)25,31,52,88,98Getonefriendto

sortthefirsthalf.14,23,30,62,79Getonefriendto

sortthesecondhalf.11MergeSortMergetwosortedlistsintoone25,31,52,88,9814,23,30,62,7914,23,25,30,31,52,62,79,88,981213二路歸并算法的基本思路：兩組歸并算法merge：按low,m,high歸并兩組記錄。結(jié)果放于low,high之間。

voidmerge(RecordNode*r,RecordNode*r1,intlow,intm,inthigh)一趟歸并算法mergePass：兩兩歸并長度為length的一組記錄：voidmergePass(RecordNode*r,RecordNode*r1,intn,intlength)

14具有n個記錄的文件排序，必須做log2n

趟歸并，每趟歸并所花費的時間是O(n)二路歸并排序算法的時間復雜度為T(n)=O(nlog2n)算法中增加了一個數(shù)組record，算法的輔助空間為S(n)=O(n)二路歸并排序是穩(wěn)定的算法評價15快速排序(QuickSort)88149825625279302331Partitionsetintotwousing

randomlychosenpivot142530233188986279≤

52≤16QuickSort142530233188986279≤

52≤14,23,25,30,31Getonefriendto

sortthefirsthalf.62,79,98,88Getonefriendto

sortthesecondhalf.17QuickSort14,23,25,30,3162,79,98,8852Gluepiecestogether.(Norealwork)14,23,25,30,31,52,62,79,88,9818QuickSort88149825625279302331Letpivotbethefirst

elementinthelist?1425302388986279≤

31≤5219QuickSort≤

14≤14,23,25,30,31,52,62,79,88,9823,25,30,31,52,62,79,88,98Ifthelistisalreadysorted,

thentheslitisworstcaseunbalanced.20設(shè)置變量i指向參加排序的序列中第一個位置0，變量j指向參加排序的序列中最后位置n-1首先保存記錄R0，R[0]為空出的位置，空位在前一區(qū)令j向前掃描，尋找小于R0的記錄，找到小于R0的記錄R[j]，將記錄R[j]移到當前空位中，這時空位在后一區(qū)這時令i自i+1起向后掃描，尋找大于R0的記錄，找到大于R0的記錄R[i]，將記錄R[i]移到當前空位中，空位又到了前一區(qū)，然后再令j自j-1起向前掃描，此交替改變掃描方向，從兩端向中間靠攏，直到i=j，這時i所指的位置為R0的最終位置快速排序基本步驟21初始序列為49,38,65,97,76,13,27,49’，例:(1)一次分區(qū)過程如下∶j向左掃描[493865977613 27 49’]i↑ j↑第一次交換后[273865977613

49’] i↑ j↑i向右掃描 [2738 65 97 76 13

49’] i↑ j↑22第二次交換后[2738

977613 65 49’] i↑ j↑j向左掃描，位置不變，第三次交換后 [2738139776

6549’] i↑ j↑i向右掃描，位置不變，第四次交換后 [273813

76976549’] i↑j↑j向左掃描[2738134976976549’]

i↑j↑例（續(xù)）:2313273849[49’65]76[97] 13 273849 49’[65]76[97] 13 273849 49’6576[97]

最后的排序結(jié)果

13 273849 49’657697例（續(xù)）:24快速排序算法

初始化申明temp為記錄結(jié)點類型l<r？i,j分別賦值為l,r;temp賦為以i為下標的值i!=j?比較、交換找到以i為下標元素的排序位置對i值的前面部分繼續(xù)快速排序endNYYN將找到的位置賦值(以i為下標的記錄)對i值的前面部分繼續(xù)快速排序?qū)φ麄€文件排序，只需調(diào)用quickSort(pvector,0,n-1)即可l,r為待比較記錄序列的頭位置和尾位置25快速排序算法26當待排序記錄已經(jīng)排序時，算法的執(zhí)行時間最長第一趟經(jīng)過n-1次比較，將第一個記錄定位在原來的位置上，并得到一個包括n-1個記錄的子文件第二趟經(jīng)過n-2次比較，將第二個記錄定位在原來的位置上，并得到一個包括n-2個記錄的子文件；…這樣最壞情況總比較次數(shù)為快速排序算法評價2728最好情況下，每次劃分使兩個子區(qū)的長度大致相等C(n)≤n+2C(n/2)≤n+2[n/2+2C(n/22)]=2n+4c(n/22)≤…≤kn+2kC(n/2k)=nlog2n+nC(1)=O(nlog2n)快速排序的平均時間復雜度是T(n)=O(nlog2n)快速排序是不穩(wěn)定的快速排序算法評價(續(xù))28分配排序分配排序是一種借助多關(guān)鍵碼排序思想對單關(guān)鍵碼排序的方法29例子∶撲克牌排序要求:每張撲克牌具有兩個屬性∶花色（梅花<方塊<紅心<黑桃）和面值（2<3<…<10<J<Q<K<A），且花色的地位高于面值，排序后為∶梅花2，…，梅花A，方塊2，…，方塊A，紅心2，…，紅心A，黑桃2，…，黑桃A 分配排序例子30撲克牌排序方法排序有以下兩種方法∶第一是先將牌按花色分成4堆，然后將每堆按面值從小到大排序，最后按花色從小到大迭在一起第二種是先將牌按面值大小分成13堆，然后從小到大把它們收集起來，再按花色分成4堆，最后順序地收集起來

31對多關(guān)鍵碼有序一般情況下，假設(shè)文件F有n個記錄

F=(R0，R1，…Rn-1)且每個記錄Ri中含有d個關(guān)鍵碼(ki0,ki1,…,kid-1)，則文件對關(guān)鍵碼(k0,k1,…,kd-1)有序是指∶文件中任意兩個記錄Ri和Rj(0≤i≤j≤n-1)滿足詞典次序有序關(guān)系

(ki0,ki1,…,kid-1)<(kj0,kj1,…,kjd-1)

其中k0稱為最高位關(guān)鍵碼，kd-1稱為最低位關(guān)鍵碼32高位優(yōu)先法:先對最高位關(guān)鍵碼k0排序，將文件分成若干堆每堆中的記錄都具有相同的k0然后分別就每堆對關(guān)鍵碼k1排序，分成若干子堆，如此重復，直到對kd-1排序最后將各堆按次序疊在一起成為一個有序文件低位優(yōu)先法:從最低位關(guān)鍵碼kd-1起排序然后再對高一位關(guān)鍵碼kd-2排序如此重復，直到對K0排序后便成為一個有序文件多關(guān)鍵碼排序算法33低位優(yōu)先法比高位優(yōu)先法簡單，高位優(yōu)先排序必須將文件逐層分割成若干子文件，然后各子文件獨立排序低位優(yōu)先排序不必分成子堆，對每個關(guān)鍵碼都是整個文件參加排序，且可通過若干次“分配”和“收集”實現(xiàn)排序基數(shù)排序就是用低位優(yōu)先法對單邏輯關(guān)鍵碼排序的一種方法分配排序算法34方法:把每個排序碼看成是一個d元組∶

Ki=(Ki0,Ki1,…,Kid-1)其中每個Ki都是集合{C0，C1，…，Cr-1}(C0<C1<…<Cr-1)中的值即C0≤Kij≤Cr-1(0≤i≤n-1,0≤j≤d-1)其中r稱為基數(shù)排序時先按Kid-1從小到大將記錄分配到r個堆中然后依次收集，再按Kid-2分配到r個堆中如此反復，直到對Ki0分配、收集，得到的便是排好序的序列基數(shù)排序35基數(shù)排序方法(續(xù))基數(shù)排序時，為了實現(xiàn)記錄的分配和收集，可以設(shè)r個隊列，排序前為空隊列，分配時將記錄插入到各自的隊列中，收集時將隊列中的記錄排在一起。36初始序列為36，5，16，98，95，47，32，36’，48，10，請用基數(shù)排序法排序。

(1)初始狀態(tài)

36→5→16→98→95→47→32→36’→48→10

例題3738例題(續(xù))(2)第一趟分配后

38(3)第一趟收集后

10→32→5→95→36→16→36’→47→98→48(4)第二趟分配后 例題(續(xù))39例題(續(xù))40(5)第二趟收集后

5→10→16→32→36→36’→47’→48→95→98

例題(續(xù))41基數(shù)排序算法中，沒有排序碼的比較和記錄的移動，只是對鏈表的掃描和指針的賦值，所以，時間耗費主要在修改指針上每趟排序中，清隊列的時間為O(r)，將n個記錄分配到隊列的時間為O(n)，收集的時間為O(r)，因此，一趟排序的時間為O(r+n)總共要進行d趟排序，基數(shù)排序的時間復雜度是T(n)=O(d*(r+n))當n較大、d較小，特別是記錄的信息量較大時，基數(shù)排序非常有效基數(shù)排序算法評價42基數(shù)排序中，每個記錄中增加了一個next字段，還增加了一個queue數(shù)組，故輔助空間為S(n)=O(n+r)基數(shù)排序是穩(wěn)定的基數(shù)排序算法評價(續(xù))43各種排序方法的比較排序算法之間的比較主要考慮以下幾個方面∶算法的時間復雜度算法的輔助空間排序的穩(wěn)定性算法結(jié)構(gòu)的復雜性參加排序的數(shù)據(jù)的規(guī)模排序碼的初始狀態(tài)各種排序算法的時間復雜度與輔助空間及算法的穩(wěn)定性如下表所示444545Shell排序、堆排序、快速排序及歸并排序的排序速度較快，其它排序方法的速度較慢從算法結(jié)構(gòu)的簡單性看，速度慢的排序算法比較簡單、直接Shell排序法，快速排序法、堆排序法及歸并排序法可以看作是對某一種排序方法的改進，算法