Что происходит, когда мы выполняем Arrays.sort() в Java? какой алгоритм сортировки Java использует в фоновом режиме?
Начиная с выпуска Java 7 в 2011 году, по умолчанию используется алгоритм сортировки DualPivotQuickSort, который является улучшением по сравнению с классическим алгоритмом быстрой сортировки.
Быстрая сортировка с двойным поворотом – это комбинация сортировки по вставке и быстрой сортировки. Сортировка по вставке выполняется быстрее, когда количество сортируемых элементов невелико, Double pivot quicksort использует этот факт, таким образом, когда количество элементов равно Java выполняет сортировку вставки под капотом.
Когда размер массива входных данных превышает 47, Java использует быструю сортировку с двойным сводом. Как следует из названия, алгоритм DualPivotQuickSort выбирает 2 точки поворота вместо 1. В отличие от быстрой сортировки, в которой мы разделяем массив вокруг 1 точки поворота, мы разделяем массив на три части вокруг 2 точек поворота.
1 – й вложенный массив: элементы < LP 2 – й вложенный массив: LP 3-й подмассив =: элементы
Алгоритм
LP: Левый поворотный RP: Правый Поворот
1.) Крайний левый элемент в массиве принимается за левую точку поворота, а крайний правый элемент – за правую точку поворота. 2.) Поменяйте местами левую ось поворота на правую, если LP > RP 3.) Разделите массив на три подмассива вокруг левого и правого поворота.
Как только разбиение завершено, мы выполняем вышеуказанные 3 шага рекурсивно для трех подмассивов.
Давайте рассмотрим пример-:
Нет необходимости менять местами точки поворота на изображении выше, так как LP < RP. Теперь мы разделяем массив, следуя приведенным ниже схемам.
1 – й вложенный массив: элементы < LP 2 – й вложенный массив: LP 3-й подмассив =: элементы
Теперь у нас есть 3 подмассива, над которыми мы выполним те же действия, что и выше. Поскольку первые два массива содержат только 2 элемента, один станет левым поворотом, а другой – правым поворотом. Мы поменяем местами левую ось поворота на правую ось поворота, если левая ось поворота больше правой оси поворота, что не относится к первым двум подмассивам.
Для третьего подмассива, как мы можем видеть на изображении ниже, левый поворот больше, чем правый, поэтому мы поменяем их местами.
Замена опорных точек.
У нас больше нет элементов в массиве, которые мы могли бы разделить дальше.
Рекомендации
https://www.geeksforgeeks.org/dual-pivot-quicksort/ https://stackoverflow.com/questions/20917617/whats-the-difference-of-dual-pivot-quick-sort-and-quick-sort http://codeblab.com/wp-content/uploads/2009/09/DualPivotQuicksort.pdf
Заключение Аналогично, Python использует Timsort, который представляет собой комбинацию сортировки вставкой и сортировки слиянием. Я хотел бы прочитать и написать о других вариантах быстрой сортировки в ближайшие несколько дней.
Если вы хотите, чтобы я написал на определенную тему, пожалуйста, не стесняйтесь размещать их в разделе комментариев ниже.
Вы можете поддержать мою работу, купив мне кофе ниже. 💚 💚 💚 💚 Хочу хотеть!!
Оригинал: “https://dev.to/s_awdesh/double-pivot-quick-sort–javas-default-sorting-algorithm-1m4”