计数排序

算法原理

计数排序假设输入的元素都是0 到 k 之间的整数。计数排序的思想是对每一个输入元素 x，确定出小于 x 的元素个数，有了这一信息，就可以把 x 直接放在它在最终输出数组的位置上，例如，如果有 17 个元素小于 x，则 x 就是属于第 18 个输出位置。计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

比较计数排序

针对排序列表中的每一个元素，算出列表中小于该元素的元素个数，并把结果记录在一张表中。这个“个数”指出了该元素在有序列表中的位置。假如一个列表 A 中有一个元素为 10，而小于 10 的元素个数有 5 个，那么 10 应该排在第六个位置上，也就是 A[5]（下标从 0 开始）。这个算法称为比较计数排序。

下面举个例子来说明，待排序数组为 array[6]=8：

1.建数组 countArray[6]用于计数，并初始化数组元素为 0:

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	0	0	0	0	0	0

2.进行第 1 轮比较，i = 0, for (j = i + 1; j < array.length; ++j)，如果 array[i] (值为7) >= array[j]，countArray[i]++，如果 array[i] < array[j]，countArray[j]++

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	3	1	0	0	0	1

3.进行第 2 轮比较，i = 1, for (j = i + 1; j < array.length; ++j)，如果 array[i] (值为9) >= array[j]，countArray[i]++，如果 array[i] < array[j]，countArray[j]++

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	3	5	0	0	0	1

4.进行第 3 轮比较，i = 2, for (j = i + 1; j < array.length; ++j)，如果 array[i] (值为4) >= array[j]，countArray[i]++，如果 array[i] < array[j]，countArray[j]++

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	3	5	2	0	0	2

5.进行第 4 轮比较，i = 3, for (j = i + 1; j < array.length; ++j)，如果 array[i] (值为2) >= array[j]，countArray[i]++，如果 array[i] < array[j]，countArray[j]++

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	3	5	2	1	0	3

6.进行第 5 轮比较，i = 4, for (j = i + 1; j < array.length; ++j)，如果 array[i] (值为1) >= array[j]，countArray[i]++，如果 array[i] < array[j]，countArray[j]++

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	3	5	2	1	0	4

7.最终状态

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	3	5	2	1	0	4

8.用一个数组 tempArray[0……5]通过**tempArray[ countArray[i] ] = array[i]**存放数组 A 的值。

索引	0	1	2	3	4	5
array 数组	7	9	4	2	1	8
countArray 数组	3	5	2	1	0	4
tempArray 数组	1	2	4	7	8	9

9.for(i = 0; i < array.length; ++i) array[i] = tempArray[i];排序完成

分布计数排序

排序步骤： 1.设被排序的数组为 array，tempArray 为临时数组。 2.首先通过一个数组 countArray[i]计算大小等于 i 的元素个数，此过程只需要一次循环遍历就可以； 3.在此基础上，计算小于或者等于 i 的元素个数，也是一重循环就完成。 4.逆序循环，从 array.length到 1，将 A[i]放到第 countArray[array[i]]个位置上 原理是：countArray[array[i]]表示小于等于 array[i]的元素个数，正好是 array[i]排序后应该在的位置。而且从 array.length到 1 逆序循环，可以保证相同元素间的相对顺序不变，这也是计数排序稳定性的体现。

下面举例说明： 数组如 array[9] = 6，创建一个临时数组 countArray[k]这样的一个数组，k 表示数组 array 中的元素必须都在 0-k 之间，对于这个数组 k 为 9。通过数组 countArray 下标来记录我们需要排序的数组 array 中的元素，然后只要输出记录了这些的下标就好了。如果针对没有重复的序列，很容易可以得到这样的排好序的序列如：array[8]=9

下标	0	1	2	3	4	5	6	7	8	9
countArray 数组	1	0	1	1	1	1	1	1	0	1
取下标排序后	0		2	3	4	5	6	7		9

针对有重复的情况，只需要记录有几个重复，在上表中的第二行就是用来解决这个问题的，我们可用来记录有几次重复，从而达到彻底的解决这排序的问题。如未排序数组：array[11] = 0

下标	0	1	2	3	4	5	6	7	8	9
countArray 数组	1	0	2	1	1	2	2	1	0	1
取下标排序后	0		2	3	4	5	6	7		9

排序后得到数组为 array[11] = 9

计数排序动图展示

代码

/**
 * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
 */
public interface Sorter<T extends Comparable<T>> {

    /**
     * 排序
     *
     * @param array 待排序的数组
     */
    default void sort(T[] array) {
    }
}

public class CountSorter<T extends Comparable<T>> implements Sorter<T> {
    public void sort(T[] array) {
        int length = array.length;

        T maxValue = getMax(array);
        //数组里所有的数字都小于range
        int range = Integer.parseInt(maxValue.toString());
        int[] countArray = new int[range + 1];

        //统计每个数组元素array[i]在数组中出现的个数
        for (int i = 0; i < length; ++i) {
            int value = Integer.parseInt(array[i].toString());
            ++countArray[value];
        }

        //通过在countArray中记录计数和，countArray中存放的是小于等于i元素的数字个数
        for (int i = 1; i < countArray.length; ++i) {
            countArray[i] += countArray[i - 1];
        }

        Object[] tempArray = new Object[length];
        // 把待排序数组中的元素放在临时数组中对应的位置上
        for (int i = length - 1; i >= 0; --i) {
            int value = Integer.parseInt(array[i].toString());
            int position = countArray[value] - 1;

            tempArray[position] = value;
            --countArray[value];
        }

        for (int i = 0; i < length; ++i) {
            array[i] = (T) tempArray[i];
        }
    }

    public T getMax(T[] array) {
        T max = array[0];
        for (int i = 0; i < array.length; ++i) {
            if (array[i].compareTo(max) > 0) {
                max = array[i];
            }
        }
        return max;
    }
}