算法简介

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法描述

具体算法描述如下：

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

代码实现

复制
1/**
2 * 基数排序适用于：
3 *  (1)数据范围较小，建议在小于1000
4 *  (2)每个数值都要大于等于0
5 * @author damonare
6 * @param  arr 待排序数组
7 * @param  maxDigit 最大位数
8 */
9//LSD Radix Sort
10
11function radixSort(arr, maxDigit) {
12    var mod = 10;
13    var dev = 1;
14    var counter = [];
15    console.time('基数排序耗时');
16    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
17        for(var j = 0; j < arr.length; j++) {
18            var bucket = parseInt((arr[j] % mod) / dev);
19            if(counter[bucket]== null) {
20                counter[bucket] = [];
21            }
22            counter[bucket].push(arr[j]);
23        }
24        var pos = 0;
25        for(var j = 0; j < counter.length; j++) {
26            var value = null;
27            if(counter[j]!=null) {
28                while ((value = counter[j].shift()) != null) {
29                      arr[pos++] = value;
30                }
31          }
32        }
33    }
34    console.timeEnd('基数排序耗时');
35    return arr;
36}
37var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
38console.log(radixSort(arr,2)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
39

算法分析

• 最佳情况：T(n) = O(n * k)
• 最差情况：T(n) = O(n * k)
• 平均情况：T(n) = O(n * k)