Лучшая структура данных для хранения миллиона значений?

Question

Пожалуйста, укажите сложность времени и лучшую структуру данных для хранения этих значений, когда значения:

1. Целые
2. Строки (словарь сортировки)

Я знаю Подсчет сортировки предпочтителен, когда целые числа находятся в небольшом диапазоне.

Спасибо.

Edit: Извините, я задал немного другой вопрос. Актуальный вопрос заключается в том, какова была бы лучшая структура данных для хранения этих значений, если целые числа являются номерами телефонов (а строки являются именами), а затем найти лучший алгоритм сортировки.

Answer 1

Взгляните на: Btrees и красно-черные деревья .

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

Answer 2

Алгоритмы сортировки вики-ссылки: Алгоритм сортировки вики

Сортировка слиянием и быстрая сортировка довольно хороши, в лучшем случае они не регистрируются.

Answer 3

Как насчет кучи ?Относительно прост в реализации и довольно быстр.Для строк вы можете использовать Trie вместе с чем-то вроде Burst sort, который, предположительно, является самым быстрым алгоритмом сортировки строк в своем классе.

Answer 4

На 32-битной машине миллион целых чисел может уместиться в массив из 4 миллионов байтов. 4 МБ не так уж много; он уместится в памяти этой системы в 500 раз (и это не так уж сложно по современным меркам). Миллион строк будет того же размера, за исключением места для хранения этих строк; для коротких строк это по-прежнему не проблема, поэтому добавьте все это. У вас может быть даже массив указателей на структуры, содержащие целое число и ссылку на строку; все будет хорошо. Только когда вы имеете дело с гораздо большим количеством данных (например, с миллиардом элементов), вам необходимо принимать специальные меры в отношении структуры данных.

Для сортировки такого количества вещей выберите алгоритм O ( n log n ) вместо алгоритма O ( n ^2). ). Алгоритмы O ( n ) полезны только тогда, когда у вас есть особенно компактные пространства ключей, что довольно редко встречается на практике. Выбор алгоритма из набора, который находится в O ( n log n ), зависит от скорости балансировки и других хороших свойств, таких как стабильность.

Если вы делаете это по-настоящему, используйте базу данных с соответствующими индексами вместо того, чтобы делать это вручную.

Answer 5

Для большинства алгоритмов сортировки существует версия на месте, поэтому может быть достаточно простого массива.Для строк вы можете рассмотреть http://en.wikipedia.org/wiki/Trie,, который может сэкономить место.Правильный алгоритм сортировки зависит от множества факторов, например, могут ли результаты быть уже отсортированы или частично отсортированы.Конечно, если у вас есть только несколько различных значений, можно использовать Countingsort, Bucketsort и т. Д.