Вручную сортировка вектора <int>в C ++

Question

В настоящее время я изучаю, как работают векторы в C ++.Я очень хорошо прочитал и понял их функциональность.

Я смотрю на различные способы сортировки векторного объекта с 10 000 объектов, я использовал метод std :: sort и shell sort.

Я заметил, что сортировка оболочки для вектора медленнее, чем сортировка простого массива в стиле C.Я узнал, что это потому, что «Быстрая вставка или удаление элементов в середине контейнера не поддерживается» (http://www.cppreference.com/wiki/container/vector/start). Так что, очевидно, сортировка оболочки с большим количеством случайных обращений будет довольно медленной.

Я былИнтересно, кто-нибудь знает, что будет лучше ручной метод сортировки для вектора с 10 000 целочисленных значений? Это для учебного упражнения, которое вы видите! :)

Answer 1

Для всех намерений и целей векторы - это массивы с добавленными тонкостями.Произвольный доступ так же быстр, как массив в стиле C.Удаление / вставка элементов в середине вектора выполняется медленно, но то же самое относится и к массивам в стиле C.Сортировка оболочки должна быть такой же быстрой по векторам, как и по массивам.Для меня это звучит так, будто вы делаете что-то неортодоксальное.

Быстрая сортировка или интросорт (std::sort один) должны быть самыми быстрыми сортировками на основе сравнения, доступными для вас.Mergesort немного медленнее, чем quicksort, но у него нет чувствительности quicksort к патологическим случаям.В среднем все они занимают O (n lg n) времени (с квадратичным наихудшим случаем для быстрой сортировки).

РЕДАКТИРОВАННОЕ ОБНОВЛЕНИЕ

Код: C-array и Vector на основе оболочек.С оптимизацией или без, сортировка 1 миллиона элементов занимает в два раза больше времени для векторов по неизвестной мне причине.Похоже, STL выполняет лот проверки ошибок при доступе к вектору.

Answer 2

Алгоритм типа быстрой сортировки идеально подходит для сортировки данных на месте, как если бы это было с вектором. То есть никаких вставок или удалений, просто перемещение данных в буфере фиксированного размера.

Answer 3

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

С уважением,
Деннис М.