一種線性時間排序算法的實(shí)現(xiàn)

摘要：提出一種不依賴關(guān)鍵字的分布，數(shù)據(jù)位數(shù)不受限制的整型或?qū)嵭蛿?shù)的內(nèi)部排序算法，其時間和空間復(fù)雜度均為O(n)。給出了算法思想和算法分析結(jié)果。

關(guān)鍵詞：排序；算法；有序樹；復(fù)雜性

0 引言

排序是計(jì)算機(jī)科學(xué)中一項(xiàng)復(fù)雜而重要的技術(shù)，無論在系統(tǒng)軟件還是應(yīng)用軟件中使用頻率都很高。許多專家學(xué)者對排序問題講行了深入的研究，給出了許多時間復(fù)雜度為O(n)的高效排序算法。其中有許多排序算法充分利用待排序數(shù)據(jù)的分布信息，降低了排序算法的時間復(fù)雜度；有的排序效率過分依賴于關(guān)鍵字的均勻分布且算法不穩(wěn)，僅適用于數(shù)據(jù)位很少的一類數(shù)據(jù)排序；有的算法穩(wěn)定但只針對具有均勻分布或近似均勻分布的數(shù)據(jù)。本文提出一種不依賴關(guān)鍵字的分布，數(shù)據(jù)位數(shù)不受限制的整型或?qū)嵭蛿?shù)的排序，此思想亦可應(yīng)用到字符型數(shù)據(jù)的排序，且時間和空間復(fù)雜度均為O(n)。

1 算法思想

假定待排數(shù)據(jù)為大于0的實(shí)型數(shù)且放在數(shù)組A中。排序的主要工作是創(chuàng)建一棵有序樹。首先找到這組數(shù)中值最大和最小的數(shù)以確定樹根結(jié)點(diǎn)的大小，根結(jié)點(diǎn)為一指針類型的數(shù)組root，假定最大數(shù)的十進(jìn)制階碼為max，最小數(shù)的十進(jìn)制階碼為min，那么root數(shù)組大小為max-min+1即root[min..max]，root[O]指向10₀的子樹根結(jié)點(diǎn)，root[1]指向10₁的子樹根結(jié)點(diǎn)……root[n]指向10₀的子樹根結(jié)點(diǎn)，中間分支結(jié)點(diǎn)為一大小為10的指針數(shù)組B[10]。如果把根結(jié)點(diǎn)所在的一層約定為第0層，那么第1層中B1[0]指向尾數(shù)中第1位值為0的子樹根結(jié)點(diǎn)，B1[1]指向尾數(shù)中第1位值為1的子樹根結(jié)點(diǎn)……B1[9]指向尾數(shù)中第1位值為9的子樹根結(jié)點(diǎn)；第2層中B2[0]指向尾數(shù)中第2位值為0的子樹根結(jié)點(diǎn)，B2[1]指向尾數(shù)中第2位值為l的子樹根結(jié)點(diǎn)……B2[9]指向尾數(shù)中第2位值為9的子樹根結(jié)點(diǎn)；……待排數(shù)據(jù)均放在葉子結(jié)點(diǎn)上，葉子結(jié)點(diǎn)類型為待排數(shù)據(jù)類型的單鏈表，數(shù)的深度取決于待排數(shù)據(jù)中尾數(shù)的最大長度len，所有葉子結(jié)點(diǎn)都在第len+1層。將數(shù)組A中所有的數(shù)據(jù)都插入上述樹中，然后將葉子結(jié)點(diǎn)按從左到右輸出即為—個已經(jīng)排好序的有序序列。例如待排數(shù)據(jù)為{860，734，53，5，9，16，18，231，234，53*，256，378，897}，可知max=3，min=1，root大小為3即為root[1..3]，len=3，樹的深度為5。對應(yīng)的排序樹如圖1所示。

具體算法描述如下：

定義三類結(jié)點(diǎn)①根結(jié)點(diǎn)root：為一基類型為指針類型的活動數(shù)組；②中間結(jié)點(diǎn)branch：為一基類型為指針類型大小為10的數(shù)組，③葉子結(jié)點(diǎn)leaf：為一待排數(shù)據(jù)類型(可以增加一個指針用來指向其同義詞結(jié)點(diǎn))。

step1：找到待排數(shù)據(jù)中值最大數(shù)的十進(jìn)制階碼放入max中，最小數(shù)的十進(jìn)制階碼放min中，規(guī)格化十進(jìn)制尾數(shù)位數(shù)最長值放len中；

step2：申請根結(jié)點(diǎn)root[min．．max]，其中每個元素初始化為空指針；

step3：如果待排隊(duì)列為空轉(zhuǎn)step5：，否則： 從待排數(shù)據(jù)中取出一個數(shù)據(jù)按下面方法插入到排序樹中： (1)取出此數(shù)十進(jìn)制階碼放入exp，尾數(shù)部分放tail中；所在層數(shù)depth=0；

(2)如果root[exp]為非空則轉(zhuǎn)step4，否則；

(3)申請一枝結(jié)點(diǎn)banch，初始化為空，并由工作指針P和root[exp]指向它；depth加1；

(4)如果depth小于len繼續(xù)，否則轉(zhuǎn)(8)；

(5)取尾數(shù)tail的第depth位置于f中；

(6)如果P所指結(jié)點(diǎn)的第f位為非空，則P指向P[f]，depth加1轉(zhuǎn)(4)否則；

(7)申請一枝結(jié)點(diǎn)banch，并由P[f]指向它，P指向當(dāng)前新結(jié)點(diǎn)，depth加1，轉(zhuǎn)(4)；

(8)取尾數(shù)tail的第len位置于f中；

(9)申請一葉子結(jié)點(diǎn)將待排數(shù)據(jù)元素放入，并由P[f]指向它，轉(zhuǎn)step3；

step4：工作指針P指向root[exp]所指結(jié)點(diǎn)，depth加1，轉(zhuǎn)(4)。

step5：按從左到右逐一打印輸出葉子結(jié)點(diǎn)即為已經(jīng)排好序的有序序列。

算法結(jié)束。

2 算法分析

時間 本算法關(guān)鍵在于建樹，從算法中可以看出建樹的時間復(fù)雜度為O(1en*n)。對于一組待排數(shù)據(jù)，其中數(shù)據(jù)的最大位數(shù)必將是一個定值常量，所以其時間復(fù)雜度為O(n)。

空間 本算法輔助空間為根結(jié)點(diǎn)和分支結(jié)點(diǎn)所用的空間，最好情況為每一個中間結(jié)點(diǎn)都是充滿的，即都有10個子結(jié)點(diǎn)，可以推算出如果有n個待排數(shù)據(jù)輔助結(jié)點(diǎn)個數(shù)為((1/(max-min+1)-1/9)／10len+1/9)n，對于給定的數(shù)max，min，len均為常量，所以空間復(fù)雜度為O(n)；最壞情況每個葉子從根結(jié)點(diǎn)起為單枝子樹，那么n個待排數(shù)據(jù)共需1+len*n，空間復(fù)雜度仍然為O(n)。所以空間復(fù)雜度也是O(n)。

3 結(jié)束語

此算法是基于待排關(guān)鍵字本身的一種非比較類的排序方法，它融合了桶排序、基數(shù)排序和B樹的排序思想，克服了桶排序中關(guān)鍵字的類型是有限類型，克服了基數(shù)排序中關(guān)鍵字不能太大，也克服了B樹中需基于比較增加了時間復(fù)雜性。是一種穩(wěn)定的線性時間復(fù)雜度和線性空間復(fù)雜度的內(nèi)排序方法。