基数排序 Radix Sort 与 JS实现

一些概念

• 该算法是稳定的排序法；
• 在所有的情况下，时间复杂度均为O(nlog(p)k)，空间复杂度为O(n*p)
  （其中K为关键词位数，p为数据字符数(即基数radix)）；
• 若n很大，p固定或很小，此方法将很有效。
• 基数排序不需要进行元素间的比较，属于分配/分布排序；
• 根据起始方向可分为 最高位优先 MSD 和 最低位优先 LSD

使用JS实现了一下，大概是结合若干队列，使用LSD的方式，从低位到高位遍历排序，最后返回排序结果；

var getNum = function(num,n){//获取num在指定位置的数值
  return Math.floor(num/Math.pow(10,n))%10;
}
var getMaxLength = function(nums){//获取最大数位（不考虑小数
  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(){
  //栈的实现（略）
};
var radix_sort = function(arr){
  var i, j, max_length = getMaxLength(arr), queues = [];

  //初始化排序队列
  for(i=0;i<10;i++){
    queues[i] = new Queue();
  }

  //打印未排序数据
  console.log('Before sorting:');
  console.log(arr);
  
  //使用LSD模式遍历排序各数位
  for(i=0;i<max_length;i++){
    //数据按位分配
    for(j=0;j<arr.length;j++){
      queues[getNum(arr[j],i)].enqueue(arr[j]);
    }
    //更新某一位排序后的数据
    arr = [];
    for(j=0;j<10;j++){
      while(!queues[j].isEmpty()){
        arr.push(queues[j].dequeue());
      }
    }
    //打印某一位排序后的数据
    console.log('sorting '+ i + ' :');
    console.log(arr);
  }
  return arr;
}

测试数据:

var arr = [91, 46, 85, 15, 92, 35, 31, 22];
sort(arr);

测试结果:

---

2017.04.12
复习后更新一个版本

function radixSort(arr,n,radix){
    if(!radix){//默认为十进制
        radix = 10;
    }
    if(!n){//如果未指定关键词位数将自动使用首个元素的位数作为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);//获取某位数值
            //这里这个转换只能搞得动十进制= =其他就会有问题 因为不能直接用其他进制来进行运算 所以考虑使用字符串处理
            queues[num].push(tmp);
        }
        console.log('round '+i+' with queues : '+queues);
        for(j=0;j<radix;j++){//重构q
            while(queues[j].length>0){
                q.push(queues[j].shift());
            }
        }
        console.log('round '+i+' q sorted : '+q);
    }
    return q;
}

测试结果：

三位数排序测试结果