Быстрее ли сортировать список после вставки элементов или добавления их в отсортированный список?

Question

Если у меня есть отсортированный список (скажем, быстрая сортировка для сортировки), если мне нужно добавить много значений, то лучше приостановить сортировку и добавить их в конец, а затем отсортировать или использовать двоичный код для размещения элементы правильно при добавлении их. Имеет ли значение, если предметы случайные или уже более или менее в порядке?

Answer 1

Если это .NET и элементы целые, то быстрее добавить их в словарь (или, если вы используете .Net 3.0 или выше, используйте HashSet, если вы не против потерять дубликаты). Это дает вам автоматическое сортировки.

Я думаю, что строки будут работать так же. Прелесть в том, что вы получаете O (1) вставку и сортировку таким образом.

Answer 2

Вы должны добавить их до, а затем использовать сортировку по основанию, это должно быть оптимальным

http://en.wikipedia.org/wiki/Radix_sort#Efficiency

Answer 3

Вставка элемента в отсортированный список - O (log n), а сортировка списка - O (n log N) Что говорит о том, что всегда лучше сначала отсортировать, а затем вставить

Но запомните, большое 'O' касается только масштабирования скорости с количеством элементов, возможно, для вашего приложения вставка в середине стоит дорого (например, если это был вектор), и поэтому добавление и сортировка после этого могут быть лучше.