本文概述
- 计数排序使用三个数组
- 运行时间分析
基本思想是确定最终排序数组中每个数字的“等级”。
计数排序使用三个数组
- [1, n]保留初始输入。
- B [1, n]保存排序的输出。
- C [1, k]是整数数组。 C [x]是x在A中的等级, 其中x∈[1, k]
- 将C初始化为零
- 对于从1到n的每个j, 将C [A [j]]递增1
如果有重复项, 我们将在复制后递减C [i]。
Counting Sort (array P, array Q, int k) 1. For i ← 1 to k 2. do C [i] ← 0[ θ(k) times] 3. for j← 1 to length [A] 4. do C[A[j]] ← C [A [j]]+1 [θ(n) times] 5. // C [i] now contain the number of elements equal to i 6. for i← 2 to k 7. do C [i]←C [i] + C[i-1] [θ(k) times] 8. //C[i] now contain the number of elements ≤ i 9. for j ← length [A] down to 1 [θ(n) times] 10. do B[C[A[j]←A [j] 11. C[A[j]←C[A[j]-1说明：
步骤1：for循环将数组R初始化为“ o”。但是在第一步中, 将循环变量1初始化为k或将0初始化为k存在矛盾。由于0-1是基于最小值的, 因此出现在数组A（输入数组）中。基本上, 我们从输入数组’ A’ 中的最小值开始
对于步骤3到4的循环, 检查每个输入元素。如果输入元素的值为“ i”, 则将C [i]递增。因此, 在步骤5之后, 对于每个整数i = 0、1、2 … .. k, C [i]保持输入元素的数量等于I。
循环的步骤6至8确定每个i = 0、1 … ..多少个输入元素小于或等于i
对于步骤9到11的循环, 将每个元素A [j]放入输出数组B中的正确排序位置。对于每个A [j], 值C [A [j]]是A [j]的正确最终位置输出数组B中的[], 因为有C [A [j]]个元素小于或等于A [i]。
因为元素可能并不唯一, 所以每次将值A [j]放入数组B时, 我们就将C [A [j]减1。 , 移到输出数组中A [j]之前的位置。
运行时间分析
- 对于第1步到第2步的循环, 取θ（k）倍
- 对于第3步到第4步的循环, 取θ（n）倍
- 对于步骤6至7的循环, 取θ（k）倍
- 对于步骤9至11的循环, 取θ（n）倍
注意：
- 计数排序具有一个稳定的重要属性：具有相同值的数字在输出数组中的出现顺序与在输入数组中的出现顺序相同。
- “计数排序”在“基数排序”中用作子例程。
A= ( 7, 1, 3, 1, 2, 4, 5, 7, 2, 4, 3)解：
文章图片
图：初始A和C阵列
For j=1 to 11J=1, C [1, k] =
文章图片
图：A [1] = 7已处理
J=2, C [1, k] =
文章图片
图：A [2] = 1已处理
J=3, C [1, k]
文章图片
图：A [3] = 3已处理
J=4, C [1, k]
文章图片
图：A [4] = 1已处理
J=5, C [1, k]
文章图片
图：A [5] = 2已处理
更新后的C为：
文章图片
图：C现在包含A元素的数量
注意：这里将逐个扫描“ A”项并将其置于“ C”中的位置, 并且将在“ C”数组中的项中提及访问该项目的次数, 并且将其更新或计数器增加如果再次访问任何项目, 则为1。
现在, 将使用以下语句执行for循环i = 2至7：
C [i] = C [i] + C [i-1]通过应用这些条件, 我们将按照我所说的将C更新为2到7
C [2] = C [2] + C [1]C [3] = C [3] + C [2]C [2] = 2 + 2C [3] = 2 + 4C [2] = 4C [3] = 6C [4] = C [4] + C [3]C [5] = C [5] + C [4]C [4] = 2 + 6C [5] = 1 +8C [4] = 8C [5] = 9C [6] = C [6] + C [5]C [7] = C [7] + C [6]C [6] = 0 + 9C [7] = 2 + 9C [6] = 9C [7] = 11因此, 更新后的C为：
文章图片
图：C设置为对A的每个数字进行排名
现在, 我们将找到新的数组B
文章图片
现在有两个条件适用：
- B [C [A [j]←A [j]
- C [A [j]←C [A [j] -1
For j←11 to 1步骤1
B [C [A [11]]] = A [11]C [A [11] = C [A [11]-1B [C [3] = 3C [3] = C [3] -1B [6] = 3C [3] = 5
文章图片
图：A [11]放置在输出数组B中
第2步
B [C [A [10]]] = A [10]C [A [10]] = C [A [10]]-1B [C [4]] =4C [4] = C [4] -1B [8] = 4C [4] = 7
文章图片
图：A [10]放置在输出数组B中
第三步
B [C [A [9]] = A [9]C [A [9] = C [A [9]]-1B [C [2]] = A [2]C [2] = C [2]-1B [4] = 2C [2] = 3
文章图片
图：A [9]放置在输出数组B中
步骤4
B [C [A [8]]] = A [8]C [A [8]] =C [A [8]] -1 B [C [7]] =7C [A [8]] = C [7]-1B [11] =7C [7] = 10
文章图片
图：A [8]放置在输出数组B中
第5步
B [C [A [7]]] = A [7]C [A [7]] = C [A [7]] - 1 B [C [5]] = 5C [5] = C [5] - 1B [9] = 5C [5] =8
文章图片
图：A [7]放置在输出数组B中
第6步
B [C [A [6]]] = A [6]C [A [6]] = C [A [6]] - 1B [C [4]] = 4C [4] = C [4] - 1B [7] = 4C [4] = 6
文章图片
图：A [6]放置在输出数组B中
步骤7
B [C [A [5]]] = A [5]C [A [5] = C [A [5]] -1B [C [2] =2C [2] = C [2] - 1B [3] = 2C [2] = 2
文章图片
图：A [5]放置在输出数组B中
步骤8
B [C [A [4]]] = A [4]C [A [4]] = C [A [4]] - 1B [C [1] = 1C [1] = C [1] - 1B [2] = 1C [1] = 1
文章图片
图：A [4]放置在输出数组B中
步骤9
B [C [A [3]]] = A [3]C [A [3]] = C [A [3]] - 1B [C [3] = 3C [3] = C [3] - 1B [5] = 3C [3] = 4
文章图片
图：A [3]放置在输出数组B中
第10步
B [C [A [2]]] = A [2]C [A [2]] = C [A [2]] - 1B [C [1]] = 1C [1] = C [1] - 1 B [1] = 1C [1] = 0
文章图片
图：A [2]放置在输出数组B中
步骤11
B [C [A [1]]] = A [1]C [A [1]] = C [A [1]] - 1B [C [7]] = 7C [7] = C [7] - 1B [10] = 7C [7] = 9
文章图片
【计数排序算法详细实现步骤】图：B现在包含最终排序的数据。
