概述

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

算法思想

计数排序对输入的数据有附加的限制条件:

1、输入的线性表的元素属于有限偏序集S;

2、设输入的线性表的长度为n，|S|=k(表示集合S中元素的总数目为k)，则k=O(n)。

在这两个条件下，计数排序的复杂性为O(n)。

计数排序的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数(此处并非比较各元素的大小，而是通过对元素值的计数和计数值的累加来确定)。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

算法步骤

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

示例

输入{3, 4, 3, 2, 1}，最大是4，数组长度是5。

建立计数数组{0, 0, 0, 0}。

遍历输入数组：

{3, 4, 3, 2, 1} -> {0, 0, 1, 0}

{3, 4, 3, 2, 1} -> {0, 0, 1, 1}

{3, 4, 3, 2, 1} -> {0, 0, 2, 1}

{3, 4, 3, 2, 1} -> {0, 1, 2, 1}

{3, 4, 3, 2, 1} -> {1, 1, 2, 1}

计数数组现在是{1, 1, 2, 1}，我们现在把它写回到输入数组里：

{0, 1, 2, 1} -> {

{o, o, 2, 1} -> {1, 2, 3, 2, 1}

{o, o, 1, 1} -> {1, 2, 3, 2, 1}

{o, o, o, 1} -> {1, 2, 3, 3, 1}

{o, o, o, o} -> {1, 2, 3, 3, 4}

这样就排好序了。

• 时间：O(n + k)，n是输入数组长度，k是最大的数的大小。
• 空间：O(n + k)，n是输入数组长度，k是最大的数的大小。

代码实现：

閱讀更多 咱小二 的文章

關鍵字: 算法 排序 技术