计数排序

什么是计数排序

“计数排序”,名副其实,就是根据”计数”的方式来进行排序,所谓”计数”,就是统计每个元素重复出现的次数。

图解计数排序-1

正如上述原始数列有5个数值,数值范围从1-5。

1
2
// 原始数列
let arr = [5,4,3,2,3,1]

那么,这些整数的值肯定是在1,2,3,4,5这5个数里面。

所以可以根据这个整数的取值范围,建立一个长度为6的数组(包括0,所以长度为6),数组下标从0到5,元素初始值全部为0。

1
2
// 用于计数的数组,数组长度为6,初始值全为0
let countingArr = [0,0,0,0,0,0]

接着根据原始数列中元素出现的次数和顺序,加入到计数数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 用于计数的数组,数组长度为6,初始值全为0
let countingArr = [0,0,0,0,0,0]
// 原始数组第一个元素为5,则在计数数组下标为5的位置加1
countingArr[5] += 1
// 以此类推,原始数组第二个元素为4,则在计数数组下标为4的位置加1
countingArr[4] += 1
// 以此类推,原始数组第三个元素为3,则在计数数组下标为3的位置加1
countingArr[3] += 1
// 以此类推,原始数组第四个元素为2,则在计数数组下标为2的位置加1
countingArr[2] += 1
// 以此类推,原始数组第五个元素为3,则在计数数组下标为3的位置加1
countingArr[3] += 1
// 以此类推,原始数组第六个元素为1,则在计数数组下标为1的位置加1
countingArr[1] += 1
// 最终得到的计数数组如下
console.log(countingArr)
// [0,1,1,2,1,1]

我们得到计数数组这个”统计结果”,排序就简单了。

后续的操作便是遍历数组,输出数组元素的下标值,元素的值是几,就输出几次。

1
2
// 计数排序后的结果
let result = [1,2,3,3,4,5]

总结

计数排序是使用空间换时间的排序算法,虽然使用它排序的速度很快,但是当数列的最大值最小值之间的插值鸿沟过大时,不适合计数排序(假设20个随机数,数值范围从0到10亿,就需要开辟10亿个数组空间,不仅浪费空间,而且时间复杂度也高);其次,计数排序只适合用于整数的数列元素场景,因为计数排序本身无法统计小数。

代码实现

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
* 找到数组中最大的一项
* @param {array} array 需要操作最大值的数组
* @param {function} compareFn // 比较用的方法,默认为defaultCompare
* @returns {number}} 返回数组中找到的最大值
*/
export function findMaxValue(array, compareFn = defaultCompare) {
// 要找到数组中的最大值,我们只需要迭代并找到值最大的一项即可
if (array && array.length > 0) {
let max = array[0];
for (let i = 1; i < array.length; i++) {
if (compareFn(max, array[i]) === Compare.LESS_THAN) {
max = array[i];
}
}
return max;
}
return undefined;
}
/**
* 计数排序
* @param {array} array 要进行排序的数组
* @returns {array} 返回排序后的数组
*/
export function countingSort(array) {
if (array.length < 2) { // 如果待排序的数组为空或只有一个元素,则不需要运行排序算法。
return array;
}
const maxValue = findMaxValue(array); // 找到数组中的最大值
let sortedIndex = 0;
const counts = new Array(maxValue + 1); // 创建计数数组,从索引 0 开始直到最大值索引 value + 1
array.forEach(element => {
// 迭代数组中的每个位置并在 counts 数组中增加元素计数值
if (!counts[element]) { // 为了保证递增成功,如果 counts 数组中用来计数某个元素的位置一开始没有用 0 初始化的话
counts[element] = 0; // 我们将其赋值为 0
}
counts[element]++;
});
// console.log('Frequencies: ' + counts.join());
// 所有元素都计数后,我们要迭代 counts 数组并构建排序后的结果数组
counts.forEach((element, i) => {
while (element > 0) {
array[sortedIndex++] = i; // 由于可能有多个元素有相同的值,我们要将元素按照在原始数组中的出现次数进行相加
element--; // 减少计数值,直到它为0
}
});
return array;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!