Метод быстрой сортировки в Java (Quick sort)

Быстрая сортировка является одной из наиболее эффективных из существующих в Java. В её основе лежит рекурсивный алгоритм Quick sort. В среднем сортировка в Java выполняется за время O(n logn), причём точная скорость зависит от выбора опорного элемента.

Принято считать, что алгоритм быстрой сортировки Quick sort использует известную стратегию «разделяй и властвуй». Речь идёт о том, чтобы разбивать задачу на подзадачи до той поры, пока перед нами не будет элементарная единица. В нашем случае массив делится на несколько массивов, а каждый из них сортируется отдельно, а потом объединяется в один массив.

Как работает быстрая сортировка в Java

Пошаговое описание алгоритма сортировки: 1.Выбираем опорный элемент из массива. Как правило, это средний элемент. 2.Делим массив на 2 подмассива. Элементы, которые меньше опорного, и элементы, которые больше опорного. 3.Рекурсивно применяем сортировку к обоим подмассивам.

В результате массивы будут делиться до тех пор, пока не останется один элемент, который потом отсортируется. Для наглядности смотрим анимацию и картинки ниже:

Анализ алгоритма быстрой сортировки

Исходный массив: Выбираем опорный компонет, берём 3: Теперь разобьём массив на подмассивы: те, что больше трёх и те, что меньше: То же сделаем с левым подмассивом: Выбираем опорный элемент: Разбиваем на подмассивы: Выбираем опорный компонент и выполняем разбиение на подмассивы. Проделываем это, пока в подмассиве не останется один элемент. Левая часть отсортирована. То же делается и для правой части, начиная от опорного элемента 3.

Что же, осталось реализовать java-код.

import java.util.Arrays;

    public class QuickSort {

        public static void quickSort(int[] array, int low, inthigh) {
            if (array.length == 0)
                return;//завершить выполнение, если длина массива равна 0

            if (low >= high)
                return;//завершить выполнение если уже нечего делить

            // выбрать опорный элемент
            int middle = low + (high - low) / 2;
            int opora = array[middle];

            // разделить на подмассивы, который больше и меньше опорного элемента
            int i = low, j = high;
            while (i <= j) {
                while (array[i] < opora) {
                    i++;
                }

                while (array[j] > opora) {
                    j--;
                }

                if (i <= j) {//меняем местами
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    i++;
                    j--;
                }
        }

        // вызов рекурсии для сортировки левой и правой части
            if (low < j)
            quickSort(array, low, j);

        if (high > i)
                quickSort(array, i, high);
        }
        public static void main(String[] args) {
            int[] x = { 8, 0, 4, 7, 3, 7, 10, 12, -3 };
            System.out.println("Было");
            System.out.println(Arrays.toString(x));

            int low = 0;
            int high = x.length - 1;

       quickSort(x, low, high);
            System.out.println("Стало");
        System.out.println(Arrays.toString(x));
    }
    }

Мы рассмотрели алгоритм, благодаря которому реализуется быстрая сортировка в Java. В заключение скажем, что Quick sort — это действительно эффективный способ, идеально подходящий даже для сортировки больших массивов.

Хотите узнать о Java-программировании больше? Записывайтесь на наш курс «Разработчик Java»!