计数排序
描述
计数排序(Counting sort)是一种稳定的线性时间排序算法。它的复杂度为 Ο(n+k)
(其中 k
是整数的范围大小)
基本思想
对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定)。然后顺序输出
实现
1 | var CountingSort = (arr) => { |
过程分析
假如当前输入 [0,2,3,4,1,5,3,1,6,3,6,7,1,2]
找出
max = 7
和min = 0
,生成一个数组counting = [0, 0, 0, 0, 0, 0, 0, 0]
用于计数遍历
arr
对每个数进行收集,[1, 3, 2, 3, 1, 1, 2, 1]
记录比自己小的数字的总数
counting = [0, 1, 4, 6, 9, 10, 11, 13]
初始化新数组
[empty × 14]
,再遍历arr
x = 0
,counting[0] = 0
counting[0]++
result = [0, empty × 13]
counting = [1, 1, 4, 6, 9, 10, 11, 13]
x = 2
,counting[2] = 4
counting[2]++
result = [0, empty × 3, 2, empty × 9]
counting = [1, 1, 5, 6, 9, 10, 11, 13]
x = 3
,counting[3] = 6
counting[3]++
result = [0, empty × 3, 2, empty × 1, 3, empty × 7]
counting = [1, 1, 5, 7, 9, 10, 11, 13]
x = 4
,counting[4] = 9
counting[4]++
result = [0, empty × 3, 2, empty × 1, 3, empty × 2, 4, empty × 4]
counting = [1, 1, 5, 7, 10, 10, 11, 13]
x = 1
,counting[1] = 1
counting[1]++
result = [0, 1, empty × 2, 2, empty × 1, 3, empty × 2, 4, empty × 4]
counting = [1, 2, 5, 7, 10, 10, 11, 13]
x = 5
,counting[5] = 10
counting[5]++
result = [0, 1, empty × 2, 2, empty × 1, 3, empty × 2, 4, 5, empty × 3]
counting = [1, 2, 5, 7, 10, 11, 11, 13]
x = 3
,counting[3] = 7
counting[3]++
result = [0, 1, empty × 2, 2, empty × 1, 3, 3, empty × 1, 4, 5, empty × 3]
counting = [1, 2, 5, 8, 10, 11, 11, 13]
x = 1
,counting[1] = 2
counting[1]++
result = [0, 1, 1, empty × 1, 2, empty × 1, 3, 3, empty × 1, 4, 5, empty × 3]
counting = [1, 3, 5, 8, 10, 11, 11, 13]
x = 6
,counting[6] = 11
counting[6]++
result = [0, 1, 1, empty × 1, 2, empty × 1, 3, 3, empty × 1, 4, 5, 6, empty × 2]
counting = [1, 3, 5, 8, 10, 11, 12, 13]
x = 3
,counting[3] = 8
counting[3]++
result = [0, 1, 1, empty × 1, 2, empty × 1, 3, 3, 3, 4, 5, 6, empty × 2]
counting = [1, 3, 5, 9, 10, 11, 13, 13]
x = 6
,counting[6] = 12
counting[6]++
result = [0, 1, 1, empty × 1, 2, empty × 1, 3, 3, 3, 4, 5, 6, 6, empty × 1]
counting = [1, 3, 5, 9, 10, 11, 13, 13]
x = 7
,counting[6] = 13
counting[7]++
result = [0, 1, 1, empty × 1, 2, empty × 1, 3, 3, 3, 4, 5, 6, 6, 7]
counting = [1, 3, 5, 9, 10, 11, 13, 14]
x = 1
,counting[1] = 3
counting[1]++
result = [0, 1, 1, 1, 2, empty × 1, 3, 3, 3, 4, 5, 6, 6, 7]
counting = [1, 4, 5, 9, 10, 11, 13, 14]
x = 2
,counting[2] = 5
counting[2]++
result = [0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 6, 7]
counting = [1, 4, 6, 9, 10, 11, 13, 14]
最后输出数组
[0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 5, 6, 6, 7]
算法复杂度
平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|
O(n+k) | O(n+k) | O(n+k) | O(n+k) | out-place | 稳定 |