Функции сортировки Java

Question

В java коллекции.sort используется алгоритм сортировки слиянием вместо быстрого сортировки. Но Arrays.sort использует быструю сортировку. (И я не уверен в превышении факта, но я нашел это в Интернете, например, на веб-сайте, таком как CodeRanch, если они не используют этот алгоритм, пожалуйста, скажите мне)

Теперь я знаю, что средняя сложность обоих алгоритмов одинакова. Только факт - худшее, что хуже, O (n^2), но это не так. И мы не занимаемся пространством в сегодняшнем мире, поэтому не имеет значения, что сортировка слияния не является алгоритмом на месте. Но мы имеем дело со стабильностью, поэтому почему мы используем быструю сортировку для array.sort, потому что это не стабильный алгоритм. Это потому, что он касается только целых чисел, но я не думаю, что это хорошая причина.

Answer 1

Ваше помещение можно легко проверить, посмотрев соответствующий Javadocs, или даже source code. Во-первых, обратите внимание, что Collections.sort(List<T>) просто делегаты Arrays.sort(Object[]) (source):

public static <T extends Comparable<? super T>> void sort(List<T> list) { 
    Object[] a = list.toArray(); 
    Arrays.sort(a); 
    ListIterator<T> i = list.listIterator(); 
    for (int j=0; j<a.length; j++) { 
     i.next(); 
     i.set((T)a[j]); 
    } 
} 

Таким образом, эти два метода будут иметь такое же поведение, и во время выполнения. Как отмечено в документации, реализация равна TimSort, гибридной сортировке и вставке. Гарантируется, что он будет стабильным. Таким образом, сортировка объектов работает одинаково, есть ли у вас массив или коллекция.

К статье относится ссылка сортировка примитив массивы.Есть меньше предположений, которые нужно сделать о примитивных массивах, особенно равных примитивах, по определению, неотличимы. Это означает, что нет необходимости обеспечивать стабильный вид. Вы заметите, что документация для примитивных методов сортировки, например Arrays.sort(int[]), ничего не говорит об устойчивости этих методов сортировки, потому что такая деталь не имеет смысла. Стабильность имеет значение только при сортировке данных, которые могут быть равными, но не идентичными.

Answer 2

Arrays.sort будет немного быстрее, чем Collections.sort, потому что Collections.sort внутренне вызывает Array.sort. При работе с примитивами стабильность не имеет значения, поскольку примитивы одинакового значения могут быть перегруппированы без побочных эффектов. И Arrays.sort дает дополнительное преимущество в производительности. Следовательно, для примитивных массивов предпочтительным будет Array.sort.

Answer 3

Arrays.sort не реально использовать общую реализацию QuickSort, то Javadoc определяет:

Алгоритм сортировки является Dual-Pivot Quicksort Владимира Ярославском, Джон Бентли, и Джошуа Блох. Этот алгоритм обеспечивает производительность O (n log (n)) на многих наборах данных, которые приводят к тому, что другие quicksorts деградируют до квадратичной производительности и, как правило, быстрее, чем традиционных (одноповоротных) реализаций Quicksort.

Посмотрите на алгоритм сортировки, расположенный в DualPivotQuicksort; как вы можете видеть в комментариях, разные алгоритмы сортировки используются в зависимости от заданного массива.

Что касается метода сортировки Collections, он называет sort полученной реализацией, которая (в случае, если я проверял) делегирует Arrays.sort.

Answer 4

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

Arrays.sort на объектных массивах, и Collections.sort, используйте Timsort, который является вариацией слияния, которая делает стабильный вид.