不积跬步之计数排序

之前的排序都是通过比较来完成的，例如冒泡排序和快速排序。

两个值比较，如果大的值，就交换。

而计数排序则是利用里字典表的原理。我现在已经有了一个字典表。比如是这样的：

{
    0:0,
    1:0,
    2:0,
    3:0,
    4:0,
    5:0,
    6:0.
    7:0,
    8:0,
    9:0
}

假设你的数组里的最大值是9，区间就是0~9。
遍历每一个值，如果值存在，那么就给它对应的value +1 .

而我们实际则使用了数组来完成的这个工作。
数组它天生的有序。角标就是实际它的值。而它对应的值则是它出现的次数。

只要我们有了这个样一个数组，遍历出来它就可以了。

//计数排序
/*
*
* 计数排序的原理：
* 1.假定该数组都是整数，
* 2.按照给定的数组，生成一个数组字典，利用数组下表为字典，来存储给定数组出现的次数。出现一次就加1
* 3.遍历数组字典，依据下定对应的值，来输出。
* */
function CountSort(array){
    //2.首先找到数组的最大值
    let max = 0;
    for(let i = 0;i<array.length ;i++){
            if(array[i] > max){
                    max = array[i];
            }
    }
    //2.依据最大值生成数组
    let array_map = [];
    array_map.length = max+1;
    array_map.fill(0);
    
    //3.填充数组---利用array它的实际的值作为角标。
    for(let i = 0;i<array.length;i++){
            array_map[array[i]]++;
    }
    let sortArray = [];
    let index = 0;
    //4.遍历统计的数据，输出结果
    for(let i = 0;i<array_map.length;i++){
         //i 其实就是 我们数组字典对应的它实际的值
          for(let j = 0;j<array_map[i];j++){
                  sortArray[index++] = i;
          }
    }
    return sortArray;
}

const data = [0,0,0,99,29,33,4,7,8,19,99,5];
console.log(CountSort(data))

当然这样做限制很大。

我们不知道它的最大值和最小值之间的查是多少，假如是1000和995，他们的差值只有5个，而我们却要建立一个1000位的数组。

还有就是数组如果重复的时候，排序出来我们不知道它是什么顺序。

针对其中的问题，我们优化一版：

//计数排序
function CountSort1(array){
        //1.得到数组的最大值和最小值
        let max = array[0];
        let min = array[0];
        for(let i = 1;i<array.length;i++){
                if(array[i] > max){
                   max = array[i];
                }
                if(array[i] < min){
                    min = array[i];
                }
        }
        //2.创建统计数组并统计对应元素的个数
        let diff = max - min;
        let countArray = [];
        countArray.length = diff+1;
        countArray.fill(0);
        
        for (let i = 0;i<array.length;i++){
                //只计数差值的值--因为我们就是按照差值来填充的数组字典
                countArray[array[i]-min]++;
        }
        
        //3.统计数组做变性，后面的元素等于前面的元素之和
        for(let i= 1;i<countArray.length;i++){
                countArray[i]+=countArray[i-1];
        }
        
        //4.倒序遍历原始数列，从统计数组找到正确的位置，输出到结果数组。
        let sortedArray = [];
        sortedArray.length = array.length;
        for(let i = array.length-1;i>=0;i--){
                sortedArray[countArray[array[i]-min]-1] = array[i];
                countArray[array[i]-min]--;
        }
        return sortedArray;
}

const data = [99,98,99,97,94,96,93];
console.log(CountSort1(data))