热门问题
时间线
聊天
视角
基數排序
来自维基百科,自由的百科全书
Remove ads
基數排序(英語:Radix sort)是一種非比較型整數排序演算法,其原理是將整數按位元數切割成不同的數字,然後按每個位數分別比較。由於整數也可以表達字串(比如名字或日期)和特定格式的浮點數,所以基數排序也不是只能使用於整數。
![]() | 此條目可參照外語維基百科相應條目來擴充。 |
它是這樣實現的:將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零。然後,從最低位開始,依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後,數列就變成一個有序序列。
基數排序的方式可以採用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由鍵值的最右邊開始,而MSD則相反,由鍵值的最左邊開始。
Remove ads
歷史
基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片製表機上的貢獻[1]。基數排序演算法早在1923年被廣泛運用在打孔卡的排序[2]。
效率
基數排序的時間複雜度是,其中是排序元素個數,是數字位數。注意這不是說這個時間複雜度一定優於,的大小取決於數字位的選擇(比如位元位數),和待排序資料所屬資料類型的全集的大小;決定了進行多少輪處理,而是每輪處理的運算元目。
以排序個不同整數來舉例,假定這些整數以為底,這樣每位數都有個不同的數字,,是待排序資料類型全集的勢。雖然有個不同的數字,需要個不同的桶,但在每一輪處理中,判斷每個待排序資料項只需要一次計算確定對應數位的值,因此在每一輪處理的時候都需要平均次操作來把整數放到合適的桶中去,所以就有:
所以,基數排序的平均時間就是:
其中前一項是一個與輸入資料無關的常數,當然該項不一定小於。
如果考慮和比較排序進行對照,基數排序的形式複雜度雖然不一定更小,但由於不進行比較,因此其基本操作的代價較小,而且在適當選擇的之下,一般不大於,所以基數排序一般要快過基於比較的排序,比如快速排序。
Remove ads
參考文獻
外部連結
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads