排序变长项/算法

Question

我一直在研究我的算法期中和存在，我碰上了有关排序可变长度的项目书这个问题：

• 现在给你一个字符串数组，不同的字符串可能有不同的字符数，但是所有字符串的总字符数是n。演示如何在O（n）时间对字符串进行排序。

我发现很多网上的答案，但他们并没有在他们的解释很清楚，所以我真的很感激，如果你能花时间深入更给我解释一下这个答案建议应做排序在O（n）的字符串时间：

1. 组由长度字符串和命令组
2. 起始I上的最大长度和下降到1后，对第i个字符计数 排序。确保只包含具有第i个字符的组。 如果群体是原数组中后续子阵中，我们执行

Answer 1

这是你正在寻找：https://en.wikipedia.org/wiki/Radix_sort

在简单的话：

你首先第一个数字排序的字符串。 这可以通过O（N）完成，因为您不需要将每个元素与其他元素进行比较。你只需要记住数组中每组值的起始和结束位置。例如，所有以'g'开头的字符串都位于数组位置35到500.当您找到一个以'g'开头的字符串时，将它添加到该组的结尾。

在下一个阶段，您对每个组都做同样的事情。如您所见，需要O（M * N），其中M是字符串长度，N是字符串的数量。 在你的情况下，你的N是所有字符串的总长度，所以它是O（N）。

虽然你有不同长度的字符串，你仍然可以保持O（N），因为在某些时候太短的项目不需要重新排序。