сортировка эффективно

Question

У меня есть массив значений, который почти, но не совсем отсортирован, с несколькими смещенными значениями (скажем, 50 на 100000).Как отсортировать наиболее эффективно?

Answer 1

В предположении, что массив почти отсортирован, вы можете использовать одно из следующих:

Smoothsort

В Wiki даже есть реализация java.Так как вы не можете сделать это быстрее, чем O (n) (поскольку для того, чтобы узнать, отсортирован ли массив или нет, требуется столько времени), smoothsort - хороший выбор.Подробнее здесь .

Преимущество сглаживания состоит в том, что оно приближается к времени O (n), если вход уже отсортирован в некоторой степени

Coctail sort

Сложность коктейльной сортировки в больших обозначениях O равна O (n2) как для наихудшего случая, так и для среднего случая, но она становится ближе к O (n) если список в основном упорядочен до применения алгоритма сортировки,

Timsort

Массивы Java фактически теперь используют timsort в Java 7 для сортировкиобъекты (sort()).Описание тимсорта здесь .

Answer 2

Использовать сортировка вставок ; это хорошо с почти отсортированными массивами, так как для них это почти время O (n). Я на самом деле считаю, что .NET Framework использует сортировку вставками для внутренней сортировки значений перечислений (поскольку они часто сортируются), хотя мне придется перепроверить это.

Answer 3

В настоящее время функции qsort или mergesort, предоставляемые большинством реализаций libc, уже эффективно обрабатывают этот особый случай.

Итак, прочитайте документацию по libc или, что еще лучше, проверьте, как она реализует сортировку(если у вас есть доступ к источнику), потому что иногда это детали реализации, не размещенные в документации!

Answer 4

Поиск Наилучший алгоритм сортировки зависит от степени контроля над данными.

Алгоритмы сортировки подразделяются на методы вставки, обмена, выбора, объединения и т. Д.Это означает, что если вы можете управлять механизмом, который вставляет новые данные в массив, вы можете сортировать их при этом.Если вы можете отсортировать массив только после того, как данные будут в наличии, тогда лучший алгоритм для этого - это совсем другой.

В любом случае, это интересные показания:

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

алгоритмы сортировки "что следует учить ученикам, когда учат первым"

сравнениеалгоритмы сортировки

что такое самый быстрый алгоритм сортировки в с

Answer 5

Моей первой интуицией было бы идентифицировать неуместные элементы и переместить их в отдельный массив, отсортировать их там с любым алгоритмом, который вам нравится (с этими несколькими, это не должно иметь значения), а затем объединить, отсортировать их обратно.