计数排序-Javascript

计数排序

首先我们要对计数排序有一个正确的认识,计数排序是用于 确定范围的整数的线性时间排序算法 ,这一句话我们就可以知道计数排序该如何用了.
处理数据: 确定范围内的整数
特点: 快(线性时间)

其数据如下:
最佳情况:T(n) = O(n+k)
最差情况:T(n) = O(n+k)
平均情况:T(n) = O(n+k)

计数排序的步骤如下

  1. 查找待排序数组中最大和最小的元素
  2. 统计每个值为i的元素的出现次数
  3. 对所有计数开始累加(从min开始,每一项和前一项相加)
  4. 反向填充目标数组,将每个元素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
22
23
24
25
26
27
28
29
30
function countingSort(arr){
var len = arr.length,
Result = [],
Count = [],
min = max = arr[0];
console.time('countingSort waste time:');
/*查找最大最小值,并将arr数置入Count数组中,统计出现次数*/
for(var i = 0;i<len;i++){
Count[arr[i]] = Count[arr[i]] ? Count[arr[i]] + 1 : 1;
min = min <= arr[i] ? min : arr[i];
max = max >= arr[i] ? max : arr[i];
}
/*从最小值->最大值,将计数逐项相加*/
for(var j = min;j<max;j++){
Count[j+1] = (Count[j+1]||0)+(Count[j]||0);
}
/*Count中,下标为arr数值,数据为arr数值出现次数;反向填充数据进入Result数据*/
for(var k = len - 1;k>=0;k--){
/*Result[位置] = arr数据*/
Result[Count[arr[k]] - 1] = arr[k];
/*减少Count数组中保存的计数*/
Count[arr[k]]--;
/*显示Result数组每一步详情*/
console.log(Result);
}
console.timeEnd("countingSort waste time:");
return Result;
}
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(countingSort(arr));

运行结果为:
[ , , , , , , , , , , , , , 48 ]
[ , , , , , , , , , , , , , 48, 50 ]
[ , , , , , 19, , , , , , , , 48, 50 ]
[ , , 4, , , 19, , , , , , , , 48, 50 ]
[ , , 4, , , 19, , , , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, , , , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, , 27, , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, 26, 27, , , , 46, , 48, 50 ]
[ 2, , 4, , , 19, 26, 27, 36, , , 46, , 48, 50 ]
[ 2, , 4, , 15, 19, 26, 27, 36, , , 46, , 48, 50 ]
[ 2, , 4, , 15, 19, 26, 27, 36, , , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, , , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, 38, , 46, 47, 48, 50 ]
[ 2, , 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]
countingSort waste time:: 14ms
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]

仔细看代码就知道其实过程很简单,但是个人认为编码时的关键在于理解最后反向填充时的操作.