这是在 Javascript 中实现计数排序的好方法还是最佳方法? 找不到标准的 JS 计数排序示例。
function countingSort(arr){
var helper = []; // This helper will note how many times each number appeared in the arr
// Since JS arrary is an object and elements are not continuously stored, helper's Space Complexity minor that n
for(var i = 0; i<arr.length; i++){
if(!helper[arr[i]]){
helper[arr[i]] = 1;
}else{
helper[arr[i]] += 1;
}
}
var newArr = [];
for(i in helper){
while(helper[i]>0){
newArr.push(parseInt(i));
helper[i]--;
}
}
return newArr;
}
var arr = [5,4,3,2,1,0];
console.log(countingSort(arr)); // [0, 1, 2, 3, 4, 5]
最佳答案
代码正确,有一些注释:
一般来说,不鼓励在数组上使用
for..in
,但是除非您在 Array 原型(prototype)上定义可枚举属性(无论如何这都是个坏主意),否则您使用对我来说没问题您可以改进循环以多次
push
相同值的部分。这可以通过将Array(helper[i]).fill(i)
连接到结果中“一次”完成。
您还可以使用reduce
使函数更具函数式编程 风格。在极端情况下,它可能看起来像这样:
function countingSort(arr){
return arr.reduce( (acc, v) => (acc[v] = (acc[v] || 0) + 1, acc), [] )
.reduce( (acc, n, i) => acc.concat(Array(n).fill(i)), [] );
}
// Sample run:
var arr = [5,4,3,2,1,0];
console.log(countingSort(arr)); // [0, 1, 2, 3, 4, 5]
关于Javascript 计数排序实现,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43194336/