Введение в алгоритмы быстрой сортировки в Java
Быстрая сортировка в Java, также известная как сортировка по разделу, является алгоритмом сортировки «разделяй и властвуй». Быстрая сортировка является хорошим примером алгоритма, который наилучшим образом использует кэши ЦП благодаря своей природе разделения и завоевания. Алгоритм быстрой сортировки является одним из наиболее используемых алгоритмов сортировки, особенно для сортировки больших списков, и большинство языков программирования реализовали его. В алгоритме быстрой сортировки исходные данные делятся на две части, которые индивидуально сортируются, а затем объединяются для получения отсортированных данных.
Предположим, что массив (8, 6, 3, 4, 9, 2, 1, 7) необходимо отсортировать с помощью быстрой сортировки.
Шаги для реализации алгоритмов быстрой сортировки
1. Выберите элемент под названием pivot из массива. Как правило, средний элемент выбран в качестве оси. Давайте возьмем 4 в качестве стержня.
2. Переставьте массив на две части таким образом, чтобы элементы, меньшие, чем точка поворота, находились до точки поворота, а элементы, большие точки поворота, появлялись после точки поворота. Следующие шаги выполняются:
- Выберите самый левый элемент, т. Е. 8, поскольку 4 - это ось, а 8 - больше, чем 4, 8 нужно переместить вправо от 4, справа мы оставляем 7, поскольку он больше 4, и выбираем 1 для замены с 8, следовательно, после замены массив становится: 1, 6, 3, 4, 9, 2, 8, 7
- Выберите следующий левый элемент, т. Е. 6, поскольку 4 - это ось, а 6 - больше, чем 4, 6 нужно переместить вправо от 4, справа мы оставляем 7, 8, поскольку они больше 4, и выбираем 2 для замены на 6, следовательно, после замены массив становится: 1, 2, 3, 4, 9, 6, 8, 7
- Теперь, поскольку все элементы слева от оси меньше, чем точка, а все элементы справа от точки больше, чем точка, мы закончили с 4 в качестве точки поворота.
3. Рекурсивно примените шаги 1 и 2 для левого подмассива (массив с элементами меньше, чем сводная), и для правого подмассива (массив с элементами больше, чем сводная). Если массив содержит только один или ноль элементов, то массив считается отсортированным.
Программа для реализации алгоритмов быстрой сортировки
Вот Java-программа для сортировки массива целых чисел с использованием алгоритма быстрой сортировки.
Код:
import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)
Выход:
Преимущества алгоритмов быстрой сортировки
Ниже приведены преимущества алгоритма быстрой сортировки:
- Отличное месторасположение ссылки . Местность ссылки - это способность процессора многократно получать доступ к одной и той же области памяти в течение короткого периода времени. Быстрая сортировка в java обеспечивает отличную локальность Reference из-за очень небольшого числа кеш-пропусков, что на современных архитектурах критично для производительности.
- Быстрая сортировка распараллеливается: после того, как начальный этап разделения массива на более мелкие области завершен, все отдельные подмассивы могут быть отсортированы параллельно независимо. По этой причине быстрая сортировка работает лучше.
Анализ сложности быстрой сортировки
Quicksort - это быстрый и хвосто-рекурсивный алгоритм, который работает по принципу «разделяй и властвуй». Вот его анализ сложности в лучшем, среднем и худшем случае:
- Сложность наилучшего случая: если массив или список содержит n элементов, то при первом запуске потребуется O (n). Теперь сортировка оставшихся двух подмассивов занимает 2 * O (n / 2). Это завершает сложность O (n logn) в лучшем случае.
- Средняя сложность случая: Средний случай быстрой сортировки составляет O (n log n).
- Сложность наихудшего случая: выбор первого или последнего приведет к снижению производительности для почти отсортированных или почти обратно отсортированных данных. Быстрая сортировка выполняет O (n 2) в худшем случае.
На Яве Массивы. Метод Sort () использует алгоритм быстрой сортировки для сортировки массива.
Рекомендуемые статьи
Это руководство по алгоритмам быстрой сортировки в Java. Здесь мы обсуждаем шаги для реализации, преимущества и анализ сложности алгоритма быстрой сортировки в Java вместе с программой. Вы также можете посмотреть следующие статьи, чтобы узнать больше -
- Сортировка вставок в Java
- цикл выполнения в Java
- JComponent в Java
- Квадраты в Яве
- Обмен в PHP
- Сортировка в C #
- Сортировка в Python
- С ++ Алгоритм | Примеры алгоритма C ++