第6章 排序與選擇

第6章排序與選擇6.3快速排序算法6.4合并排序算法6.5線性時間排序算法6.6中位數(shù)與第k小元素6.1簡單排序算法6.2堆排序算法2023/2/316.1.1冒泡排序基本思想：將第一個記錄的關鍵字與第二個記錄的關鍵字進行比較，若為逆序(即：a[0].key>a[1].key)，則交換；然后比較第二個記錄與第三個記錄；依次類推，直至第n-1個記錄和第n個記錄比較為止——第一趟冒泡排序，結果關鍵字最大的記錄被安置在最后一個記錄上對前n-1個記錄進行第二趟冒泡排序，結果使關鍵字次大的記錄被安置在第n-1個記錄位置重復上述過程，直到“在一趟排序過程中沒有進行過交換記錄的操作”為止6.1簡單排序算法2023/2/32例：49389776132730初始關鍵字38497613273097第一趟384913273076第二趟3813273049第三趟13273038第四趟132730第五趟384976971397279730971376767627301349274930491338383038272023/2/33算法描述算法分析時間復雜度最好情況（正序）比較次數(shù)：n(n-1)/2交換次數(shù)：0最壞情況（逆序）比較次數(shù)：交換次數(shù)：∴T(n)=O(n2)2023/2/346.1.2直接插入排序基本思想：

整個排序過程為n-1趟插入，即先將序列中第1個記錄看成是一個有序子序列，然后從第2個記錄開始，逐個進行插入，直至整個序列有序。6.1簡單排序算法2023/2/35例

49386597761327i=138(3849)6597761327i=265(384965)97761327i=397(38496597)761327i=476(3849657697)1327i=513(133849657697)27i=0()i=6(133849657697)2727j=i-1jjjjj977665493827

(13273849657697)排序結果：2023/2/36算法分析時間復雜度若待排序記錄按關鍵字從小到大排列(正序)關鍵字比較次數(shù)：記錄交換次數(shù)：若待排序記錄按關鍵字從大到小排列(逆序)關鍵字比較次數(shù)：記錄交換次數(shù)：∴T(n)=O(n2)算法描述2023/2/376.1.3選擇排序基本思想：首先通過n-1次關鍵字比較，從n個記錄中找出關鍵字最小的記錄，將它與第一個記錄交換；再通過n-2次比較，從剩余的n-1個記錄中找出關鍵字次小的記錄，將它與第二個記錄交換；重復上述操作，共進行n-1趟排序后，排序結束。6.1簡單排序算法2023/2/38例初始：[49386597761327]kjjjjjjkki=01349一趟：

13[386597764927]i=1kkjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序結束：

132738496576972023/2/39算法描述算法評價時間復雜度記錄交換次數(shù)：最好情況：0最壞情況：n-1比較次數(shù)：∴T(n)=O(n2)返回章目錄2023/2/3106.2快速排序算法

6.2.0算法的基本策略思想——非平衡、預處理二分分治第一步對于給定的數(shù)組a[p:r],p<r,以x=a[p]為基準，調整a[p:q]，使得能夠確定一個下標q,p≦q≦r，將a[p:r]分成3段,即：a[p:q-1]，a[q]和a[q+1:r],滿足a[p:q-1]中的任一元素都不大于x,同時，a[q+1:r]中的任一元素都不小于x；這叫劃分(Partition)。第二步將這種策略依次分別遞歸地運用于a[p:q-1]和a[q+1:r],使得a[p:q-1]和a[q+1:r]分別從小到大排好序;從而達到數(shù)組a[p:r]從小到大就地排好序。2023/2/3116.2快速排序算法

6.2.1快速排序(QuickSort)算法的實現(xiàn)://對a[0:n-1]快速排序只要調用QuickSort(a,0,n-1);

2023/2/3126.2.2劃分(Partition)的實現(xiàn)2023/2/3136.2.3算法的性能分析

快速排序的運行時間與劃分是否平衡密切相關。對于輸入序列a[0:n-1]，Partition的計算時間顯然為O(n)。它的最壞情況發(fā)生在劃分產(chǎn)生的兩段分別包含n-1個元素和1個元素的時候。如果算法每一次調用Partition都出現(xiàn)這種不平衡劃分，則QuickSort(a,0,n-1)的耗時T(n)滿足2023/2/314算法的性能分析：在最好情況下，每次劃分所取的基準都恰好為中值，即每次劃分都產(chǎn)生大小相當?shù)?段，則T(n)滿足2023/2/3156.2快速排序算法6.2.4隨機快速排序算法(1)算法的動因可以證明，如果在a[0:n-1]中選擇的作為劃分(Partition)的基準值是隨機的，那么，快速排序算法在平均情況下的時間復雜性就是O(nlogn)，即達到基于比較的排序算法類中的最好水平。因此，人們提出:劃分(Partition)的基準值不固定為數(shù)組的第1個值而是隨機在a[p:r]中地挑選。其他思想不變，這就是隨機快速排序算法。2023/2/3166.2.4隨機快速排序算法(續(xù))

