鏈式歸并排序法

摘要：介紹一種鏈式存儲的逐步歸并排序算法，其最佳時間復雜度為O(n)，空間復雜度為O(1)。

關鍵詞：鏈表；歸并排序；算法；復雜性

0 引言

排序問題是指給定一個數據項集，使其中的數據按遞增或遞減排列。數據項可以是具有線性順序的任意對象。排序是計算機科學中最重要的研究課題之一，據統計，在大型計算中心，排序工作往往要占去大約1/4的計算時間。排序具有極高的理論和實際價值，2000年被列為對科學和工程計算的研究與實踐影響最大的十大問題之一。對排序算法的研究無論是在理論上還是在實踐上都具有重大的意義。

數十年來，人們在此問題上進行了不懈的研究，獲得了大量的研究成果，各種排序方法有近百種之多。這其中最常用的就有：快速排序、希爾排序、冒泡排序、插入排序、選擇排序、堆排序、歸并排序、基數排序、雜湊排序等十多種排序算法。這些排序算法基本上可以歸為兩大類：基于比較的排序和不基于比較的排序。基于比較的排序是指要將各個數據項進行直接或間接的比較以確定每個數據的最終位置。理論研究表明，不基于比較的排序如基數排序、雜湊排序的時間復雜度可以達到O(n)，但問題是這類排序一般都需要較大的輔助空間，而且對數據項有著比較嚴格的要求，只能在特性場合下使用。基于比較的排序的時間下限是O(nlog2n)，快速排序、堆排序、歸并排序的平均時間復雜度都可以達到這個級別。這類排序對數據項沒有任何限制，因而獲得了更為廣泛的應用。本文是在數據的鏈式存儲的基礎上對數據進行排序方法的探討，從逐漸合并有序鏈來達到排序的目的。

1 算法的基本思路

我們知道歸并排序是將序列分成基本均勻的兩部分，對兩部分都需排序之后再合并。該算法的優點是無論原序列的分布情況如何，它的劃分總是均勻的，因此最好情況和最壞情況的時間復雜度都是O(nlog2n)，空間復雜度為O(n)。它采用的是順序存儲，算法用遞歸的方式實現。如果我們用非順序的方式，用不等長的非遞歸方式實現可以得到性能更好的歸并排序算法。

1.1鏈式歸并排序算法的基本思想

首先根據原始數據的順序建立一條單鏈表，將在無序鏈中以表首結點為首結點尋找一條新的有序鏈，將其歸并到原來的有序鏈中，再在剩下的無序鏈中以表首結點為首結點尋找一條有序鏈，再歸并……直到所有結點都歸并到有序鏈中去為止。

1.2具體算法描述

Step 1：輸入n個待排數據，用插入法建立一條單鏈表為原鏈表link；將原有序鏈lastorderlink和新有序鏈neworderlink都初始化為空鏈表；

Step 2：將工作指針p指向原鏈表link表的新的表首結點；

Step 3：如果p為空，轉step 8，否則繼續進行；

Step 4：將原鏈表link表的表首結點(p所指結點)取出(p指針需下移一位)作為新有序表neworderlink的表首結點插入；

Step 5：如果p為非空，則繼續Setp 6，否則轉step7；

Setp 6：如果p所指結點的值不小于新有序表neworderlink的表尾結點值就從rink表中取出并將其插入到neworderfink表的鏈尾，p指針下移，否則p指針僅下移，轉Step 5；

Setp 7：將新有序表neworderlink歸并到原有序鏈las-torderlink中，并將新有序鏈neworderlink置為空表，轉Step 2；

Setp 8：排序結束，lastorderlink中即為有序鏈表。

1.3算法示例

示例如下：原始數據為：32、59、21、12、45、89、63、34、26、11、7、6、18、24、29、64、3、46、77、22。以頭插入的方式建立單鏈表。

具體排序過程見圖1～圖5所示：

1.4算法流程圖

算法流程圖如圖6所示。

2 算法分析

2.1時間復雜度

(1)當原始待排數據為正序有序時，只需進行一趟就結束，時間復雜度為O(n)(最好情況)；

(2)當原始待排數據為逆序有序時，每一趟新有序鏈表中只有一個結點，需進行n-1趟，蛻化到選擇排序，其時間復雜度即為O(n²)(最壞情況，有待改進)；

(3)當原始待排數據為隨機分布時，時間復雜度為O(nlogn)；

(4)當原始待排數據為所有值相同時，只需進行一趟就結束，時間復雜度為O(n)；

(5)當原始待排數據為波形分布(假定波長為C)時，時間復雜度為O(Cn)；

(6)當原始待排數據為峰型分布(先正序后逆序)和谷型分布(先逆序后正序)時，時間復雜度為最壞情況的一半。

2.2空間復雜性

需要幾個輔助的工作指針，空間復雜度為O(1)。

3 結束語

從上面的分析可以看出，本算法除了在隨機分布數據的排序上的效率略接近于傳統的二路歸并外，最佳情況好于后者，可見改進是成功的。當然本算法還有很多值得改進的地方。例如，當逆序或峰型谷型分布時，有待于改進。