计数排序就是这么容易

[toc]

声明：参考来源互联网，有任何争议可以留言。站在前人的肩上，我们才能看的更远。

本教程纯手打，致力于最实用教程，不需要什么奖励，只希望多多转发支持。
欢迎来我公众号，希望可以结识你，也可以催更，微信搜索：JavaPub

有任何问题都可以来谈谈！

计数排序 是比较容易的排序算法，但是对数量级较小的整数排序很实用。

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

例如：计数排序是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

计数排序是一个简单的排序算法，看下边原理很容易理解。

算法的步骤如下：

找出待排序的数组中最大和最小的元素
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项
对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1

如果有疑问，看下边一个例子

题目：数组里有 20 个随机数，取值范围为从 0 到 10，要求用最快的速度把这 20 个整数从小到大进行排序。

无论是 [归并排序]()，[冒泡排序]() 还是 [快速排序]() 等等，都是基于元素之间的比较来进行排序的。但是有一种特殊的排序算法叫 计数排序 ，这种排序算法不是基于元素比较，而是利用 数组下标 来确定元素的正确位置。

通过 计数排序 特性分析题目，我们知道整数的取值范围是从 0 到 10，那么这些整数的值肯定是在 0 到 10 这 11 个数里面。于是我们可以建立一个长度为 11 的数组，数组下标从 0 到 10，元素初始值全为 0，如下所示：

先假设 20 个随机整数的值是：9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9

让我们先遍历这个无序的随机数组，每一个整数按照其值对号入座，对应数组下标的元素进行 加 1 操作。

比如第一个整数是 9，那么数组下标为 9 的元素加 1：

第二个整数是 3，那么数组下标为 3 的元素加 1：

继续遍历数列并修改数组 ……

最终，数列遍历完毕时，数组的状态如下：

数组中的每一个值，代表了数列中对应整数的出现次数。

有了这个统计结果，排序就很简单了，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次：

0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10

这就是计数排序的基本过程，它 适用于一定范围的整数排序。在取值范围不是很大的情况下，它的性能在某些情况甚至快过那些 O(nlogn)的排序，例如快速排序、归并排序。

@Test
public void sortJavaPub(){int [] array = {2,1,5,3,4};
    //1. 得到数列的最大值
    int max = array[0];
    for (int i = 1; i < array.length; i++) {if (array[i] > max)
            max = array[i];
    }
    //2. 根据数列的最大值确定统计数组的长度
    int[] coutArray = new int[max + 1];
    //3. 遍历数列，填充统计数组
    for(int i = 0; i < array.length; i++)
        coutArray[array[i]]++;

    //4. 遍历统计数组，输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for (int i = 0; i < coutArray.length; i++) {for (int j = 0; j < coutArray[i]; j++) {sortedArray[index++] = i;
        }
    }
    System.out.println(Arrays.toString(sortedArray));
}

返回结果：

[1, 2, 3, 4, 5]

1. 当数列最大最小值差距过大时，并不适用于计数排序

比如给定 20 个随机整数，范围在 0 到 1 亿之间，此时如果使用计数排序的话，就需要创建长度为 1 亿的数组，不但严重浪费了空间，而且时间复杂度也随之升高。

2. 当数列元素不是整数时，并不适用于计数排序

如果数列中的元素都是小数，比如 3.1415，或是 0.00000001 这样子，则无法创建对应的统计数组，这样显然无法进行计数排序。

计数排序就是这么容易

前言

1. 计数排序(Counting Sort)

1.1. 计数排序(Counting Sort)

2. 原理

2.1. 步骤

2.2. 实例题目

3. 代码

3.1. 代码

4. 扩展阅读

4.1. 局限性