排序問題

算法園地

編者按：教育部頒布的《普通高中信息技術(shù)課程標(biāo)準(zhǔn)（2017年版）》在“必修模塊1的教學(xué)”中用專門的單元來談?wù)摿怂惴?，這說明，新課程要求高中信息技術(shù)在教學(xué)中應(yīng)當(dāng)以算法為要旨，強化算法的重要性。

因此，本刊開設(shè)“算法園地”專欄，特邀北京大學(xué)計算機(jī)系原系主任李曉明教授、南京大學(xué)計算機(jī)系原系主任陳道蓄教授撰寫有關(guān)算法的文章，為讀者提供一些既有思想性又有實用性的材料。

專欄的讀者定位是對算法問題有興趣的中小學(xué)教師，內(nèi)容的鋪陳將努力做到通俗性、趣味性和嚴(yán)謹(jǐn)性相結(jié)合。每月介紹一個算法，每期獨立成篇，大體按照以下六個方面展開：應(yīng)用背景、算法描述、實例模擬、性質(zhì)分析、思考問題、參考代碼。你以前如果學(xué)過算法，在這里會看到一種不同的視野;你以前如果沒有學(xué)過算法，則可以通過對每月一個算法的學(xué)習(xí)，既領(lǐng)悟到算法思想的精髓，又形成算法實戰(zhàn)的能力。

我們已經(jīng)知道，在排好序的文檔中搜索，效率會比在沒有排好序的文檔中高得多。任何數(shù)據(jù)處理系統(tǒng)中可能都會用到排序算法，且可能使用頻繁，因此排序的效率尤為重要。

排序一般是根據(jù)輸入數(shù)據(jù)對象的關(guān)鍵字進(jìn)行。關(guān)鍵字均取自某全序集，全序集是指其中任意兩個元素均可“比大小”的集合。排序算法將輸入元素按照定義的次序要求輸出。為了簡單，我們假設(shè)輸入元素均為正整數(shù)（對象即關(guān)鍵字），編程時可以采用一維數(shù)組或List結(jié)構(gòu)，且序列中不含相同元素，任意兩個元素比較一定有大小之分。輸出為嚴(yán)格遞增序列。

如果關(guān)鍵字的值是不可分解的，算法能夠執(zhí)行的基本操作只是比較兩個關(guān)鍵字的大小，這樣的排序算法稱為“基于關(guān)鍵字比較的算法”，本文主要討論此類算法。（Python等語言庫函數(shù)提供了針對List結(jié)構(gòu)的排序功能，可以直接調(diào)用。當(dāng)然這不在本文考慮范圍內(nèi)）

● “冒泡”排序算法

對海量數(shù)據(jù)排序這是一個很大的挑戰(zhàn)，不過，一些廣為人知的計算機(jī)排序算法與人的思維方式并沒有什么差別。很多程序設(shè)計初學(xué)者編寫的第一個排序程序是“冒泡”排序，其基本思想可以用圖1表示。

圖1中最左邊的是輸入序列（從下向上）。我們總是試圖找出當(dāng)前待處理區(qū)域中的最大元素，將它放到最高位置，這就像水中的氣泡往上冒一樣，所以稱為“冒泡”排序。開始時待處理區(qū)域是整個序列，我們從最下面的位置開始依次向上做比較操作，一旦發(fā)現(xiàn)“逆序”，即上下位置與元素大小相反，則做一次“互換”。圖1中的箭頭表示連續(xù)執(zhí)行“互換”的結(jié)果，已經(jīng)放置到正確位置的元素用粗黑體表示，新一輪操作中這些位置不再包含在待處理區(qū)域中，重復(fù)執(zhí)行上述過程，直到待處理區(qū)域只含一個元素為止。整個過程描述如下頁圖2所示。

循環(huán)未必需要執(zhí)行到k=0才停止，如果某一輪中swap一次也沒執(zhí)行，算法就可以停止了，這只需用一個標(biāo)記變量即可。

