Ответ 1
Если вы знаете, что строка состоит только из определенных символов (что почти всегда имеет место), вы можете использовать вариант BucketSort или RadixSort.
Эффективный алгоритм сортировки строк
Сортировка строк путем сравнения (например, стандартная функция QuickSort + strcmp) может быть немного медленной, особенно для длинных строк, использующих общий префикс (функция сравнения принимает время O (s), где s - длина строки), поэтому стандартное решение имеет сложность O (s * nlog n). Известны ли более быстрые алгоритмы?
Ответы
Ответ 2
Вы можете создать trie, который должен быть O(s*n), я считаю.
Ответ 3
Пожалуйста, найдите "Быстрая сортировка Sedgewick Multikey" (Sedgewick написал знаменитые учебники по алгоритмам на C и Java). Его алгоритм относительно прост в реализации и довольно быстро. Это позволяет избежать проблемы, о которой вы говорите выше. Существует алгоритм сортировки пакетов, который утверждает, что работает быстрее, но я не знаю никакой реализации.
Существует статья Fast String Sort в С# и F #, которая описывает алгоритм и ссылается на код Sedgewick, а также на код С#, (раскрытие: это статья и код, который я написал на основе бумаги Sedgewick).