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