(2)隨機版的劃分的實現(xiàn)2023/2/3176.2.4隨機快速排序算法(續(xù))（3）隨機快速排序算法的實現(xiàn)返回章目錄2023/2/3186.3合并排序算法(非就地)

6.3.1遞歸版的合并排序算法(1)基本策略思想——平衡、簡單二分分治：將待排序元素序列簡單地分成大小大致相等的左右兩段，接著依次分別對這兩段子序列遞歸地進行合并排序，然后利用這兩段子序列已得到的有序性，將它們有序地合并在一個工作區(qū)，最后用工作區(qū)中排好序的全序列更新原待排序的元素序列成為所要求的排好序的元素序列。2023/2/3196.3合并排序算法(非就地)

6.3.1遞歸版的合并排序算法(2)算法的實現(xiàn)2023/2/320R.Sedgewick發(fā)明的一個優(yōu)化歸并排序方法：2023/2/3216.3合并排序算法(非就地)

6.3.1遞歸版的合并排序算法算法的復雜度顯然,Copy可在O(n)時間內完成。也容易理解，Merge可在O(n)時間內完成。因此合并排序算法對n個元素進行排序，在最壞情況下所需的計算時間T(n)滿足解此遞歸方程可知T(n)=O(nlogn)。由于基于比較的排序問題的計算時間下界為Ω(nlogn)，故合并排序算法是一個漸近最優(yōu)算法。但它需要加倍的空間,即需要O(n)的輔助空間。2023/2/3226.3合并排序算法(非就地)

6.3.2非遞歸版的合并排序算法(1)基本思想

事實上，

算法MergeSort的遞歸過程只是將待排序數(shù)組一分為二，直至待排序數(shù)組中只有1個元素為止(它已有序)。然后不斷地合并相鄰的2個已有序的數(shù)組段。按此機制，可以首先將數(shù)組a中相鄰元素兩兩配對。用Merge算法將它們合并，得到n/2個長度為2的排好序的數(shù)組段。然后再將它們Merge成長度為4的排好序的數(shù)組段，…，如此繼續(xù)下去，直至整個數(shù)組排好序。2023/2/3236.3合并排序算法(非就地)

6.3.2非遞歸版的合并排序算法(2)算法的實現(xiàn)2023/2/3246.3合并排序算法(非就地)

6.3.2非遞歸版的合并排序算法(3)需要的函數(shù)2023/2/3256.3合并排序算法(非就地)6.3.3自然合并排序算法(1)基本思想事實上，任意給定的數(shù)組a都是由不多于n段自然有序的子數(shù)組拼接起來的，如{4，8，3，7，1，5，6，2}就是由自然排好序的子數(shù)組{4，8}，{3，7}，{1，5，6}和{2}拼接起來的。而且可以在O(n)的時間里把這些子數(shù)組的界限找出來。因此我們不妨按照這種自然的有序段，通過調用Merge(c，d，

l，m，r)反復地合并其相鄰的兩段，最后也可達到將a排序的目的。例如由{4，8，3，7，1，5，6，2}?{4，8}，{3，7}，{1，5，6}和{2}?{3，4，7，8}和{1，2，5，6}?{1，2，3，4，5，6，7，8}。返回章目錄2023/2/3266.4特殊有序集的線性時間排序算法6.4.0引言到目前為止，所討論的排序算法有2個共同的特點：(1)它們要排序的集合的全集的基數(shù)沒有限制。(2)它們用于確定排序結果的主要運算是輸入元素間的比較。這類排序算法稱為基于比較的排序算法。基于比較的排序算法的計算時間下界是?(nlogn)。本節(jié)討論要排序的集合的全集的基數(shù)m有限制的情形。對這種情形的排序，有比基于比較更有效的算法——線性時間排序算法，但是，它們都要以花費更多的空間為代價。

2023/2/3276.4特殊有序集的線性時間排序算法6.4.1計數(shù)排序算法

(1)算法的基本思想：對于要排序的a[0:n-1]中的每一個元素，設法計算出它在最終排序結果序列中的序號，然后對號入座。設全集S的基數(shù)為m。由于S的有序性，我們可以按照它的序，給S的元素設立一個計數(shù)器數(shù)組c[0:m]。其中的c[i]用來統(tǒng)計S的第i個元素出現(xiàn)在a[0:n-1]中的次數(shù)，i=1,2,3,…,m。由c[0:m]便可計算出a[0:n-1]中每一個元素在排序結果序列中的序號，從而解決a[0:n-1]的排序問題。2023/2/3286.4特殊有序集的線性時間排序算法6.4.1計數(shù)排序算法

(2)算法的實現(xiàn)：2023/2/3296.4特殊有序集的線性時間排序算法6.4.1計數(shù)排序算法

