張忠誠 魯法明

（山東科技大學(xué)計算機科學(xué)與工程學(xué)院 青島 266590）

1 引言

排序是生活中最為常用的一種算法，迄今為止，人類發(fā)明了各種各樣的排序算法，有基于插入操作的插入類排序，有基于交換操作的冒泡排序，有基于選擇操作的選擇排序等。很多精妙的排序方法背后可能隱含著相同的算法設(shè)計策略。以直接插入排序［1，8］、簡單選擇排序［1］、冒泡排序［1］、快速排序［2～3］以及歸并排序［4～5］為例，它們采用的基本操作和排序過程不同，但實際都可以由遞歸與分治策略得出。本文分析這些經(jīng)典排序算法背后隱含的遞歸與分治原理，并從遞歸與分治的角度分析它們在排序原理、排序過程以及排序性能之間存在的異同，以便于學(xué)習(xí)者加深對排序算法以及遞歸與分治策略的理解。

2 遞歸與分治的基本原理

遞歸與分治［1，7］是一種經(jīng)典的問題求解策略，其基本思想是:對于一個規(guī)模為N的問題，若該問題可以容易地解決（比如說規(guī)模N較?。﹦t直接解決，否則將其分解為k個規(guī)模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地求解這些子問題，然后將各子問題的解合并得到原問題的解。遞歸與分冶法在每一層遞歸時都有如下三大步驟:

1）將原問題分解為若干個規(guī)模較小，相互獨立，與原問題形式相同的子問題；

2）若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地求解各個子問題；

3）將這些子問題的解合并成原問題的解。

分治是思想，遞歸是手段，二者相輔相成。要想求解分治問題，最常用的方法就是針對相應(yīng)的分治問題設(shè)計遞歸函數(shù)。那么該如何設(shè)計一個遞歸函數(shù)呢？設(shè)計一個遞歸函數(shù)需要確定以下兩個條件。首先要確定遞歸邊界，即每個遞歸函數(shù)必須至少有一個遞歸邊界，當(dāng)滿足這個邊界條件時遞歸不再進行，即函數(shù)不再調(diào)用自身而是直接返回處理結(jié)果。其次要設(shè)計遞歸關(guān)系，即如何將規(guī)模較大的原問題的求解歸結(jié)為規(guī)模較小的若干子問題的求解。

3 經(jīng)典排序算法的遞歸原理

3.1 直接插入排序

3.1.1 直接插入排序過程及非遞歸實現(xiàn)

直接插入排序?qū)⒋判蛐蛄袩o序塊和有序塊，有序塊在前，無序塊災(zāi)后。通過比較和移動將無序塊首元素插入有序塊適當(dāng)位置，使得有序塊不斷變長；如此重復(fù)，N-1趟則完成排序（N為序列長度）。插入類排序的基本操作是無序塊首元素到左側(cè)有序塊的“插入”，故稱之為“插入類排序”。

基于上述關(guān)于直接插入排序的過程描述，可得直接插入排序的非遞歸實現(xiàn)如圖1所示，其中arr表示待排序數(shù)組，lengthOfArr表示待排序數(shù)組的長度，之后的所給出的程序中若無特殊說明，符號含義均是如此，同時假設(shè)題目要求是由小到大進行排序。

圖1 直接插入排序的非遞歸實現(xiàn)

圖2 直接插入排序的遞歸實現(xiàn)

3.1.2 直接插入排序的遞歸與分治原理及遞歸實現(xiàn)

分析直接插入排序的過程可見，一趟插入排序完成后，有序塊長度增加1，待處理的無序塊長度減小1。初始無序塊長度為N-1，經(jīng)過N-1趟直接插入排序后，無序塊長度變?yōu)?。將該排序過程看作無序塊的消除過程，則直接插入排序可以理解為如下一個遞歸的過程。

遞歸邊界:無序塊長度為1時自然有序，遞歸終止；

遞歸關(guān)系:無序塊長度大于1時，首先消除無序塊首元素，將其插入到左側(cè)有序塊的適當(dāng)位置，使得左側(cè)有序塊長度增加1，同時無序塊長度減小1，遞歸處理無序塊。

根據(jù)上述遞歸解釋，我們可以得到圖3所示的插入排序原理圖，相應(yīng)的直接插入排序的遞歸函數(shù)代碼見圖2。

圖3 直接插入排序圖解

3.2 冒泡排序

