Эффективный алгоритм сортировки строк

Question

Сортировка строк по сравнению (например, стандартная функция QuickSort + strcmp) может быть немного медленной, особенно для длинных строк, имеющих общий префикс (функция сравнения занимает время O (s), где s - длина строки) таким образом, стандартное решение имеет сложность O (s * nlog n). Известны ли более быстрые алгоритмы?

Answer 1

Если вы знаете, что строка состоит только из определенных символов (что почти всегда так), вы можете использовать вариант BucketSort или RadixSort .

Answer 2

Вы могли бы построить три , которые, я считаю, должны быть O(s*n).

Answer 3

Поищите «Sedgewick Multikey quick sort» (Седжвик написал известные учебники по алгоритмам на C и Java).Его алгоритм относительно прост в реализации и довольно быстр.Это позволяет избежать проблемы, о которой вы говорите выше.Существует алгоритм сортировки пакетов, который утверждает, что он быстрее, но я не знаю ни о какой реализации.

Есть статья Быстрая сортировка строк в C # и F # , которая описывает алгоритм иимеет ссылку на код Седжвика, а также на код C #.(раскрытие: это статья и код, который я написал на основе статьи Седжвика).