基数排序算法

算法简介

基数排序是 1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或 bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法（稳定是指相等元素的顺序和原数组中的一直）
基数排序(Radix Sort)是桶排序的扩展

算法分析

主要思想：

比如：2，22，31，1221，90，85，105

个位排序：90，31，1221，2，22，85，105

十位排序：2，105，1221，22，31，85，90

百位排序：2，22，31，85，90，105，1221

千位排序：2，22，31，85，90，105，1221

注意：每次排序都是在上次排序的基础上进行排序的，也就是说此次排序的位数上他们相对时，就不移动元素（即顺序参数上一个位数的排序顺序）

算法步骤

  1. 把所有元素都分配到相应的桶中

  2. 把所有桶中的元素都集合起来放回到数组中

  3. 依次循环上面两步，循环次数为最大元素最高位数

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
let arr = [53, 3, 542, 748, 14, 214];
console.log('原数组：', arr)
radixSort(arr);
console.log('基数排序后：', arr)

//基数排序方法
/**
 *
 * @param {处理的数组} arr
 */
function radixSort(arr) {
    //定义一个二维数组，表示10个桶，每个桶就是一个一维数组
    //说明
    //1，二维数组包含10个一维数组，
    //2.为了防止在放入数的时候，数据溢出，则每个一维数组（桶）
    //大小定为arr.length
    //3.很明确，基数排序是使用空间换时间的经典算法
    let bucket = new Array(10);
    for (let i = 0; i < bucket.length; i++) {
        bucket[i] = new Array(arr.length);
    }

    //为了记录每个桶中，实际存了多少个数据，我们定义一个
    //一维数组来记录每个桶的每次放入的数据个数
    //可以这里理解
    //比如：bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数
    let buckeElementCounts = new Array(10).fill(0);

    //1.得到数组中最大的位数
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i]
        }
    }
    //得到最大是几位数
    let maxLength = (max + '').length;


    for (let i = 0, n = 1; i < maxLength; i++, n = n * 10) {
        //每一轮，对每个元素的各个位数进行排序处理,
        //第一次是个位，第二次是十位，第三次是百位
        for (let j = 0; j < arr.length; j++) {
            //取出每个元素的各位的值
            let digitOfElement = Math.floor(arr[j] / n) % 10;
            bucket[digitOfElement][buckeElementCounts[digitOfElement]]
                = arr[j];
            buckeElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序（以为数组的下标依次取出数据，放入原来数组）
        let index = 0;
        //遍历每一桶，并将桶中的数据，放入原数组
        for (let k = 0; k < buckeElementCounts.length; k++) {
            //如果桶中有数据，我们才放入原数组
            if (buckeElementCounts[k] !== 0) {
                //循环该桶即第k个桶，即第k个一维数组，放入
                for (let l = 0; l < buckeElementCounts[k]; l++) {
                    //取出元素放入arr
                    arr[index] = bucket[k][l];
                    //arr下标后移
                    index++;
                }
                //每轮处理后，下标要清0
                buckeElementCounts[k] = 0;
            }
        }
    }
}

复杂度

时间复杂度：O(nlog（r）m) （其中r为所采取的基数，而m为堆数）
稳定性：稳定
复杂性：较复杂