排序變長項/算法

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），因爲在某些時候太短的項目不需要重新排序。