частично сортировка массива, в котором некоторые числа уже отсортированы

Question

Мне нужно частично отсортировать массив в порядке убывания, в котором некоторые числа могут быть отсортированы.

Является ли их любая функция, которая могла бы сделать это эффективно или любой эффективный алгоритм.

Answer 1

Timsort предназначен специально для этого случая.

Timsort является алгоритмом сортировки гибрида, полученный от сортировки слияния и сортировки вставок, чтобы они хорошо выступить на многих видах реального мира данных. Он был изобретен Тимом Петерсом в 2002 году для использования на языке программирования Python . Алгоритм находит подмножества данных, которые уже заказываются , и использует подмножества для сортировки данных более эффективно.

Другая альтернатива Smoothsort, также предназначенная для использования частично отсортированных данных.

Это является разновидностью пирамидальной сортировки, разработанный Эдсгер Дейкстрой в 1981 г. Как пирамидальной сортировки, Плавная сортировка-х верхняя граница представляет собой О (п журнала п). преимущества Плавной сортировки является то, что он приходит ближе к O (п) время, если входа уже отсортированный в каком-то степени, в то время как пирамидальной сортировке средних О (п лога п) независимо от начального отсортированном состояния.

Answer 2

std::sort в целом.

Хотя точная информация о реализации является качеством реализации, хорошая реализация std::sort должна использовать частично отсортированный характер данных. libc++., Например.

Обратите внимание, что если вы знаете, где отсортированные элементы, вы можете использовать std::inplace_merge. Например, предположим, что v является vector с сортировкой [1, 7] и [7, 10], тогда вы можете использовать std::inplace_merge(v.begin() + 1, v.begin() + 7, v.begin() + 10), однако это более подвержено ошибкам.

Что касается заказа результата: если < вас не устраивает, не стесняйтесь предоставить свою собственную функцию сравнения.

Answer 3

Если вы занимаетесь сортировкой внутри цикла, вместо этого обратите внимание на treap или red-black tree. Котировки в среднем быстро (но с довольно большим стандартным отклонением), красно-черные деревья дают низкую изменчивость во время работы (не так хорошо при среднем времени работы, но при низком стандартном отклонении от времени). IOW, для пакетных приложений используйте treap, для интерактивных приложений вам может понадобиться красно-черное дерево, чтобы ваш пользователь не должен долго ждать.

Если вы не сортируете в цикле, то Timsort.