第6章 排序與選擇

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

整個(gè)排序過程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序。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)排序結(jié)果：2023/2/36算法分析時(shí)間復(fù)雜度若待排序記錄按關(guān)鍵字從小到大排列(正序)關(guān)鍵字比較次數(shù)：記錄交換次數(shù)：若待排序記錄按關(guān)鍵字從大到小排列(逆序)關(guān)鍵字比較次數(shù)：記錄交換次數(shù)：∴T(n)=O(n2)算法描述2023/2/376.1.3選擇排序基本思想：首先通過n-1次關(guān)鍵字比較，從n個(gè)記錄中找出關(guān)鍵字最小的記錄，將它與第一個(gè)記錄交換；再通過n-2次比較，從剩余的n-1個(gè)記錄中找出關(guān)鍵字次小的記錄，將它與第二個(gè)記錄交換；重復(fù)上述操作，共進(jìn)行n-1趟排序后，排序結(jié)束。6.1簡單排序算法2023/2/38例初始：[49386597761327]kjjjjjjkki=01349一趟：

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

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

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

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

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

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

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

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

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

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

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

事實(shí)上，

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

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

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

l，m，r)反復(fù)地合并其相鄰的兩段，最后也可達(dá)到將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特殊有序集的線性時(shí)間排序算法6.4.0引言到目前為止，所討論的排序算法有2個(gè)共同的特點(diǎn)：(1)它們要排序的集合的全集的基數(shù)沒有限制。(2)它們用于確定排序結(jié)果的主要運(yùn)算是輸入元素間的比較。這類排序算法稱為基于比較的排序算法?；诒容^的排序算法的計(jì)算時(shí)間下界是?(nlogn)。本節(jié)討論要排序的集合的全集的基數(shù)m有限制的情形。對這種情形的排序，有比基于比較更有效的算法——線性時(shí)間排序算法，但是，它們都要以花費(fèi)更多的空間為代價(jià)。

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

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

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

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

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

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

同一個(gè)桶中的元素序列：用單鏈實(shí)現(xiàn)的隊(duì)列。它以分別指向隊(duì)首和隊(duì)尾結(jié)點(diǎn)的兩個(gè)指針為標(biāo)識。

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特殊有序集的線性時(shí)間排序算法6.4.2桶排序算法(2)實(shí)現(xiàn)算法的準(zhǔn)備—數(shù)據(jù)結(jié)構(gòu)的選擇(續(xù))為全集有序元素鍵值(在1與m之間)序列設(shè)置的桶序列：由兩個(gè)指針數(shù)組bottom和top來表達(dá)。Bottom[i]和top[i]分別指向第i桶中元素隊(duì)列首結(jié)點(diǎn)和尾結(jié)點(diǎn)。bi(1)bi(2)0bi(k)01immi10……bottom

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

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

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