前面提到，排序過程中用“互換”操作消除“逆序”，一般意義上的“逆序”，是指兩個對象位置下標(biāo)大小與值的大小正好相反（也稱它們的位序與值序不一致）。排序過程可以理解為消除輸入序列中的所有“逆序”的過程，如果輸入的數(shù)據(jù)值是嚴(yán)格遞減的，那么任何兩個元素均構(gòu)成“逆序”，逆序的數(shù)量為O（n2）?！懊芭荨迸判蛩惴偸潜容^相鄰的兩個對象，也只可能將兩個相鄰的對象互換，這意味著每次比較最多消除輸入中的一個逆序，因此，最壞情況下算法執(zhí)行的比較次數(shù)為O（n2）。根據(jù)隨機(jī)輸入使得任一處理區(qū)域中最大元素出現(xiàn)在任一位置的概率相等，很容易推知平均比較次數(shù)仍是平方數(shù)量級的。

理論分析告訴我們，基于關(guān)鍵字比較的排序算法比較次數(shù)不可能比O（nlogn）更好，換句話說，如果算法的效率能達(dá)到O（nlogn），就是最優(yōu)了。冒泡算法與最優(yōu)的差距有多大呢？粗略地說，如果在特定計算環(huán)境下對100萬的數(shù)據(jù)排序，某個O（nlogn）的算法需要1秒鐘，O（n2）的算法可能需要10小時以上。

● 快速排序算法

快速排序可能是應(yīng)用最廣的排序算法，其基本思想是將輸入分解為兩個規(guī)模較小的子問題，遞歸求解。算法首先調(diào)用函數(shù)partition，以一個任選的元素為“標(biāo)桿”，將比標(biāo)桿小的元素放入子集small，大的元素放入子集large。partition返回值是針對這樣的分割，標(biāo)桿元素應(yīng)該處于的位置splitPoint。函數(shù)partition的結(jié)果如圖3所示，快速排序過程如圖4所示。

接下來討論如何實現(xiàn)partition。選第一個元素做標(biāo)桿是隨意的，因為輸入的隨機(jī)性，選任意元素效果是一樣的。給定標(biāo)桿，通過比較大小分出兩個子集似乎很容易，但我們希望在“原地”操作，也就是說不用額外的存儲空間（除了標(biāo)桿本身），這需要一點“技巧”。我們用矩形框表示當(dāng)前的待處理范圍，調(diào)用partition時標(biāo)桿已選定移出，因此第一個位置是空位。在partition執(zhí)行期間始終保留一個空位。執(zhí)行過程包含一個擴(kuò)充small的過程與一個擴(kuò)充large的過程，從large開始交替進(jìn)行，同時空位也交替地出現(xiàn)在左或右（如上頁圖5）。

每一次擴(kuò)充過程的終止條件為：發(fā)現(xiàn)應(yīng)該移動的元素或者遇到空位，如果是后者，則整個partition執(zhí)行完成。圖6所示為擴(kuò)大子集small的過程，擴(kuò)大子集large的過程與extandSmall是對稱的，讀者可自行完成。

實現(xiàn)子問題分割的函數(shù)partition利用循環(huán)，交替地調(diào)用上述兩個函數(shù)（如圖7）。圖8是一個例子執(zhí)行過程的部分演示。

快速排序避免了冒泡排序中只比較相鄰元素的局限，那么其效率如何呢？遞歸算法的效率與需要遞歸的次數(shù)密切相關(guān)。一般而言，子問題規(guī)模下降快的話就會更快遇到終止條件，使遞歸次數(shù)下降。

設(shè)想輸入序列中數(shù)據(jù)嚴(yán)格遞增，從人的觀點看根本不需要計算，直接輸出就是了。但是算法看不出這一點，選中的標(biāo)桿恰好是最小元素，于是兩個子問題一個是空序列，另一個規(guī)模比原輸入只少一個元素。在這種原始輸入數(shù)據(jù)條件下，很不幸的是每次遞歸都遇到同樣情況。每次遞歸劃分子問題執(zhí)行比較操作次數(shù)為O（n），因此最壞情況下快速排序的代價仍然是O（n2）。

其實這種極端情況出現(xiàn)的概率太小了，實際經(jīng)驗與概率推導(dǎo)都表明，在應(yīng)用中快速排序完全可以降低O（nlogn）的時間復(fù)雜度，而且快速排序算法幾乎不需要額外存儲空間，其他額外開銷也很小，所以應(yīng)用廣泛。

