Почему java.util.Arrays.sort (Object []) использует 2 вида алгоритмов сортировки?
Перейдите в Project / properties и Java Built Path и непроверьте частные библиотеки Android
4 ответа
Важно отметить, что алгоритм O(N log N) на практике не всегда быстрее, чем O(N^2). ) алгоритм. Это зависит от констант и задействованного диапазона N. (Помните, что асимптотическая запись измеряет относительную скорость роста, а не абсолютную скорость).
Для небольших N сортировка вставками фактически превосходит сортировку слиянием. Это также быстрее для почти отсортированных массивов.
Вот цитата:
Хотя это один из элементарных алгоритмов сортировки с
O(N^2)временем наихудшего случая, сортировка вставками является предпочтительным алгоритмом. либо когда данные почти отсортированы (поскольку они адаптивны), либо когда размер задачи невелик (поскольку у нее небольшие накладные расходы).По этим причинам, а также потому, что она стабильна, сортировка вставками часто используется в качестве рекурсивного базового случая (когда размер задачи невелик) для алгоритмов сортировки по принципу «разделяй и властвуй» с более высокими накладными расходами, таких как сортировка слиянием или быстрая сортировка. .
Вот еще одна цитата из Лучший алгоритм сортировки для почти отсортированных списков статья:
прямая сортировка вставками лучше всего подходит для небольших или очень почти отсортированных списков
На практике это означает следующее:
- Некоторый алгоритм A1 с более высокой асимптотической верхней границей может быть предпочтительнее другого известного алгоритма A2 с более низкой асимптотической верхней границей
- Возможно, A2 просто слишком сложно реализовать
- Или, возможно, это не имеет значения в рассматриваемом диапазоне
N- См., например. Алгоритм Копперсмита-Винограда
- Некоторые гибридные алгоритмы могут адаптировать различные алгоритмы в зависимости от размера входных данных
Связанные вопросы
- Какой алгоритм сортировки лучше всего подходит для повторной сортировки почти полностью отсортированного списка?
- Является ли Есть ли веская причина использовать сортировку вставками?
Числовой пример
Давайте рассмотрим эти две функции:
f(x) = 2x^2; эта функция имеет квадратичную скорость роста, то есть «O(N^2)»g(x) = 10x; эта функция имеет линейный рост, то есть "O(N)"
Теперь давайте построим две функции вместе:
Источник: WolframAlpha: постройте 2x^2 и 10x для x от 0 до 10
Обратите внимание, что между x=0..5, f(x) <= g(x), но для любого большего x, f(x) быстро перерастает g(x).
Аналогично, если A1 является квадратичным алгоритмом с низкими накладными расходами, а A2 является линейным алгоритмом с высокими , A1 может быть быстрее, чем A2.
Таким образом, вы можете, если захотите, создать гибридный алгоритм A3 , который просто выбирает один из двух алгоритмов в зависимости от размера входных данных. Стоит ли это усилий, зависит от фактических задействованных параметров.
Было проведено множество тестов и сравнений алгоритмов сортировки, и было решено, что, поскольку сортировка вставками превосходит сортировку слиянием для небольших массивов, стоит реализовать оба метода для Arrays.sort.
Похоже, они считают, что mergeSort (array ) медленнее для коротких массивов. Надеюсь, они действительно это проверили.
Цитируется по: http://en.wikipedia.org/wiki/Insertion_sort
Some divide-and-conquer algorithms such as quicksort and mergesort sort by
recursively dividing the list into smaller sublists which are then sorted.
A useful optimization in practice for these algorithms is to use insertion
sort for sorting small sublists, where insertion sort outperforms these more
complex algorithms. The size of list for which insertion sort has the advantage
varies by environment and implementation, but is typically between eight and
twenty elements.
Это для скорости. Накладные расходы на mergeSort достаточно высоки, поэтому для коротких массивов он будет медленнее, чем сортировка вставками.