Javascript 计数排序实现

Question

这是在 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]

Answer 1

代码是正确的，有一些注释：

• 一般来说，不鼓励使用for..inon arrays，但除非你在 Array 原型上定义可枚举属性（无论如何这都是一个坏主意），否则你使用它对我来说没问题

• 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]