一種線性時間排序算法的實現

摘要：提出一種不依賴關鍵字的分布，數據位數不受限制的整型或實型數的內部排序算法，其時間和空間復雜度均為O(n)。給出了算法思想和算法分析結果。

關鍵詞：排序；算法；有序樹；復雜性

0 引言

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

1 算法思想

假定待排數據為大于0的實型數且放在數組A中。排序的主要工作是創建一棵有序樹。首先找到這組數中值最大和最小的數以確定樹根結點的大小，根結點為一指針類型的數組root，假定最大數的十進制階碼為max，最小數的十進制階碼為min，那么root數組大小為max-min+1即root[min..max]，root[O]指向10₀的子樹根結點，root[1]指向10₁的子樹根結點……root[n]指向10₀的子樹根結點，中間分支結點為一大小為10的指針數組B[10]。如果把根結點所在的一層約定為第0層，那么第1層中B1[0]指向尾數中第1位值為0的子樹根結點，B1[1]指向尾數中第1位值為1的子樹根結點……B1[9]指向尾數中第1位值為9的子樹根結點；第2層中B2[0]指向尾數中第2位值為0的子樹根結點，B2[1]指向尾數中第2位值為l的子樹根結點……B2[9]指向尾數中第2位值為9的子樹根結點；……待排數據均放在葉子結點上，葉子結點類型為待排數據類型的單鏈表，數的深度取決于待排數據中尾數的最大長度len，所有葉子結點都在第len+1層。將數組A中所有的數據都插入上述樹中，然后將葉子結點按從左到右輸出即為—個已經排好序的有序序列。例如待排數據為{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。對應的排序樹如圖1所示。

具體算法描述如下：

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

step1：找到待排數據中值最大數的十進制階碼放入max中，最小數的十進制階碼放min中，規格化十進制尾數位數最長值放len中；

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

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

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

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

(4)如果depth小于len繼續，否則轉(8)；

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

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

(7)申請一枝結點banch，并由P[f]指向它，P指向當前新結點，depth加1，轉(4)；

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

(9)申請一葉子結點將待排數據元素放入，并由P[f]指向它，轉step3；

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

step5：按從左到右逐一打印輸出葉子結點即為已經排好序的有序序列。

算法結束。

2 算法分析

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

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

3 結束語

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