非比较排序(计数排序、基数排序、桶排序)

1.桶排序第一步：确定这个序列要分为几个桶第二步：把每个元素放到对应的桶里面第三步：对每个桶进行排序第四步：对所有的桶进行整合

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 = new Array(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;
}

2.计数排序：利用数组的index是天然有序的特征来排序. 例如: 已知一个乱序数组的范围是0~10,长度未知, 我们只需要遍历一遍数组,点出每个值出现的次数,并用一个新数组来存储这个次数,就能做到排序. 假如数字1出现3次, 那么新数组newAry[1]=3, 在新数组遍历的时候输出3次"1"（很像哈希）

    function countSort(ary) {
        let newAry = new Array(ary.length).fill(0);
        for (const value of ary) {
            newAry[value]++;
        }
        ary = [];
        // 给ary重新赋值
        for(var i =0; i<newAry.length; i++) {
            // 循环数字次数
            for(var k = newAry[i]; k>0; k--) {
                ary.push(i);
            }
        }
        newAry = null;
        return ary;
    }

3.基数排序:是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

const radixSort = (arr) => {
    let length = arr.length
    if (length <= 1) {
        return arr
    }
    let maxDigit = String(parseInt(Math.max(...arr))).length // 取最大位数
    let mod = 10;
    let dev = 1;
    let counter = []
    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev);
            counter[bucket] = counter[bucket] == null ? [] : counter[bucket]
            counter[bucket].push(arr[j]);
        }
        let pos = 0;
        for(let j = 0; j < counter.length; j++) {
            let value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                    arr[pos++] = value;
                }
            }
        }
    }
    return arr;
}