计数排序

计数排序（百度百科）

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序，堆排序）

排序思路

1. 假设有N个数的数组Array，取值范围在（0~9）之间，所以初始化一个数组countArray大小为10（即最大值+1），然后全部初始化为0
2. 遍历Array数组填充countArray数组。就是把Array数组的值作为countArray数组的下标然后加1
3. 遍历countArray数组，把值按照顺序填回Array数组，最终输出结果即可

图示过程（菜鸟教程）

算法局限性

• 当数列中的元素不是整数的时候，不适合用计数排序
• 当数列中的元素最大值和最小值差距过大时，不适合用计数排序

代码实现

package sort;

import java.util.Arrays;

/**
 * @author god-jiang
 * @date 2020/3/6  19:36
 */
public class CountSort {
    public static int[] countSort(int[] array) {
        //求Array数组的最大值
        int max = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        //创建一个长度为max+1的countArray数组
        int[] countArray = new int[max + 1];
        //计数排序
        for (int i = 0; i < array.length; i++) {
            countArray[array[i]]++;
        }

        int index = 0;
        int[] sortedArray = new int[array.length];
        for (int i = 0; i < countArray.length; i++) {
            for (int j = 0; j < countArray[i]; j++) {
                sortedArray[index++] = i;
            }
        }
        return sortedArray;
    }

    //主函数入口
    public static void main(String[] args) {
        int[] array = new int[]{0, 2, 4, 4, 1, 1, 6, 5, 8, 9, 9, 6};
        int[] sortedArray = countSort(array);
        System.out.println(Arrays.toString(sortedArray));
    }
}

运行截图

总结

计数排序的时间复杂度可以做到O(N)，因为它的原理不是比较，而是计数。而通过比较达到排序效果的最快也要O(N*logN)。所以计数排序能达到线性排序的效果，但是这个算法有着局限性（max和min的差距不能过大；必须是整数）。