本文共 1164 字，大约阅读时间需要 3 分钟。

计数排序是一种非基于比较的排序算法，前七个排序算法都是基于比较的。

计数排序思路很简单，就是先找出一个数组中最大的数，然后创建一个最大下标为该数的空数组，然后把其他元素的出现次数放进去，然后再遍历即可。

计数排序的计数就是指的是对数组中元素出现的次数进行排序。

如果数组中最小的数小于0，那么就得使用偏移量来使其落到非负数区域

这个方法的时间复杂度可以达到O(n),但是空间复杂度却相当的高，空间复杂度为O(max - min)

package Sort;public class CountSort {    public static void countSort(int[] array){        int minValue = Integer.MAX_VALUE, maxValue = Integer.MIN_VALUE;        for(int i = 0; i < array.length; i++){            minValue = minValue < array[i]?minValue:array[i];            maxValue = maxValue > array[i]?maxValue:array[i];        }        int pos = 0;//偏移量        pos = minValue < 0?Math.abs(minValue):-minValue;        int[] count = new int[maxValue - minValue + 1];        for(int i = 0; i < array.length; i++){            count[array[i] + pos]++;        }        int index = 0;//将排完序的数组放回原数组的下标        for(int i = 0; i < count.length; i++){            int cnt = count[i];            while(cnt > 0){                array[index++] = i - pos;                cnt--;            }        }    }    public static void main(String[] args){        int[] array = {1,9,2,-33,4,122,1222,2};        countSort(array);        ArrayPrint.arrayPrint(array);    }}

转载地址：http://aizji.baihongyu.com/