Как сортировать быстрее, чем n log n (учитывая сильное условие в списке)?

Ответ 1

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

Ключевым фактом является то, что вы работаете с целыми числами, и вы знаете самый большой ключ, который точно используется для сортировки по методу radix и его сложность линейна.

также второй подход, если k из них уже отсортирован, вы можете использовать некоторую версию сортировки оболочки с последовательностью, которая даст лучший результат

Ответ 2

Сортировка выбора - хороший выбор, когда ваш массив уже в основном отсортирован; он должен выполнять только O(n(n-k) свопы. Если отсортированные элементы имеют тенденцию быть смежными, то Timsort также может хорошо работать. В любом случае вы не будете лучше, чем O(n log n) при достаточно малых k, конечно.

Ответ 3

Если мы не знаем:

• как k и n связаны друг с другом
• и как именно элементы k находятся в массиве

Существует простой вариант, который мы можем сделать намного лучше, чем Θ(nlog(n)) в худшем случае.

Почему:

• Положим k=1 и удачи...
• Скажем, что k=0.9n и положим k элементов спереди. Даже если бы мы знали, что они впереди, нам еще нужно отсортировать массив размером 0.1n, поэтому в худшем случае нам нужны 0.1*n*log(0.1*n)=0.1*n*(log(0.1)+log(n))=0.01*nlog(n)-0.1*n сравнения, которые Θ(n*log(n)).

Конечно, это только теоретический результат для худшего случая. На практике информация о том, что есть ровно k элементов в соответствующих местах, может ограничить значительную работу. Но наверняка нам нужно знать немного больше о k и n (или, по крайней мере, предполагать что-то).

Ответ 4

Адаптивная сортировка - это своего рода алгоритмы сортировки, которые используют существующий порядок в своем вводе. Сортировка вставки - один из адаптивных видов, который хорошо работает, когда массив почти отсортирован. Конечно, худшим случаем является O (N ^ 2).

Существуют и другие адаптивные типы, такие как, Adaptive heap sort, которые используют treap, чтобы преимущество упорядоченных элементов при построении кучи. Адаптивная сортировка слияния (естественная сортировка слияния) и Smoothsort

Теоретическая сложность также будет O (N * lnN), но они могут работать более эффективно, когда данные частично сортируются.

Ответ 5

Алгоритм:

• Найдите пробег k смежных элементов уже в порядке
• Сортировка других элементов n-k
• Слияние двух отсортированных списков

Пример с n = 8, k = 4.

['echo', 'cat', 'bat', 'board', 'hand', 'hotel', 'kilo', 'hit']

Найдите 4 смежных элемента уже по порядку.

['echo', 'cat', 'bat', 'board', 'hand', 'hotel', 'kilo', 'hit']

(Так получилось, что мы нашли 5 уже по порядку. Тем лучше.)

Сортировка других элементов

[cat, echo, hit]

Объедините два отсортированных списка

['bat', 'board', 'cat', 'echo', 'hand', 'hit', 'hotel', 'kilo']

Готово.

Временные сложности трех шагов:

• О (п)
• О ((п-к) журнал (п-к))
• О (п)

Для любого фиксированного отношения k/n, второй шаг доминирует (при достаточно большом n).