У меня есть массив значений, который почти, но не совсем отсортирован, с несколькими смещенными значениями (скажем, 50 в 100000). Как его сортировать наиболее эффективно?
Эффективно сортировать
Ответ 1
В предположении, что массив почти отсортирован, вы можете использовать одно из следующих значений:
Smoothsort
У Wiki даже есть реализация java на нем. Так как вы не можете сделать это быстрее, чем O (n) (так как для того, чтобы даже выяснить, отсортирован ли массив или нет), это хороший выбор. Подробнее здесь.
Преимущество smoothsort заключается в том, что он приближается к времени O (n), если вход уже отсортирован в некоторой степени
Коктейльная сортировка
Сложность сортировки коктейлей в больших O обозначается O (n2) как для худшего случай и средний случай, но он становится ближе к O (n), если список прежде всего, перед применением алгоритм сортировки,
Timsort
Java-массивы фактически используют timsort в java 7 для сортировки объектов (sort()). Описание timsort здесь.
Ответ 2
Используйте вставку сортировки; это отлично с почти сортированными массивами, так как это близко к O (n) времени для них. Я действительно верю, что .NET Framework использует сортировку вставки для сортировки значений enum внутри (поскольку они часто сортируются), хотя мне пришлось бы повторно проверить это.
Ответ 3
Моя первая интуиция заключалась бы в том, чтобы идентифицировать неулокальные элементы и переместить их в отдельный массив, сортировать их там с любым алгоритмом, который вам нравится (с этим немного, это не должно иметь значения), а затем объединить их сортировку обратно.
Ответ 4
Поиск наилучшего алгоритма сортировки зависит от от того, сколько у вас контроля над данными.
Алгоритмы сортировки классифицируются как методы вставки, обмена, выбора, слияния и т.д. Это означает, что если вы можете управлять механизмом, который вставляет новые данные в массив, вы можете сортировать их при этом. Если вы можете сортировать массив только после того, как данные есть, то лучший алгоритм для этого - другой, совершенно другой.
В любом случае, это интересные показания:
http://en.wikipedia.org/wiki/Sorting_algorithm
алгоритмы, которые должны быть учтены, прежде всего, после первого обучения
Ответ 5
В настоящее время функции qsort или mergesort, предоставляемые большинством реализаций libc, уже эффективно обрабатывают этот особый случай.
Итак, прочитайте вашу документацию по libc или даже лучше, проверьте, как она реализует сортировку (если у вас есть доступ к исходному коду), потому что иногда это детализация, не укомплектованная документами!