3.2.1 冒泡排序過程及非遞歸實現(xiàn)

冒泡排序分為多輪，每輪對待排序序列進行遍歷，遍歷過程中對相鄰的元素進行兩兩比較，如果它們的順序錯誤則交換之。上述過程重復(fù)進行，最多N-1趟則不再有交換發(fā)生，排序終止。實際上，每一輪冒泡排序都會使得當(dāng)前最大的元素沉到最底部，而小的元素不斷的朝上冒，故形象地稱之為冒泡排序?；谏鲜鲫P(guān)于冒泡排序的過程描述，可得冒泡排序的非遞歸實現(xiàn)如圖5所示。

3.2.2 冒泡排序的遞歸與分治原理及遞歸實現(xiàn)

冒泡排序的過程同樣可以用遞歸與分治的思想來解釋。待排序序列看作由有序塊和無序塊兩部分組成，無序塊在前，有序塊在后。每一輪冒泡將無序塊最大的元素都移動到有序塊的最前部，此時有序塊長度加1，無序塊長度減1。將該排序過程看作無序塊的消除過程，則冒泡排序可以理解為如下一個遞歸的過程。

遞歸邊界:無序塊長度為1時或者一輪冒泡排序沒有發(fā)生交換時，排序終止；

遞歸關(guān)系:只要不滿足遞歸邊界的條件，就遍歷當(dāng)前無序塊，從首元素開始兩兩比較，只要不滿足大小順序要求就交換，每次遞歸無序塊長度減1，遞歸處理無序塊；

根據(jù)上述遞歸解釋可得圖4所示冒泡排序的原理圖，其對應(yīng)的遞歸函數(shù)代碼見圖6。

圖4 冒泡排序圖解

圖5 冒泡排序的非遞歸實現(xiàn)

圖6 冒泡排序的遞歸實現(xiàn)

3.3 選擇排序

3.3.1 選擇排序過程及非遞歸實現(xiàn)

簡單選擇排序首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找當(dāng)前最小元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢?；谏鲜鲫P(guān)于選擇排序的過程描述我們可得選擇排序的非遞歸實現(xiàn)如圖8所示。

3.3.2 選擇排序的遞歸與分治原理及遞歸實現(xiàn)

簡單選擇排序可以看作一種貪心算法，每趟排序都挑選出當(dāng)前最小的元素放到無序塊最前端（或者說有序塊最后面）。同時，它也可以基于遞歸與分治的策略來解釋。同樣將待排序序列分為有序塊和無序塊兩部分，有序塊在前，無序塊在后，每一趟選擇排序都是將當(dāng)前子序列的最小值添加到有序塊的后面，有序塊的長度加1，無序塊的長度減1，這也是一個無序塊逐步變小過程，基于此可以得到簡單選擇排序的遞歸描述如圖7。

圖7 選擇排序圖解

遞歸邊界:長度為1的序列自然有序，遞歸終止；

遞歸關(guān)系:若長度大于1，則選擇當(dāng)前無序塊的最小值，與當(dāng)前無序塊的首元素進行交換，即添加到有序塊的后面。使得有序塊的長度加1，無序塊的長度減1，遞歸處理無序塊。

The pore throat characteristics of narrow-channel tight sandstone gas reservoirs in the

可得圖7所示冒泡排序的原理圖，其對應(yīng)的遞歸函數(shù)代碼見圖9。

圖8 選擇排序的非遞歸實現(xiàn)

圖9 選擇排序的遞歸實現(xiàn)

3.4 快速排序

快速排序直接使用遞歸與分治策略把一個待排序序列根據(jù)樞軸元素一分為二，左側(cè)子序列元素值均小于或者等于樞軸元素，右側(cè)均大于或等于樞軸元素。具體步驟如下:從序列中挑出一個元素（例如選擇待處理序列最左側(cè)元素），稱為“樞軸”或者“基準”元素，通過一趟劃分操作使得樞軸左側(cè)的元素均小于或等于基準值，樞軸右側(cè)的元素均大于或等于基準值；顯然，一趟劃分后，樞軸兩側(cè)待處理的子序列長度都比原始序列小，該過程不斷重復(fù)，最終待處理的子序列長度為1或者0試停止劃分，排序完成。根據(jù)上述快速排序的過程可得其遞歸原理如下:

遞歸邊界:序列的長度為零或1時，無需劃分，遞歸終止；

