[Algorithm] Radix Sort (基數排序)
基數排序（英語：Radix sort），屬於「分配式排序」（distribution sort），是一種非比較型整數排序演算法
基數排序法會使用到「桶子」（bucket），屬於穩定性的排序（stable sort）
依比較的方向可分為 MSD (Most Significant Digit First) 和 LSD (Least Significant Digit First) 兩種。MSD 從最高有效鍵值開始排序（最大位數排到小），而 LSD 則是從最低有效鍵值開始排序（最小位數排到大）
Radix Sort 的定義 (參考維基百科)
原理是將整數按位元數切割成不同的數字，然後按每個位數分別比較。
由於整數也可以表達字串（比如名字或日期）和特定格式的浮點數
所以基數排序也不是只能使用於整數
主要步驟
取得每個資料鍵值的最 小/大 位數
依據該位數大小排序資料
取得下一個有效位數，並重複步驟二，至最 小/大 位數為止
可參考維基上動圖
時間複雜度 O(k.n)
範例程式碼
Ruby 範例
附上 Ruby 的 online sandbox，有興趣可以把 code 貼進去玩玩看
arr = 20.times.map{ rand 100 }
def radix_sort(array)
# 找出 array 裡的最大長度
max_length = Math.log(array.max(), 10).ceil
max_length.times do |j|
# 建立 buckets
buckets = (0..9).map{ [] }
array.each do |i|
# 取 i 的個位數數字，並將值塞進對應的 bucket
buckets[i.to_s[-j - 1].to_i] << i
end
# 排除空 bucket，並做排序
array = buckets.select{ |i| !i.empty? }.reduce(:+)
end
array
end
puts 'before'
puts arr.inspect
puts
puts 'after'
puts radix_sort(arr).inspect
結果如下
JavaScript 範例
JavaScript 的 online sandbox，有興趣可以把 code 貼進去玩玩看
const unsortedArr = [5, 41, 41, 56, 6, 63, 91, 69, 96, 96, 89, 32, 69, 67, 86, 52, 49, 19, 8, 91];
radixSort = arr => {
// 找出 array 裡的最大長度
const maxNum = Math.max(...arr);
for (let i = 0; i < maxNum; i++) {
// 建立 buckets
let buckets = Array.from({length:10}, () => [])
for (let j = 0; j < arr.length; j++) {
// 取 arr[j] 的個位數數字，並將值塞進對應的 bucket
buckets[getPosition(arr[j], i)].push(arr[j])
}
arr= [].concat(...buckets)
}
return arr
}
getPosition = (num, place) => Math.floor(num / Math.pow(10, place)) % 10;
console.log(radixSort(unsortedArr));
結果如下
