如何有效地对数组进行排序

Question

我正在尝试对数组[3,3,2,1,3,2,2,2,1]到[1,1,3,3,3,2,2,2,2]进行排序。

我正在尝试使用对象来处理它，使用数字作为键，使用出现次数作为值。

const sortNums = (arr) => {
const result = {}
for (let i = 0; i < arr.length; i++) {
const num = result[arr[i]] || 0;
result[arr[i]] = num + 1;
}
//The above will gives me { '1': 2, '2': 4, '3': 3 }
//How to convert back to array?
}
console.log(sortNums([3,3,2,1,3,2,2,2,1]))

当然，我可以使用Object.entries映射回数组，但整个算法将被认为是O(n^2(，对吗？我试图探索它是否可以在O(n(中实现。或者我不应该用object开头？

Answer 1

您可以获得对数组进行排序的计数。

const sortNums = array => {
const count = {};
for (let v of array) count[v] = (count[v] || 0) + 1;
return array.sort((a, b) => count[a] - count[b] || a - b);
}
console.log(sortNums([3, 3, 2, 1, 3, 2, 1]));

使用对象进行排序的方法。

const sortNums = array => {
var count = {},
result = {};
for (let v of array) (count[v] = count[v] || []).push(v);
for (let a of Object.values(count)) (result[a.length] = result[a.length] || []).push(a);
return Object.values(result).flat(Infinity)
}
console.log(sortNums([3, 3, 2, 1, 3, 2, 1]));

Answer 2

您可以执行此

const sortNums = (arr) => {
const result = {}
for (let i = 0; i < arr.length; i++) {
const num = result[arr[i]] || 0;
result[arr[i]] = num + 1;
}
const a = [];
for(let i = 0; i <= 9; i++) {
if(result[i]) {
a.push(...Array.from({length: result[i]}, x => i));
}
}
return a;
}

Answer 3

尝试类似的东西

var curIndex = 0;
for i in result {
arr.fill(i, curIndex, curIndex + result[i]);
curIndex = curIndex + result[i];
}

Answer 4

假设这些数字是小的非负整数，您可以像已经做过的那样对它们进行计数，然后在有人(本例中为Array.from()(请求时立即生成结果，只需一对简单的循环：

function *sortNums(array){
let stats=[];
for(var i of array)
stats[i]=(stats[i]||0)+1;
for(let i=0;i<stats.length;i++)
while(stats[i]>0){
stats[i]--;
yield i;
}
}
console.log(Array.from(sortNums([3, 3, 10, 2, 1, 0, 3, 2, 1])).join());

当然，可以直接"传统"方式将碎片收集到阵列中：

let ret=[];
for(let i=0;i<stats.length;i++)
while(stats[i]>0){
stats[i]--;
ret.push(i);//yield i;
}
return ret;