Javascript Counting Sort implementation

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 原型上定义可枚举的属性(无论如何这是一个坏主意)，否则您使用它对我来说很好

• 您可以改进循环的部分，使其多次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]

Answer 2

计数排序是从初始化长度为 k 的辅助数组开始的，该数组将保存每个数字的计数。每个索引的初始值为 0。之后，您遍历输入数组，并在每次在数组中遇到该数字时将每个值的"计数"增加 1。现在，辅助数组保存每个元素在输入数组中的次数。最后一步是从最小值循环到最大值。在此循环中，您将遍历 count 数组中的每个相应值，并按顺序将 count 大于 0 的元素添加到数组中。你通过使用辅助递增变量添加每个项目(例如，如果我们使用"i"从最小值循环到最大值，那么我们将使用"j"遍历数组)，然后增加第二个递增变量，以便下一个项目放在下一个最高的数组索引中，最后你减少计数数组中当前项目的值，这样你就不会添加太多该值的元素。

const countingSort = (arr, min, max) => {
const count = {};
// First populate the count object
for (let i = min; i <= max; i++) {
count[i] = 0;
}
for (let i = 0; i < arr.length; i++) {
count[arr[i]] += 1;
}
/* Now, count is indexed by numbers, with values corresponding to occurrences, eg:
* {
*   3: 1,
*   4: 0,
*   5: 2,
*   6: 1,
*   7: 0,
*   8: 0,
*   9: 1
* }
*/

// Then, iterate over count's properties from min to max:
const sortedArr = [];
for (let i = min; i <= max; i++) {
while (count[i] > 0) {
sortedArr.push(i);
count[i]--;
}
}
return sortedArr;
};
console.log(countingSort([3, 6, 5, 5, 9], 3, 9));

Answer 3

const countingSort = (arr, min, max) => {

let counters = [...Array(max+1)].map(e => 0);
let result = []
for(let i = min; i < max; i++){
counters[arr[i]] += 1
}

for(let j = min; j <= max; j++){
while( counters[j] > 0){
result.push(j)
counters[j]--
}
}

return result
}

Answer 4

const countingSort = (arr, min, max) => {
const count = {};
// First populate the count object
for (let i = min; i <= max; i++) {
count[i] = 0;
}
for (let i = 0; i < arr.length; i++) {
count[arr[i]] += 1;
}
/* Now, count is indexed by numbers, with values corresponding to occurrences, eg:
* {
*   3: 1,
*   4: 0,
*   5: 2,
*   6: 1,
*   7: 0,
*   8: 0,
*   9: 1
* }
*/

// Then, iterate over count's properties from min to max:
const sortedArr = [];
for (let i = min; i <= max; i++) {
while (count[i] > 0) {
sortedArr.push(i);
count[i]--;
}
}
return sortedArr;
};
console.log(countingSort([3, 6, 5, 5, 9], 3, 9));

const countingSort = (arr, min, max) => {
const count = {};
// First populate the count object
for (let i = min; i <= max; i++) {
count[i] = 0;
}
for (let i = 0; i < arr.length; i++) {
count[arr[i]] += 1;
}
/* Now, count is indexed by numbers, with values corresponding to occurrences, eg:
* {
*   3: 1,
*   4: 0,
*   5: 2,
*   6: 1,
*   7: 0,
*   8: 0,
*   9: 1
* }
*/

// Then, iterate over count's properties from min to max:
const sortedArr = [];
for (let i = min; i <= max; i++) {
while (count[i] > 0) {
sortedArr.push(i);
count[i]--;
}
}
return sortedArr;
};
console.log(countingSort([3, 6, 5, 5, 9], 3, 9));

Answer 5

let a = [2, 1, 1, 0, 2, 5, 4, 0, 2, 8, 7, 7, 9, 2, 0, 1, 9];
let max = Math.max(...a);
let min = Math.min(...a);
function countingSort(arr) {
const count = [];
for (let i = min; i <= max; i++) {
count[i] = 0;
}
for (let i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
const sortedArr = [];
for (let i = min; i <= max; i++) {
while (count[i] > 0) {
sortedArr.push(i);
count[i]--;
}
}
return sortedArr;
}

console.log(countingSort(a));

Answer 6

解决这个问题的最简单方法是这样写的：

const range = (start, stop, step) => {
if (typeof stop == "undefined") {
stop = start;
start = 0;
}
if (typeof step == "undefined") step = 1;
if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) return [];
let result = [];
for (let i = start; step > 0 ? i < stop : i > stop; i += step) 
result.push(i);
return result;
};
const numbers = [1, 2, 2, 2, 1, 3, 3, 1, 2, 4, 5];
const max = Math.max.apply(Math, numbers);
let count = Array.apply(null, Array(max + 1)).map(() => 0);
for (x of numbers)
count[x] += 1;
let arr = [];
for (x in range(max + 1))
for (i in range(count[x]))
arr.push(parseInt([x]));
console.log(arr);