前面提到過任一元素做標(biāo)桿碰到最壞情況的概率是一樣的（盡管各自的最壞輸入不一樣），但我們有個簡單辦法可以使碰到“最壞”輸入的概率大大降低：隨機(jī)從輸入序列中選三個元素，用大小居中的元素做標(biāo)桿。注意，不管如何選，調(diào)用partition時總讓空位在首位。

● 合并排序算法：均衡分解子問題

快速排序最壞情況下的表現(xiàn)不佳是因為兩個子問題可能大小懸殊，如果我們采用遞歸方法時設(shè)法使兩個子問題大小幾乎相等是否會產(chǎn)生更好的算法呢？

最簡單地實現(xiàn)均衡分解的做法就是一切兩半。為了簡單，假設(shè)輸入序列長度為2的整次冪，即n=2k經(jīng)過k=logn輪分解，子問題規(guī)模為1，遞歸終止。將兩個已經(jīng)排好序的序列合成一個，過程如上頁圖9所示，合并排序過程非常簡單（如上頁圖10）。

顯然，合并過程中每比較一次至少有一個元素進(jìn)入合并區(qū)，所以合并的總比較次數(shù)不會超過合并區(qū)的大小。合并總共進(jìn)行k=logn輪，每輪合并區(qū)的總規(guī)模為n，分解每個子問題的代價顯然是常量，所以合并排序最壞情況的時間復(fù)雜度為O（nlogn），當(dāng)然平均復(fù)雜度也不會更高。這意味著合并排序達(dá)到最優(yōu)，但合并排序的應(yīng)用遠(yuǎn)不如快速排序。對比前面討論快速排序時講到的一個優(yōu)點，合并排序有個明顯的缺點：合并不能在“原地”進(jìn)行，需要O（n）的額外存儲空間。

● 結(jié)束語

并非所有的排序算法都是基于關(guān)鍵字比較的算法，有時候輸入可能滿足一些特別的條件，如輸入對象的關(guān)鍵字是十進(jìn)制表示的自然數(shù)，關(guān)鍵字可以分解為“位”。比較未必非得對整個數(shù)值進(jìn)行，也可以逐位比較，還有些應(yīng)用中我們可以預(yù)先知道關(guān)鍵字值的上下界。這些條件可以利用來設(shè)計出線性代價的排序算法。

有些讀者可能非常好奇：即便限于關(guān)鍵字比較算法，以后完全有可能出現(xiàn)更聰明的人，想出更聰明的方法，現(xiàn)在怎么能確信不可能比O（nlogn）更好了呢？確實，對大多數(shù)問題判定算法的“最優(yōu)”往往很困難，但對基于關(guān)鍵字比較的排序問題我們可用圖11幫大家理解確定問題復(fù)雜度下限的基本思想。

這里的下標(biāo)1、2、3并沒有任何特殊意義，所以這個圖適用于一切對長度為3的序列排序過程。圖11中中間節(jié)點（矩形）表示一次比較操作。在輸入對象均不相等的假設(shè)下這是完全二叉樹，左右兩個子節(jié)點分別對應(yīng)于“<”和“>”兩種結(jié)果，而葉節(jié)點（橢圓）對應(yīng)一種特定的排列，也就是排序問題的解。對任一輸入，從根節(jié)點開始對關(guān)鍵字進(jìn)行比較，并根據(jù)比較結(jié)果決定下一個操作。如果遇到葉節(jié)點，則算法終止，輸出相應(yīng)結(jié)果，圖11中葉節(jié)點顯示對象遞增的次序。由于輸入是隨機(jī)的，解可能是輸入序列的任意一種（重新）排列，而n個元素的序列可能的排列方式有n！個，所以對長度為n的輸入，類似的算法樹至少有n！個葉。而算法最壞情況下復(fù)雜度的下限是圖11中從根到葉的最長路徑的下界，當(dāng)整個樹是完全平衡樹時這個下界最小，為log（n！），而log（n?。师福╪logn）。