YUAN 2019-06-21
首先我们要对计数排序有一个正确的认识,计数排序是用于确定范围的整数的线性时间排序算法,这一句话我们就可以知道计数排序该如何用了.
处理数据:确定范围内的整数
特点:快(线性时间)
其数据如下:
最佳情况:T(n) = O(n+k)
最差情况:T(n) = O(n+k)
平均情况:T(n) = O(n+k)
计数排序的步骤如下
查找待排序数组中最大和最小的元素
统计每个值为i的元素的出现次数
对所有计数开始累加(从min开始,每一项和前一项相加)
反向填充目标数组,将每个元素i放在新数组的第C[i]项,每放一个元素,计数-1.
JS代码如下:
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 ]
仔细看代码就知道其实过程很简单,但是个人认为编码时的关键在于理解最后反向填充时的操作.