一些概念
- 該算法是穩(wěn)定的排序法抄淑；
- 在所有的情況下觉至，時間復(fù)雜度均為O(nlog(p)k)，空間復(fù)雜度為O(n*p)
（其中K為關(guān)鍵詞位數(shù)助赞，p為數(shù)據(jù)字符數(shù)(即基數(shù)radix)）； - 若n很大袁勺，p固定或很小雹食，此方法將很有效。
- 基數(shù)排序不需要進行元素間的比較期丰，屬于分配/分布排序群叶；
- 根據(jù)起始方向可分為 最高位優(yōu)先 MSD 和 最低位優(yōu)先 LSD
使用JS實現(xiàn)了一下，大概是結(jié)合若干隊列钝荡，使用LSD的方式街立，從低位到高位遍歷排序，最后返回排序結(jié)果埠通；
var getNum = function(num,n){//獲取num在指定位置的數(shù)值
return Math.floor(num/Math.pow(10,n))%10;
}
var getMaxLength = function(nums){//獲取最大數(shù)位（不考慮小數(shù)
var i, max = 0;
for(i=0;i<nums.length;i++){
if(nums[i].toString().length > max){
max = nums[i].toString().length;
}
}
return max;
};
var Queue = function(){
//棧的實現(xiàn)（略）
};
var radix_sort = function(arr){
var i, j, max_length = getMaxLength(arr), queues = [];
//初始化排序隊列
for(i=0;i<10;i++){
queues[i] = new Queue();
}
//打印未排序數(shù)據(jù)
console.log('Before sorting:');
console.log(arr);
//使用LSD模式遍歷排序各數(shù)位
for(i=0;i<max_length;i++){
//數(shù)據(jù)按位分配
for(j=0;j<arr.length;j++){
queues[getNum(arr[j],i)].enqueue(arr[j]);
}
//更新某一位排序后的數(shù)據(jù)
arr = [];
for(j=0;j<10;j++){
while(!queues[j].isEmpty()){
arr.push(queues[j].dequeue());
}
}
//打印某一位排序后的數(shù)據(jù)
console.log('sorting '+ i + ' :');
console.log(arr);
}
return arr;
}
測試數(shù)據(jù):
var arr = [91, 46, 85, 15, 92, 35, 31, 22];
sort(arr);
測試結(jié)果:
2017.04.12
復(fù)習(xí)后更新一個版本
function radixSort(arr,n,radix){
if(!radix){//默認(rèn)為十進制
radix = 10;
}
if(!n){//如果未指定關(guān)鍵詞位數(shù)將自動使用首個元素的位數(shù)作為n
n = arr[0].toString().length;
console.log('auto n : '+n);
}
var i,j,tmp,num,queues=[],q=arr.slice();
for(i=0;i<radix;i++){
queues.push([]);//生成Q[0]~Q[radix-1]
}
for(i=0;i<n;i++){//LSD低位起始
while(q.length>0){
tmp = q.shift();
num = Math.floor(tmp/Math.pow(radix,i)%radix);//獲取某位數(shù)值
//這里這個轉(zhuǎn)換只能搞得動十進制= =其他就會有問題 因為不能直接用其他進制來進行運算 所以考慮使用字符串處理
queues[num].push(tmp);
}
console.log('round '+i+' with queues : '+queues);
for(j=0;j<radix;j++){//重構(gòu)q
while(queues[j].length>0){
q.push(queues[j].shift());
}
}
console.log('round '+i+' q sorted : '+q);
}
return q;
}
測試結(jié)果：
三位數(shù)排序測試結(jié)果
