Сортировать массив, который частично отсортирован

Question

Я пытаюсь отсортировать массив с такими свойствами, как

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

пример массива = 14,19,34,56,36,22,20,7,45,56,50,32,31,45 ......... до

Заранее спасибо

Answer 1

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

В общем, сложность N log N, потому что мы не знаем, как она отсортирована на данный момент. Если он умеренно хорошо отсортирован, то есть меньше изменений направления, то потребуется меньше сравнений.

Answer 2

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

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

Answer 3

Strand Sort может быть близко к тому, что вы ищете. O (n sqrt (n)) в среднем случае, O (n) в лучшем случае (список уже отсортирован), O (n ^ 2) в худшем случае (список отсортирован в обратном порядке).

Делись и наслаждайся.

Answer 4

Если вы точно знаете, что данные «почти отсортированы» и размер набора достаточно мал (скажем, массив, который можно проиндексировать с помощью 16-разрядного целого числа), то, вероятно, Shell Ваша лучшая ставка. Да, он имеет базовую временную сложность O (n ^ 2) (которую можно уменьшить с помощью последовательности, используемой для определения размера промежутка, до текущего наилучшего наихудшего случая O (n * log ^ 2 (n))), но производительность улучшается с сортировкой входного набора, установленного в наилучшем случае O (n) на уже отсортированном наборе. Использование последовательности Седжвика для размера промежутка даст лучшую производительность в тех случаях, когда входные данные сортируются не так, как вы ожидали.

Answer 5

См. Топологическая сортировка