鏈?zhǔn)綒w并排序法

摘要：介紹一種鏈?zhǔn)酱鎯?chǔ)的逐步歸并排序算法，其最佳時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

關(guān)鍵詞：鏈表；歸并排序；算法；復(fù)雜性

0 引言

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

數(shù)十年來(lái)，人們?cè)诖藛?wèn)題上進(jìn)行了不懈的研究，獲得了大量的研究成果，各種排序方法有近百種之多。這其中最常用的就有：快速排序、希爾排序、冒泡排序、插入排序、選擇排序、堆排序、歸并排序、基數(shù)排序、雜湊排序等十多種排序算法。這些排序算法基本上可以歸為兩大類：基于比較的排序和不基于比較的排序。基于比較的排序是指要將各個(gè)數(shù)據(jù)項(xiàng)進(jìn)行直接或間接的比較以確定每個(gè)數(shù)據(jù)的最終位置。理論研究表明，不基于比較的排序如基數(shù)排序、雜湊排序的時(shí)間復(fù)雜度可以達(dá)到O(n)，但問(wèn)題是這類排序一般都需要較大的輔助空間，而且對(duì)數(shù)據(jù)項(xiàng)有著比較嚴(yán)格的要求，只能在特性場(chǎng)合下使用?；诒容^的排序的時(shí)間下限是O(nlog2n)，快速排序、堆排序、歸并排序的平均時(shí)間復(fù)雜度都可以達(dá)到這個(gè)級(jí)別。這類排序?qū)?shù)據(jù)項(xiàng)沒(méi)有任何限制，因而獲得了更為廣泛的應(yīng)用。本文是在數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)的基礎(chǔ)上對(duì)數(shù)據(jù)進(jìn)行排序方法的探討，從逐漸合并有序鏈來(lái)達(dá)到排序的目的。

1 算法的基本思路

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

1.1鏈?zhǔn)綒w并排序算法的基本思想

首先根據(jù)原始數(shù)據(jù)的順序建立一條單鏈表，將在無(wú)序鏈中以表首結(jié)點(diǎn)為首結(jié)點(diǎn)尋找一條新的有序鏈，將其歸并到原來(lái)的有序鏈中，再在剩下的無(wú)序鏈中以表首結(jié)點(diǎn)為首結(jié)點(diǎn)尋找一條有序鏈，再歸并……直到所有結(jié)點(diǎn)都?xì)w并到有序鏈中去為止。

1.2具體算法描述

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

Step 2：將工作指針p指向原鏈表link表的新的表首結(jié)點(diǎn)；

Step 3：如果p為空，轉(zhuǎn)step 8，否則繼續(xù)進(jìn)行；

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

Step 5：如果p為非空，則繼續(xù)Setp 6，否則轉(zhuǎn)step7；

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

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

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

1.3算法示例

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

具體排序過(guò)程見(jiàn)圖1～圖5所示：

1.4算法流程圖

算法流程圖如圖6所示。

2 算法分析

2.1時(shí)間復(fù)雜度

(1)當(dāng)原始待排數(shù)據(jù)為正序有序時(shí)，只需進(jìn)行一趟就結(jié)束，時(shí)間復(fù)雜度為O(n)(最好情況)；

(2)當(dāng)原始待排數(shù)據(jù)為逆序有序時(shí)，每一趟新有序鏈表中只有一個(gè)結(jié)點(diǎn)，需進(jìn)行n-1趟，蛻化到選擇排序，其時(shí)間復(fù)雜度即為O(n²)(最壞情況，有待改進(jìn))；

(3)當(dāng)原始待排數(shù)據(jù)為隨機(jī)分布時(shí)，時(shí)間復(fù)雜度為O(nlogn)；

(4)當(dāng)原始待排數(shù)據(jù)為所有值相同時(shí)，只需進(jìn)行一趟就結(jié)束，時(shí)間復(fù)雜度為O(n)；

(5)當(dāng)原始待排數(shù)據(jù)為波形分布(假定波長(zhǎng)為C)時(shí)，時(shí)間復(fù)雜度為O(Cn)；

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

2.2空間復(fù)雜性

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

3 結(jié)束語(yǔ)

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