基數排序(英語:Radix sort)是一種非比較型整數排序演算法,其原理是將整數按位元數切割成不同的數字,然後按每個位數分別比較。由於整數也可以表達字串(比如名字或日期)和特定格式的浮點數,所以基數排序也不是只能使用於整數。

基數排序
概況
類別排序演算法
資料結構陣列
複雜度
最壞時間複雜度
空間複雜度
最佳解Yes
相關變數的定義

它是這樣實現的:將所有待比較數值(正整數)統一為同樣的數碼長度,數碼較短的數前面補零。然後,從最低位開始,依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。

基數排序的方式可以採用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始。

歷史

編輯

基數排序的發明可以追溯到1887年赫爾曼·何樂禮打孔卡片製表機英語Tabulation Machine上的貢獻[1]。基數排序演算法早在1923年被廣泛運用在打孔卡的排序[2]

效率

編輯

基數排序的時間複雜度是 ,其中 是排序元素個數, 是數字位數。注意這不是說這個時間複雜度一定優於  的大小取決於數字位的選擇(比如位元位數),和待排序數據所屬資料類型的全集的大小; 決定了進行多少輪處理,而 是每輪處理的運算元目。

以排序 個不同整數來舉例,假定這些整數以 為底,這樣每位數都有 個不同的數字,  是待排序資料類型全集的勢。雖然有 個不同的數字,需要 個不同的桶,但在每一輪處理中,判斷每個待排序數據項只需要一次計算確定對應數碼的值,因此在每一輪處理的時候都需要平均 次操作來把整數放到合適的桶中去,所以就有:

 

所以,基數排序的平均時間 就是:

 

其中前一項是一個與輸入數據無關的常數,當然該項不一定小於 

如果考慮和比較排序進行對照,基數排序的形式複雜度雖然不一定更小,但由於不進行比較,因此其基本操作的代價較小,而且在適當選擇的 之下, 一般不大於 ,所以基數排序一般要快過基於比較的排序,比如快速排序。

參考文獻

編輯
  1. ^ US 395781 UK 327 
  2. ^ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp. 168–179.

外部連結

編輯