计算排序算法

影-死神

一. 计数排序算法基本思路
                1. 遍历数组，找出最大值maxValue和最小值minValue，新建一个长度为maxValue-minValue+1的数组，并初始化为0
                2. 遍历数组，每个整数按照其值，对应新数组的下标（value-minvalue）加一
                3. 遍历新数组，每次输出新数组的下标值加minValue的值到原数组以更新原数组，对应的值是几就输出几次
        算法的时间复杂度：
                由于遍历了两遍原数组和一遍新数组，所以时间复杂度为 O(2N+M) = O(n)
        算法的空间复杂度：
                由于新建了一个数组，所以空间复杂度为 O(N+M) = O(n)
        Java代码实现：

public class CountSort {
        public static void sort(int[] array) {
                int minValue = array[0];
                int maxValue = array[0];
               
                //遍历数组寻找最大值和最小值
                for (int i=1;i<array.length;i++) {
                        if (array < minValue) {
                                minValue = array;
                        }
                        if (array > maxValue) {
                                maxValue = array;
                        }
                }
               
                //新的数组并计数
                int[] countList = new int[maxValue-minValue+1];
               
                for (int i=0;i<array.length;i++) {
                        countList[array-minValue]++;
                }
               
                //输出到原数组
                int index = 0;
                for (int i=0;i<countList.length;i++) {
                        for (int j=0;j<countList;j++) {
                                array[index] = minValue + i;
                                index++;
                        }
                }
        }
       
        public static void main(String[] args) {
                int[] list = {5, 8, 6, 3, 9, 2, 1, 7, 4};
               
                sort(list);
               
                for (int i=0;i<list.length;i++) {
                        System.out.print(list + " ");
                }
        }
}

二. 计数排序的适用场景
        由于计数排序是根据下标进行排序的所以只能排序整数，而如果最大值和最小值之间的差值太大时，又过于浪费内存空间，所以适用于一定范围内差值不太大的整数的排序，此时，排序速度甚至超过快速排序。