Data Structures Algorithms 简明教程
Counting Sort Algorithm
计数排序是外部排序算法，它假定所有输入值都是介于 0 和 k 之间的整数。然后对这些输入值进行数学计算，以将它们置于输出数组中的正确位置。
Counting sort is an external sorting algorithm that assumes all the input values are integers that lie between the range 0 and k. Then mathematical computations on these input values to place them at the correct position in the output array.
该算法使用计数器来计算数字出现的频率，并按相应的顺序排列它们。假设数字“m”在输入序列中出现 5 次，则该计数器的值将变为 5，且在输出数组中重复 5 次。
This algorithm makes use of a counter to count the frequency of occurrence of the numbers and arrange them accordingly. Suppose, if a number ‘m’ occurs 5 times in the input sequence, the counter value of the number will become 5 and it is repeated 5 times in the output array.
Counting Sort Algorithm
计数排序算法假定输入相对较小，因此算法如下 −
The counting sort algorithm assumes that the input is relatively smaller so the algorithm is as follows −
*步骤 1 *− 维护两个数组，一个大小为不重复的输入元素以存储计数值，另一个大小为输入数组以存储输出。
*Step 1 *− Maintain two arrays, one with the size of input elements without repetition to store the count values and other with the size of the input array to store the output.
*步骤 2 *− 使用全 0 初始化计数数组，保持输出数组为空。
*Step 2 *− Initialize the count array with all zeroes and keep the output array empty.
*步骤 3 *− 每次元素出现在输入列表中，将对应的计数器值增加 1，直至达到输入列表的末尾。
*Step 3 *− Every time an element occurs in the input list, increment the corresponding counter value by 1, until it reaches the end of the input list.
*步骤 4 *− 现在，在输出数组中，每次计数器大于 0 时，将元素添加到其相应索引处，即如果“0”的计数器为 2，则把“0”添加到输出数组的第 2 个位置（即第 1 个索引处）。然后将计数器值减 1。
*Step 4 *− Now, in the output array, every time a counter is greater than 0, add the element at its respective index, i.e. if the counter of ‘0’ is 2, ‘0’ added at the 2nd position (i.e. 1st index) of the output array. Then decrement the counter value by 1.
*步骤 5 *− 重复步骤 4，直至所有计数器值变为 0。获得的列表即为输出列表。
*Step 5 *− Repeat Step 4 until all the counter values become 0. The list obtained is the output list.
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]Analysis
计数排序算法的平均情况时间复杂度与桶排序相同。它运行的时间为 Θ(n) 。
The average case time complexity for the counting sort algorithm is same as bucket sort. It runs in Θ(n) time.
Example
考虑一个要排序的输入列表为 0, 2, 1, 4, 6, 2, 1, 1, 0, 3, 7, 7, 9。
Consider an input list to be sorted, 0, 2, 1, 4, 6, 2, 1, 1, 0, 3, 7, 7, 9.
为了更容易计算，我们从个位数开始。
For easier computations, let us start with single digit numbers.
Step 1
Step 1
创建两个数组：一个用于存储计数器，另一个用于存储输出。使用 0 初始化计数器数组。
Create two arrays: to store counters and the output. Initialize the counter array with zeroes.
Step 2
Step 2
在将所有计数器值增加直到达到输入列表的末尾后，我们实现以下内容 −
After incrementing all the counter values until it reaches the end of the input list, we achieve −
Step 3
Step 3
现在，将元素推送到输出列表中相应索引处。
Now, push the elements at the corresponding index in the output list.
Step 4
Step 4
在输出数组中添加元素后，将计数器减少 1。现在，1 添加到了第 4 个索引中。
Decrement the counter by 1 after adding the elements in the output array. Now, 1 is added at the 4th index.
Step 5
Step 5
添加上一步中索引之前剩下的值。
Add the remaining values preceding the index in previous step.
Step 6
Step 6
在添加完最后一个值后，我们得到
After adding the last values, we get −
最终排序的输出为 0、0、1、1、1、2、2、3、4、6、7、7、9
The final sorted output is achieved as 0, 0, 1, 1, 1, 2, 2, 3, 4, 6, 7, 7, 9
Implementation
计数排序实现与我们构造数组以存储输入数组中每个元素的频率的算法紧密相关。根据这些频率，元素被放入输出数组中。在计数排序算法中，重复的元素也会被排序。
The counting sort implementation works closely with the algorithm where we construct an array to store the frequency of each element of the input array. Based on these frequencies, the elements are placed in the output array. Repetitive elements are also sorted in the counting sort algorithm.