javascript - 对字符串中的所有字符进行排序

Question

我正在尝试解决这个问题，我想对字符串中的字符数组进行排序

问题:

对字符数组进行排序(仅限 ASCII，而非 UTF8)。

输入:一串字符，如完整的英文句子，由换行符或 NULL 分隔。可以重复。

例如:这很简单

输出:一串字符，按其 ASCII 值排序。您可以覆盖现有数组。

例如: Taehiisssy

解决方案的复杂性:以线性时间和恒定额外空间为目标。

我知道在 JavaScript 中你可以做类似的事情

const sorted = str.split('').sort().join('')

编辑:我想看看我是否可以使用 charCodeAt(i) 方法，如果我能从中得到任何东西的话。

但这将是 O(nLogN) ^^ 不是线性的(+用于拆分的额外空间 O(N))

但是在常量空间中，我们如何对字符数组进行排序？

Answer 1

逐个字符制定累计计数

const s="This is easy";

// Create an array which will hold the counts of each character, from 0 to 255 (although strictly speaking ASCII is only up to 127)
let count = Array(256).fill(0);

// Look at each character in the input and increment the count for that character in the array.
for(let i=0; i<= s.length; i++) {
  c=s.charCodeAt(i);
  count[c]++;
}

let out="";
// Now scan through the character count array ...
for(let i=0; i<= 255; i++) {
// And for each character, e.g. "T", show it the number of times you saw it in the input
  for(let rep=0; rep<count[i]; rep++){
    out+=String.fromCharCode(i);
  }
}

console.log(out);

这仅使用恒定的表格大小，256 个数字长(或您希望允许的任何数量的不同符号)。

并且它所花费的时间与输入字符串中的字符数线性相关(假设当该字符的计数为零时，几乎没有时间花在内部 FOR 循环上)。