Метод быстрой сортировки в Java (Quick sort) | OTUS
⚡ Подписка на курсы OTUS!
Интенсивная прокачка навыков для IT-специалистов!
Подробнее

Курсы

Программирование
Python Developer. Professional
-3%
Разработчик на Spring Framework
-5%
iOS Developer. Professional
-8%
Golang Developer. Professional
-6%
Базы данных
-12%
Agile Project Manager
-5%
Android Developer. Professional
-11%
Microservice Architecture
-5%
C++ Developer. Professional
-5%
Highload Architect
-6%
JavaScript Developer. Basic
-8%
Backend-разработчик на PHP
-9%
Разработчик IoT
-13%
PostgreSQL
-8%
Подготовка к сертификации Oracle Java Programmer (OCAJP) Framework Laravel Cloud Solution Architecture Reverse-Engineering. Professional Архитектура и шаблоны проектирования Node.js Developer Интенсив «Оптимизация в Java» Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes iOS Developer. Basic Супер-интенсив «СУБД в высоконагруженных системах» Супер-интенсив "Tarantool"
Инфраструктура
DevOps практики и инструменты
-12%
Базы данных
-12%
Network engineer. Basic
-10%
Network engineer
-4%
Экcпресс-курс «ELK»
-10%
Инфраструктурная платформа на основе Kubernetes
-6%
Administrator Linux.Basic
-10%
Экспресс-курс «CI/CD или Непрерывная поставка с Docker и Kubernetes»
-30%
Дизайн сетей ЦОД
-13%
PostgreSQL
-8%
Разработчик программных роботов (RPA) на базе UiPath и PIX Reverse-Engineering. Professional Внедрение и работа в DevSecOps Administrator Linux. Advanced Infrastructure as a code in Ansible Супер - интенсив по паттернам проектирования Супер - интенсив по Kubernetes Экспресс-курс «IaC Ansible»
Специализации Курсы в разработке Подготовительные курсы
+7 499 938-92-02

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

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

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

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

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

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

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

Исходный массив: 1.jpg-20219-c46f39.png Выбираем опорный компонет, берём 3: 2.jpg-20219-72edab.png Теперь разобьём массив на подмассивы: те, что больше трёх и те, что меньше: 3.jpg-20219-1adaa3.png То же сделаем с левым подмассивом: 4.jpg-20219-8232b9.png Выбираем опорный элемент: 5.jpg-20219-98d089.png Разбиваем на подмассивы: 6.jpg-20219-cd9859.png Выбираем опорный компонент и выполняем разбиение на подмассивы. Проделываем это, пока в подмассиве не останется один элемент. 7.jpg-20219-233490.png Левая часть отсортирована. То же делается и для правой части, начиная от опорного элемента 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»!

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться