基數排序（Radix Sort）

時間 2021-01-20 標籤算法基礎

基數排序是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序。最後的次序就是高優先級高的在前，高優先級相同的低優先級高的在前。

10.1 算法描述

取得數組中的最大數，並取得位數；
arr爲原始數組，從最低位開始取每個位組成radix數組；
對radix進行計數排序（利用計數排序適用於小範圍數的特點）；

10.2 動圖演示

10.3 代碼實現

var counter = [];

function radixSort(arr, maxDigit) {

var mod = 10;

var dev = 1;

for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

for(var j = 0; j < arr.length; j++) {

var bucket = parseInt((arr[j] % mod) / dev);

if(counter[bucket]==null) {

counter[bucket] = [];

}

counter[bucket].push(arr[j]);

}

var pos = 0;

for(var j = 0; j < counter.length; j++) {

var value =null;

if(counter[j]!=null) {

while ((value = counter[j].shift()) !=null) {

arr[pos++] = value;

}

return arr;

}

10.4 算法分析

基數排序基於分別排序，分別收集，所以是穩定的。但基數排序的性能比桶排序要略差，每一次關鍵字的桶分配都需要O(n)的時間複雜度，而且分配之後得到新的關鍵字序列又需要O(n)的時間複雜度。假如待排數據可以分爲d個關鍵字，則基數排序的時間複雜度將是O(d*2n) ，當然d要遠遠小於n，因此基本上還是線性級別的。

基數排序的空間複雜度爲O(n+k)，其中k爲桶的數量。一般來說n>>k，因此額外空間需要大概n個左右。