(3)算法的復雜度分析：對數(shù)組c初始化需要O(m)的時間。統(tǒng)計出現(xiàn)在a[0:n-1]中的元素的出現(xiàn)次數(shù)需要O(n)的時間。對所有i統(tǒng)計出現(xiàn)在a[0:n-1]中的元素值小于或等于i(1≦i≦m)的元素個數(shù)需要O(m)的時間。最后，讓a[0:n-1]中的所有元素到達排序結果數(shù)組b中正確位置需要O(n)的時間。這樣，整個算法所需的計算間為O(m+n)。當m=O(n)時算法的計算時間復雜性為O(n)。算法需要的空間顯然為O(m)。2023/2/3306.4特殊有序集的線性時間排序算法6.4.2桶排序算法(1)算法的基本思想：

給全集的每一個元素鍵值設一個相應的桶，并將要排序的元素按鍵值對號入桶，讓同一個桶內的元素保有它們被輸入時的相對順序；然后利用全集的有序性，按鍵值的序收集各相應的桶中的元素。這樣，所得到的元素序列就是所要求的排好序的序列。2023/2/3316.4特殊有序集的線性時間排序算法6.4.2桶排序算法(2)實現(xiàn)算法的準備—數(shù)據(jù)結構的選擇待排序的元素序列：用單鏈實現(xiàn)的表List<T>

排好序的元素序列：用單鏈實現(xiàn)的表List<T>

同一個桶中的元素序列：用單鏈實現(xiàn)的隊列。它以分別指向隊首和隊尾結點的兩個指針為標識。

a(1)a(2)a(3)0a(n)……first0a(in)a(i3)a(i2)a(i1)……first0b(k)b(3)b(2)b(1)……bottomtop2023/2/3326.4特殊有序集的線性時間排序算法6.4.2桶排序算法(2)實現(xiàn)算法的準備—數(shù)據(jù)結構的選擇(續(xù))為全集有序元素鍵值(在1與m之間)序列設置的桶序列：由兩個指針數(shù)組bottom和top來表達。Bottom[i]和top[i]分別指向第i桶中元素隊列首結點和尾結點。bi(1)bi(2)0bi(k)01immi10……bottom

top首結點尾結點2023/2/3336.4.2桶排序算法(3)算法的復雜度分析：桶排序算法與計數(shù)排序算法大致相同，它們都需要O(m+n)計算時間。初始化空桶需要O(m)時間。將所有待排序元素對號裝入桶中共需O(n)時間。將桶中元素依序連接共需O(m)時間。于是，整個桶排序算法共要O(m+n)時間。與計數(shù)排序算法類似，如果m=O(n)，則桶排序算法只需要O(n)計算時間。桶排序算法也需要O(m)的空間。2023/2/3346.5中位數(shù)與第k小元素

6.5.0引言(1)概念與術語中位數(shù)第k小元素(2)問題的提法：給定線性序集中n個元素和一個整數(shù)k，1≤k≤n,要求不經(jīng)排序而找出這n個元素中第k小(大)的元素。當k=1時，就是要找最小(大)元素;當k=n時，就是要找最大(小)元素;當k=(n+1)/2時，就是要找中位元素。2023/2/3356.5.1平均情況下的線性時間選擇算法(1)基本思想——不平衡、預處理的二分分治與二分查找類似。但二分查找的預處理只做一次，而且二分是平衡二分。這里借助隨機劃分RandomizedPartition做預處理，然后根據(jù)k值決定在分出的兩段中哪一段遞歸地查找。2023/2/3366.5.1平均情況下的線性時間選擇算法(2)算法的實現(xiàn)2023/2/3376.5.1平均情況下的線性時間選擇算法(3)算法的復雜度分析容易看出,在最壞情況下,算法RandomizedSelect需要O(n2)的計算時間。例如在找最大元素時，總是在最小元素處劃分。但該算法的平均性能很好。由于隨機劃分函數(shù)RandomizedPartition使用了一個隨機數(shù)產(chǎn)生器Random，它能隨機地產(chǎn)生p和r之間的一個隨機整數(shù)，因此，RandomizedPartition產(chǎn)生的劃分基準是隨機的。在這個條件下，可以證明：算法RandomizedSelect可以在平均時間O(n)內找出n個輸入元素中的第k小元素。

2023/2/3386.5.2最壞情況下的線性時間選擇算法(1)Select算法的基本思想在線性時間內找一個劃分基準，使得按這個基準將輸入的數(shù)組劃分成的兩個子數(shù)組的長度，即使在最壞的情況下，也不會嚴重失衡，以便采用類似于RandomizedSelect的分治策略，在最壞情況下用O(n)的時間完成選擇任務。2023/2/3396.5.2最壞情況下的線性時間選擇算法(2)Select算法找劃分基準的一種構思①不計n個輸入元素的最后(nmod