Javascript Counting Sort implementation

Question

這是一個很好的方法或最好的方法來實現Counting Sort in 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不鼓勵，但除非你對數組原型定義枚舉的屬性（這是壞的想法無論如何），你對我的使用對我來說很好

• 你可以改進你循環到push幾次相同的值的部分。這可以通過將Array(helper[i]).fill(i)連接到結果「1」來完成。

你也可以使用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]