排序（2）

线性排序：Bucket sort，Counting sort，Radix sort

桶排序

1. 数据能划分为m个桶，桶之间有天然有序；
2. 数据在各个桶之间分布均匀；

计数排序

数据范围不大的非负整数排序

function countingSort(arr) {
    let min = arr[0], max = arr[0];
    arr.forEach((item) => {
        min = min < item ? min : item;
        max = max > item ? max : item;
    });
    let n = max - min + 1, countList = [];
    for (let i = 0; i < n; i++) {
        countList.push(0);
    }
    arr.forEach((item) => {
        countList[item - min]++;
    });
    let result = [];

    // 方法1: 累加，逆序求值
    for (let i = 1; i < n; i++) {
        countList[i] += countList[i-1];
    }
    for (let i = arr.length-1; i >= 0; i--) {
        let val = arr[i];
        let j = countList[val-min];
        result[j-1] = val;
        countList[val-min]--;
    }

    // 方法2: 递减取值
    // for (let i = 0; i < countList.length; i++) {
    //     while(countList[i] > 0) {
    //         result.push(i+min);
    //         countList[i]--;
    //     }
    // }
    return result;
}

基数排序

1. 有独立分割的位，高低位有递进关系；
2. 每位数据范围不可太大，要可以用线性排序。
   例：手机号码，低位到高位每位稳定排序，k位整数=k次桶排序or计数排序

function radixSort(arr) {
    let n = 0;
    arr.forEach(item => {
        let tmpLen = String(item).length;
        n = tmpLen > n ? tmpLen : n;
    });
    let bucket = [], result = [], max = n;
    while (n > 0) {
        n--;
        result = [];
        bucket = [];
        for (let i = 0; i <= 9; i++) {
            bucket[i] = [];
        }
        arr.forEach(item => {
            let val = String(item);
            let prefix = max - val.length;
            while(prefix > 0) {
                val = "0" + val;
                prefix--;
            }
            let key = val.charAt(n) || 0;
            bucket[key].push(item);
        });
        for (let i = 0; i <= 9; i++) {
            if (bucket[i].length > 0) {
                result = result.concat(bucket[i]);
            }
        }
        arr = result;
    }
    return result;
}