Алгоритм быстрой сортировки в Java

Быстрая сортировка, также известная как сортировка по разделам, представляет собой эффективный алгоритм сортировки “разделяй и властвуй”. Алгоритм может быть реализован с использованием циклов или рекурсий. Алгоритм выполняет сортировку на месте. Быстрая сортировка – это сортировка сравнения, что означает, что она может сортировать элементы любого типа, для которых определено отношение “меньше, чем”.

Алгоритм делит массив на два меньших подмассива. Чтобы разделить алгоритм на два массива, выбирается ось или элемент внутри массива. Фаза разбиения состоит в изменении порядка массива таким образом, чтобы все элементы со значениями, меньшими, чем точка поворота, находились перед точкой поворота, в то время как все элементы со значениями, превышающими точку поворота, находились после нее. После этапа разделения стержень находится в своем окончательном положении. Свод логически разбивает исходный массив на два подмассива. Затем алгоритм быстрой сортировки рекурсивно сортирует подмассивы, выбирая новую ось и соответствующим образом перемещая значения. Каждый элемент будет выбран в качестве стержня и будет размещен в правильном положении.

Классификация алгоритмов

Следующая таблица содержит информацию об анализе алгоритма быстрой сортировки. Он определяет наихудший, средний и наилучший случаи с точки зрения временной сложности, а также наихудший случай с точки зрения пространственной сложности.

Пожалуйста, используйте следующую ссылку для объяснения обозначения Big-O и того, что хорошо, справедливо и плохо.

Быстрая сортировка На Яве

public final class QuickSort {

    public void sort(int[] collection) {
        if (collection != null) {
            quickSort(collection, 0, collection.length-1);
        } else {
            throw new IllegalArgumentException("Input paramenter for array to sort is null.");
        }
    } 

    private void quickSort(int[] collection, int firstPosition, int lastPosition) {
        if (firstPosition >= lastPosition) {
            return;
        } else {            
            int pivotIndex = partition(collection, firstPosition, lastPosition);
            quickSort(collection, firstPosition, pivotIndex-1);
            quickSort(collection, pivotIndex+1, lastPosition);
        }       
    } 

    private int partition(int[] collection, int firstPosition, int lastPosition) {  
        int pivotIndex = selectPivot(firstPosition, lastPosition);
        swap (collection, pivotIndex, lastPosition);
        int store = firstPosition;
        pivotIndex = lastPosition;
        for (int i = firstPosition; i <= lastPosition-1 ; i++) {
            if (collection[i] <= collection[pivotIndex]) {
                swap (collection, i, store);
                store++;
            }
        }
        swap (collection, store, pivotIndex);
        pivotIndex = store;
        return pivotIndex;
    }   

    private void swap(int[] collection, int x, int y) {
        int temp = collection[x];
        collection[x] = collection[y];
        collection[y] = temp;
    } 

    private int selectPivot(int first, int last) {
        return (first+last)/2;
    } 

} 

Пример кода (GitHub)

Подробную информацию о классе быстрой сортировки можно просмотреть здесь . Подробную информацию о тестовом классе быстрой сортировки JUnit можно просмотреть здесь .

Вывод

Алгоритм быстрой сортировки является частью более крупной группы алгоритмов сортировки. Обучение на основе опыта – вот причина, по которой я создал этот пост о реализации алгоритма быстрой сортировки в Java. Я многое узнал о том, как другие решали алгоритм быстрой сортировки на других языках, включая различные реализации в Java.

Сообщение Алгоритм быстрой сортировки в Java появилось впервые на Код 2 бита .

Оригинал: “https://dev.to/code2bits/quick-sort-algorithm-in-java-2c7j”