Лучший способ отсортировать длинный список строк

Question

Я хотел бы знать, как лучше отсортировать длинный список строк по времени и пространственной эффективности.Я предпочитаю эффективность времени, а не эффективность пространства.

Строки могут быть числовыми, буквенными, буквенно-цифровыми и т. Д. Меня не интересует поведение сортировки, такое как буквенно-цифровая сортировка v / s, алфавитная сортировка, только сама сортировка.

Несколько способов, о которых я могу подумать.

1. Использование кода, например: функция Arrays.Sort () фреймворка .Net.Я думаю, что способ, которым это работает, состоит в том, что хеш-коды для строк вычисляются, и строка вставляется в правильную позицию, используя двоичный поиск.

2. Использование базы данных (например: MS-sql).Я этого не сделал.Я не знаю, насколько это будет эффективно.

3. Использование префиксной древовидной структуры данных, такой как trie.Сортировка требует обхода всех trieNode дерева Trie с использованием времени DFS (поиск в глубину) - O (| V | + | E |).(Поиск занимает время O (l), где l - длина строки для сравнения).

Любые другие способы или структуры данных?

Answer 1

Я нашел этот документ , в котором используется структура данных Trie для эффективной сортировки больших наборов строк.Я не стал вдаваться в подробности.

Answer 2

Вы говорите, что у вас есть база данных, и предположительно строки хранятся в базе данных.Тогда вы должны получить базу данных, чтобы сделать работу за вас.Он может использовать индекс и, следовательно, не нужно фактически сортировать список, а просто читать его из индекса в отсортированном порядке.

Если индекс отсутствует, база данных все еще может помочьвы.Если вы выбираете только первые k строк для некоторого небольшого постоянного числа k, например, 100. Когда вы используете ORDER BY с предложением LIMIT, это позволяет SQL Server использовать специальную оптимизацию под названием TOP N SORT, которая выполняется влинейное время вместо времени O (n log (n)).

Если ваших строк еще нет в базе данных, вам следует использовать функции, предоставляемые .NET.Я думаю, что вряд ли вы сможете написать собственный код, который будет намного быстрее, чем сортировка по умолчанию.

Answer 3

Предположим, у вас большой список строк и длина списка равна N.

Использование алгоритма сортировки на основе сравнения, такого как MergeSort, HeapSort или Quicksort, даст вам

, где n - размер списка, а d - максимальная длина всех строк в списке.

В этом случае мы можем попытаться использовать сортировку по Radix.Пусть b будет основанием, а d будет длиной максимальной строки, тогда мы можем показать, что время выполнения с использованием радикальной сортировки равно .

Кроме того, если строки говорятстрочные буквы английского алфавита, время работы составляет

Источник: MIT Opencourse Algorithms, лекция проф.Эрик Демейн.

Answer 4

Radix sort также может быть хорошим вариантом, если строки не очень длинные, например, список имен