博客

计数排序

**基本思想：**对于每一个待排序元素，如果知道了待排序数组中有多少个比它小的元素，那么就可以直接得出排序后该元素应该在什么位置上。


图示：





代码示例：

	
    public static void countSort(int[] array){
        //1、统计元素的范围
        int minValue = array[0];
        int maxValue = array[0];
        for(int i = 1 ;i<array.length-1;i++){
            if(array[i]>maxValue){
                maxValue = array[i];
            }
            if(array[i]<minValue){
                minValue = array[i];
            }
        }
        //2、开辟计数空间：该范围中最多包含的不同元素种类的个数
        int range = maxValue-minValue+1;
        int[] arrayCount = new int[range];

        //3、统计每个元素出现的次数
        for(int i = 0; i < array.length;i++){
            arrayCount[array[i]-minValue]++;
        }

        //4、对元素进行回收----排序
        int index = 0;
        for(int i = 0;i < range;i++){
            while(arrayCount[i]--!=0){
                array[index++] = i + minValue;
                arrayCount[i]--;
            }
        }
    }

使用场景：

数据密集集中在某个范围中

**性能：**时间复杂度：O(N)；空间复杂度：O(N) ；稳定性：稳定

桶排序

基本原理：

将数组分到有限数量的桶里，在分别对每个桶进行排序。

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

1. 在额外空间充足的情况下，尽量增大桶的数量

2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
   
   同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

3. 什么时候最快？
   
   当输入的数据可以均匀的分配到每一个桶中。

4. 什么时候最慢？
   
   当输入的数据被分配到了同一个桶中。

图示：