基數排序
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目可參照外語維基百科相應條目來擴充。 |
基數排序 | |
---|---|
![]() | |
概況 | |
類別 | 排序演算法 |
資料結構 | 陣列 |
複雜度 | |
最壞時間複雜度 | |
空間複雜度 | |
最佳解 | Yes |
相關變數的定義 |
基數排序(英語:Radix sort)是一種非比較型整數排序演算法,其原理是將整數按位元數切割成不同的數字,然後按每個位數分別比較。由於整數也可以表達字串(比如名字或日期)和特定格式的浮點數,所以基數排序也不是只能使用於整數。
它是這樣實現的:將所有待比較數值(正整數)統一為同樣的數碼長度,數碼較短的數前面補零。然後,從最低位開始,依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。
基數排序的方式可以採用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始。
歷史
基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片製表機上的貢獻[1]。基數排序演算法早在1923年被廣泛運用在打孔卡的排序[2]。
效率
基數排序的時間複雜度是,其中是排序元素個數,是數字位數。注意這不是說這個時間複雜度一定優於,的大小取決於數字位的選擇(比如位元位數),和待排序數據所屬資料類型的全集的大小;決定了進行多少輪處理,而是每輪處理的運算元目。
以排序個不同整數來舉例,假定這些整數以為底,這樣每位數都有個不同的數字,,是待排序資料類型全集的勢。雖然有個不同的數字,需要個不同的桶,但在每一輪處理中,判斷每個待排序數據項只需要一次計算確定對應數碼的值,因此在每一輪處理的時候都需要平均次操作來把整數放到合適的桶中去,所以就有:
所以,基數排序的平均時間就是:
其中前一項是一個與輸入數據無關的常數,當然該項不一定小於。
如果考慮和比較排序進行對照,基數排序的形式複雜度雖然不一定更小,但由於不進行比較,因此其基本操作的代價較小,而且在適當選擇的之下,一般不大於,所以基數排序一般要快過基於比較的排序,比如快速排序。
參考文獻
- ^ US 395781和UK 327
- ^ 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.
外部連結
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/f/fa/Wikibooks-logo.svg/40px-Wikibooks-logo.svg.png)
|