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

摘要：提出一種不依賴關鍵字的分布，數據位數不受限制的整型或實型數的內部排序算法，其時間和空間復雜度均為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的子樹根結點；