##概述

计数排序是一个非基于比较的排序算法,它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序） 1.非基于比较的排序 2.是以空间换取时间的做法 3.它的排序效率是线性的，在特定的场景下（已知数组的最大最小值，且数组元素整体量不是很大的情况下）排序效率极高，复杂度为Ο(n+k)（其中k是整数的范围）。当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序。

##基本原理

通俗一点讲就是将原数组的元素值等于新数组的下标，元素值重复一次，下标+1。从而得到元素值重复的次数。再借助数组下标有序的特性，循环遍历后，完成数组的排序。 比如说创建辅助数组 b，等于目标数组 a，对于 a 中的每个元素 a[i]，将其出现的次数映射到 b[j] 中，其中有 j（b的下标） = a[i]（a的元素值）。

##简单实现

 public static void  simpleCountSort(){ 
        //假设排序的数组为{2,1,0,1}
        int nums[]={2,1,0,1};  
  
        int maxNum=2;  
  
        int storeArray[]=new int[maxNum+1];  
         
        //词频计数  
        for(int i=0;i<nums.length;i++){  
            //num[i]：原数组中的元素值
            //storeArray[nums[i]]：元素值作为词频数组下标
            //storeArray[nums[i]]++：将该下标存储的元素值+1
            storeArray[nums[i]]++;  
        }  
  
        System.out.println("==============排序后==============");  
  
        int ndx=0;  
        //遍历计数后的词频数组  
        for (int i = 0; i <storeArray.length ; i++) {  
            //对于每个index的值进行循环，输出，因为有可能重复  
            while (storeArray[i]>0){  
                nums[ndx]=i;//把词频数组的值，放回原数组里面，  
                ndx++;//替换一个数，就索引自增  
                storeArray[i]--;//词频减1，进入下一轮循环
            }  
        }  
        System.out.println(Arrays.toString(nums));  
    }

##优化版本 上面的代码具有以下缺点： 当元素的值域比较接近，比如数组{99，90，91,93,94，99,98,94，97,98}，其中最小值为90，最大值为99，按照上面的思路，必须新建一个长度为100的数组，然而该数组只使用了最后的十个索引，造成空间上极大的浪费。

实现步骤： 1，找出数组里面的最大值和最小值

2，求出每个元素出现的词频（count）

3，遍历词频数组求和

4，反向遍历原始数组，进行目标数组填充，填充后的数组再遍历就是有序的。

未完待续。