Время выполнения для метода Arrays.Sort в Java

Question

Кто-нибудь знает время работы в большой нотации O для метода arrays.sort java? Мне нужно это для моего научного проекта.

Answer 1

От официального docs

Я заметил, что есть в основном два подхода. Таким образом, это зависит от того, что вы сортируете и какой перегруженный метод от sort семейства методов, которые вы вызываете.

Документов отметить, что для примитивных типов, таких какlong, byte (Пример: static void sort(long[])):

Алгоритма сортировки является настроен быстрой сортировкой, приспособленной от Jon L. Bentley и М. Дугласа Макилры " Engineering a Sort Function ", Практика и опыт в области программного обеспечения, Vol. 23 (11) P. 1249-1265 (ноябрь 1993). Этот алгоритм обеспечивает производительность n * log (n) во многих наборах данных , которые приводят к снижению производительности на быстродействие до квадратичной производительности.

Для типов объектов: (Пример: void sort(Object list[]))

Гарантированное O (NlogN) исполнение

Алгоритм сортировки представляет собой модифицированный слиянием (в котором слияние опущен если самый высокий элемент в нижнем подсписке меньше, чем нижний элемент в верхнем подсписке ). Этот алгоритм обеспечивает гарантированную производительность n * log (n) .

Надеюсь, что это поможет!

Answer 2

Arrays.sort() использует Tim sort - O (N log N) для массива объектов и QuickSort для массивов примитивов - снова O (N log N).

Вот удивительное сравнение алгоритмов сортировки: http://www.sorting-algorithms.com/