计数排序解析及JavaScript实现

计数排序

计数排序(Counting sort)是一种稳定的线性时间排序算法。

计数排序使用一个额外的数组}C ,其中第i个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。当输入的元素是 n0k 之间的整数时,它的运行时间是 Θ(n+k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。

由于用来计数的数组 C 的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。

计数算法步骤

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

流程图

计数排序流程图

JavaScript代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function countSort(arr,min,max){
var len =arr.length,
// 桶数组
count = [],
// 输出数组
result = [];

// 找出输入数组中最大值和最小值
var max = Math.max.apply({},arr);
min = Math.min.apply({},arr);
// 初始化桶数组,从最小值开始,到最大值结束
for(var i = min; i <= max; i++){
count[i] = 0;
}
// 遍历输入数组,填充count
for(var j=0; j < len; j++){
count[arr[j]]++;
}

for(var k = 0; k <= max; k++){
// 按顺序将值推入输出数组,并将对应下标减1
while(count[k]-- > 0){
result.push(k);
}
}
return result;
}

验证

1
2
3
4
countSort([13, 44, 38, 26, 47, 15, 19, 26, 27, 15, 46, 14, 19, 50, 48]);
// 输出[13, 14, 15, 15, 19, 19, 26, 26, 27, 38, 44, 46, 47, 48, 50]
countSort([43,41,15,13,48,13,74,35,12,62,15,45]);
// 输出 [12, 13, 13, 15, 15, 35, 41, 43, 45, 48, 62, 74]

总结

计数排序就是简单的桶排序,一个桶代表数组中一个数出现的个数,所以需要一个和数组数字范围一样大的辅助数组,一般用在范围小于100的排序,时间复杂度为O(n),空间复杂度为数组的数字范围。

参考内容