排序算法-基数排序

基数排序（radix sort）的基础

技术排序的定义：基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

基数排序步骤

以LSD为例，排序数组arr = [73, 22, 93, 43, 55, 14, 28, 65, 39, 81];
注：最低位优先(Least Significant Digit first)法，简称LSD法
最高位优先(Most Significant Digit first)法，简称MSD法

1. 首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中。
   以下红色字体代表桶编号
   得到：
   0
   1 81
   2 22
   3 73 93 43
   4 14
   5 55 65
   6
   7
   8 28
   9 39
   再将这些桶子中的数值重新串接起来，成为以下的数列。
   81, 22, 73, 93, 43, 14, 55, 65, 28, 39

2. 接着再进行一次分配，这次是根据十位数来分配
   0
   1 14
   2 22 28
   3 39
   4 43
   5 55
   6 65
   7 73
   8 81
   9 93
   接下来将这些桶子中的数值重新串接起来，成为以下的数列：
   14, 22, 28, 39, 43, 55, 65, 73, 81, 93
   这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。
   PS：LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

代码实现

/**
 * 基数排序适用于：
 *  (1)数据范围较小，建议在小于1000
 *  (2)每个数值都要大于等于0
 * @param  arr 待排序数组
 * @param  maxDigit 最大位数
 */
//LSD Radix Sort
function radixSort(array, maxDigit) {
	var mod = 10;
	var dev = 1;
	var counter = [];
	var arr = array.slice();
	console.time('基数排序耗时');
	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;
				}
		  }
		}
	}
	console.timeEnd('基数排序耗时');
	return arr;
}
var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
var demo = radixSort(arr,2);
console.log(arr); // [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(demo); // [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];

动图展示

参考文档：
JS的十大经典算法排序
十大经典排序算法
基数排序