Data Structures Algorithms 简明教程

Counting Sort Algorithm

计数排序是外部排序算法，它假定所有输入值都是介于 0 和 k 之间的整数。然后对这些输入值进行数学计算，以将它们置于输出数组中的正确位置。

该算法使用计数器来计算数字出现的频率，并按相应的顺序排列它们。假设数字“m”在输入序列中出现 5 次，则该计数器的值将变为 5，且在输出数组中重复 5 次。

Counting Sort Algorithm

计数排序算法假定输入相对较小，因此算法如下 −

*步骤 1 *− 维护两个数组，一个大小为不重复的输入元素以存储计数值，另一个大小为输入数组以存储输出。

*步骤 2 *− 使用全 0 初始化计数数组，保持输出数组为空。

*步骤 3 *− 每次元素出现在输入列表中，将对应的计数器值增加 1，直至达到输入列表的末尾。

*步骤 4 *− 现在，在输出数组中，每次计数器大于 0 时，将元素添加到其相应索引处，即如果“0”的计数器为 2，则把“0”添加到输出数组的第 2 个位置（即第 1 个索引处）。然后将计数器值减 1。

*步骤 5 *− 重复步骤 4，直至所有计数器值变为 0。获得的列表即为输出列表。

COUNTING-SORT(A, B, k)
let C[0 … k] be a new array
for i = 0 to k
C[i] = 0
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1

// C[i] now contains the number of elements equal to i.
for i = 1 to k
C[i] = C[i] + C[i – 1]
// C[i] now contains the number of elements less than or equal to i.
for j = A.length downto 1
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j – 1]