基數排序之算法

基數排序是一種非比較型整數排序算法，其原理是将整數按位數切割成不同的數字，然後按每個位數分别比較。由于整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，是以基數排序也不是隻能使用于整數。

一、定義

二、算法思想

基數排序：根據鍵值的每位數字來配置設定桶；

計數排序：每個桶隻存儲單一鍵值；

桶排序：每個桶存儲一定範圍的數值；

這三種排序算法都利用了桶的概念，但對桶的使用方法上有明顯差異。

三、具體實作

按照優先從高位或低位來排序有兩種實作方案:

MSD：由高位為基底，先按k1排序分組，同一組中記錄鍵碼k1相等，再對各組按k2排序分成子組，之後，對後面的關鍵碼繼續這樣的排序分組，直到按最次位關鍵碼kd對各子組排序後，再将各組連接配接起來，得到一個有序序列。MSD方式适用于位數多的序列。

LSD：由低位為基底，先從kd排序，再對kd-1進行排序，依次重複，直到對k1排序後，得到一個有序序列。LSD方式适用于位數少的序列。

四、效率分析

基數排序更适合用于對時間，字元串等這些整體權值未知的資料進行排序。基數排序不改變相同元素之間的相對順序，是以它是穩定的排序算法。

1、時間複雜度

最壞的情況：時間複雜度為O(n*k)；

最佳的情況：時間複雜度為O(n*k)；

平均來講，時間複雜度為O(n*k)。

2、空間複雜度

空間複雜度為常量O(n+k)。

部落格簽名：敬畏生命，珍惜時間，熱愛生活。