计数排序

排序算法有很多，包括插入排序，冒泡排序，堆排序，归并排序，选择排序，计数排序，基数排序，桶排序，快速排序等。插入排序，堆排序，选择排序，归并排序和快速排序，冒泡排序都是比较排序，它们通过对数组中的元素进行比较来实现排序，其他排序算法则是利用非比较的其他方法来获得有关输入数组的排序信息。

计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

详解

计数排序就相当于你给东西归类，假如你拿了几本书，几根????，几块橡皮，你所有东西放在一起，放在一个你看不见但是能摸到的地方。你随手一模，一块橡皮，就给橡皮数加一，摸到一本书就给书数加1，直到你摸完，你就知道有几本书，几根????，几块橡皮。这就是计数排序，角标是他的数字，数组里存的数就是他的个数。
但是计数排序你不能保证他的所有数字都是正数，所以一般数组的大小等于最大值减最小值。比较占内存。
就比如说这个数据：8，5，9，2，7，4，6，1，3，10，-3，-2，-10.

角标零就等于-10，依次计算，这就是计数排序。
如果这个角标上有值那就给角标对应的数字++。
下面是Java代码：

class Test02{
    public static void main(String[] args){
     
        countSort();

    }
    public static void countSort(){
        int[] arr={8,5,9,2,7,4,6,1,3,10,-3,-2,-10};
        int min=arr[0];
        int max=arr[0];
        for(int i=0;i<arr.length;i++){//O(n)
            if(arr[i]>max){
                max=arr[i];
            }
            if(arr[i]<min){
                min=arr[i];
            }
        }
        int[] nums=new int[max-min+1];
        int offset=min;
        for(int i=0;i<arr.length;i++){//O(n)
            nums[arr[i]-offset]++;
        }
        int index=0;
        for(int i=0;i<nums.length;i++){//O(m)
            if(nums[i]!=0){
                for(int j=0;j<nums[i];j++){
                    arr[index++]=i+offset;
                }
            }
        }
        show(arr);
    }
    public static void show(int[] arr){
        //[1,2,3,4,5,6,7,8,9]
        String s="[";
        for(int i=0;i<arr.length;i++){
            if(i==arr.length-1){
                s+=arr[i]+"]";
            }else{
                s+=arr[i]+",";
            }
        }
        System.out.println(s);
    }
}

时间复杂度

它的复杂度为Ο(n+k)（其中k是整数的范围）