遞歸關(guān)系:當(dāng)序列的長度大于1時，則按照一定規(guī)則選擇一個值作為樞軸進行劃分，使樞軸左邊的值都小于或等于基準值，樞軸右邊的值都大于等等于基準值大。之后遞歸處理樞軸左右兩個子序列。

根據(jù)上述關(guān)于快速排序的遞歸解釋，可得圖10與圖11所示的快速排序的遞歸原理與遞歸函數(shù)。

圖10 快速排序圖解

圖11 快速排序的遞歸實現(xiàn)

3.5 歸并排序

3.5.1 歸并排序過程及非遞歸實現(xiàn)

圖12 歸并排序的非遞歸實現(xiàn)

3.5.2 歸并排序的遞歸與分治原理及遞歸實現(xiàn)

歸并排序同樣可以從遞歸和分治的角度理解。當(dāng)待排序序列長度為1時序列自然有序，此為遞歸邊界；當(dāng)待排序序列長度大于1時，將該序列從中間平均地一分為二，只要將左右兩個子序列分別排序，接下來進行這兩個子序列的有序歸并即可，如此就將N個數(shù)的排序問題歸結(jié)為了長度約為N/2的兩個子序列的排序問題，此即遞歸關(guān)系。根據(jù)上述歸并排序的遞歸與分治解釋，可得其遞歸函數(shù)的實現(xiàn)以及遞歸原理如圖13和圖14所示。

圖13 歸并排序圖解

圖14 歸并排序的遞歸實現(xiàn)

4 基于遞歸與分治的排序性能比較

由圖3、圖4以及圖7所示插入排序、冒泡排序以及選擇排序的遞歸原理可知，這三種排序算法雖然遞歸與分治的具體方法不同，但在遞歸的過程中，每次都是將原始長為N的序列的排序問題歸結(jié)為長度為N-1序列排序問題，它們都需要遞歸N-1次才能最終到達遞歸邊界，其時間復(fù)雜度都是O（N2）。

然而，由圖10所示的快速排序的遞歸原理可見，快速排序一趟劃分后，將長度為N的序列排序問題歸結(jié)為兩個長度不確定的子序列排序問題，從而其遞歸的次數(shù)也是不確定的。如果每次樞軸都能將待處理子序列等長的一分為二，則遞歸最多l(xiāng)og2N趟到達遞歸邊界，此時快速排序的時間復(fù)雜度最優(yōu)，能達到O（N log2N）；如果每次劃分都使得樞軸一側(cè)子序列長度為0、另一側(cè)子序列長度為N-1，則此時需要遞歸N-1趟方能達到遞歸邊界，此時快速排序的時間復(fù)雜度最壞為O（N2）。

就歸并排序而言，由圖13所示的遞歸原理可知，歸并排序每趟都將原序列的排序問題歸結(jié)為長度大致相等的兩個子序列的排序，此時最多l(xiāng)og2N趟切分即可到達遞歸邊界，所以其時間復(fù)雜度恒為O（N log2N）［9］。

綜上所述，上述五種排序算法的背后都隱含著遞歸與分治的解題策略，但是由于遞歸次數(shù)的不同導(dǎo)致了算法性能的不同。在基于遞歸與分治策略求解問題時，設(shè)計的遞歸關(guān)系應(yīng)使子問題的規(guī)模減小的盡量快，越快到達遞歸邊界則算法性能越高。

5 結(jié)語

本文從遞歸與分治的求解策略出發(fā)，對直接插入排序、冒泡排序、選擇排序、快速排序、歸并排序等經(jīng)典排序算法的排序原理進行了新的解讀，由文中分析可見，上述排序算法雖然具體的排序過程以及采用的就排序基本操作不同，有的基于插入，有的基于交換，有的基于選擇，有的基于歸并，但它們背后都隱含了遞歸與分治的問題求解策略，而且這些排序算法性能上的不同也可以從遞歸次數(shù)的角度進行統(tǒng)一解釋。實際上，現(xiàn)實世界中的問題多種多樣，但通用的問題求解策略卻往往沒有多少，遞歸與分治就是其中最典型的一個，它不僅可以用于排序，在Strassen矩陣乘法、棋盤覆蓋等其他經(jīng)典問題中也有廣泛應(yīng)用。后續(xù)工作中，可以繼續(xù)探究希爾排序［10～11］、堆排序［12～14］、基數(shù)排序［15］等經(jīng)典排序算法背后隱含的其他問題求解策略。