基数排序，计数排序和桶排序，代码实现，复杂度

[xszi]

基数排序与计数排序、桶排序这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

1. 基数排序 —— 基于非比较排序

可以采用两种模式

• LSD (Least sgnificant digital)
• MSD (Most sgnificant digital)

用PPT画了个图（LSD模式）加深理解，真心不容易啊，虽然丑但一定要贴出来^_^

再来看一下大神的动图效果：

代码实现

function radixSort(arr) {
    // 先获取数组最大值
    var maxDigit = arr[0]
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] > maxDigit) {
            maxDigit = arr[i]
        }
    }
    var mod = 10; // 进制
    var dev = 1; // 
    var counter = []
    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数组
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        // 第一次根据个位数顺序输出arr
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j] != null) {
                while((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
            }
        }
        // 紧接着在十位数上重复该动作
    }
    return arr;
}

算法复杂度

时间复杂度： *O(d(n+k)) (d是最大值的位数，k是进制) 空间复杂度：O(k + N)**

2. 计数排序

计数排序也是一种非基于比较的排序算法，其空间复杂度和时间复杂度均为O(n+k)，其中k是整数的范围。基于比较的排序算法时间复杂度最小是O(nlogn)的。该算法于1954年由 Harold H. Seward 提出。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤

• 花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max

• 开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)

• 数组 B 中 index 的元素记录的值是 A 中某元素出现的次数

• 最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

代码实现

function countingSort(arr) {
    // 先获取数组最大值
    var maxValue = arr[0]
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] > maxValue) {
            maxValue = arr[i]
        }
    }
    var bucket = newArray(maxValue + 1),
        sortedIndex = 0;
        arrLen = arr.length,
        bucketLen = maxValue + 1;

    for(var i = 0; i < arrLen; i++) {
        if(!bucket[arr[i]]) {
            bucket[arr[i]] = 0;
        }
        bucket[arr[i]]++;
    }

    for(var j = 0; j < bucketLen; j++) {
        while(bucket[j] > 0) {
            arr[sortedIndex++] = j;
            bucket[j]--;
        }
    }

    return arr;
}

算法复杂度

时间复杂度：O(n+k) 空间复杂度：O(n+k)

3. 桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

算法描述

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

动画演示：

代码实现

function bucketSort(arr, bucketSize) {
    if(arr.length === 0) {
        return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for(i = 1; i < arr.length; i++) {
        if(arr[i] < minValue) {
            minValue = arr[i];               // 输入数据的最小值
        }else if(arr[i] > maxValue) {
            maxValue = arr[i];               // 输入数据的最大值
        }
    }

    // 桶的初始化
    var DEFAULT_BUCKET_SIZE = 5;           // 设置桶的默认数量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = newArray(bucketCount);
    for(i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    // 利用映射函数将数据分配到各个桶中
    for(i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for(i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);                     // 对每个桶进行排序，这里使用了插入排序
        for(var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                     
        }
    }

    return arr;
}

算法复杂度

时间复杂度：O(n) 空间复杂度：O(n+m) m代表桶的个数

排序算法之桶排序的深入理解以及性能分析