文章目录
  1. 1. 计数排序
    1. 1.1. 排序问题
    2. 1.2. 计数排序
    3. 1.3. 思路
    4. 1.4. js基本思路实现
    5. 1.5. 验证

计数排序的javascript实现。

计数排序


排序问题

  • 输入:n个数的一个序列<a1, a2, ..., an>
  • 输出:输入序列的一个排列<a1', a2', ..., an'>,满足a1' <= a2' <= ... <= an'

计数排序

计数排序(Counting sort)是一种稳定的线性时间排序算法。
计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

当输入的元素是n个0到k之间的整数时,它的运行时间是Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。

思路

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

js基本思路实现

这里我们先使用两个数组分别保存“基准”左边、右边的子集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function countingSort(iArr, max) {
var n = iArr.length;
var oArr = [];
// 创建长度max的数组,填充0
var C = [];
for(var i = 0; i <= max; i++){
C[i] = 0;
}
// 遍历输入数组,填充C
for(var j = 0; j < n; j++){
C[iArr[j]]++;
}
// 遍历C,输出数组
for(var k = 0; k <= max; k++){
// 按顺序将值推入输出数组,并将对应标志位减1
while(C[k]-- > 0){
oArr.push(k);
}
}
return oArr;
}

验证

1
2
3
4
5
6
7
8
countingSort([5, 2, 4, 6, 1, 3], 6);
// 输出[1, 2, 3, 4, 5, 6]
countingSort([2, 1, 3, 1, 5], 5);
// 输出[1, 1, 2, 3, 5]
countingSort([5, 2, 12, 2, 134, 1, 3, 34, 4, 6, 1, 3, 4], 134);
// 输出[1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 12, 34, 134]

查看Github有更多内容噢:https://github.com/godbasin
更欢迎来被删的前端游乐场边撸猫边学前端噢

码生艰难,写文不易,给我家猪囤点猫粮了喵~

作者:被删

出处:https://godbasin.github.io

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

文章目录
  1. 1. 计数排序
    1. 1.1. 排序问题
    2. 1.2. 计数排序
    3. 1.3. 思路
    4. 1.4. js基本思路实现
    5. 1.5. 验证