Алгоритм быстрой сортировки (Quick sort) в Java

Алгоритм быстрой сортировки — это один из самых быстрых существующих алгоритмов сортировки (на момент написания данной статьи), который является примером стратегии «разделяй и властвуй». Большинство готовых библиотек и методов по сортировке используют quick sort алгоритм как основу.

Перед тем, как мы перейдем к написанию кода сначала разберемся как именно работает данный алгоритм. К стати говоря, алгоритм быстрой сортировки как и алгоритм сортировки пузырьком в худшем случае работает за время O( $n^2$ ) что довольно медленно. Но не торопитесь делать поспешные выводы. В среднем алгоритм быстрой сортировки выполняется за время O(n logn); причем время сортировки очень зависит от выбора опорного элемента, о котором Вы узнаете далее.

Алгоритм быстрой сортировки — это рекурсивный алгоритм. Как уже было сказано выше quick sort использует стратегию «разделяй и властвуй». Ее суть заключается в том, что задача разбивается на подзадачи до тех пор, пока не будет элементарной единицы. Так и с алгоритмом: массив делится на несколько массивов, каждый из который сортируется по отдельности и потом объединяется в один массив.

Пошаговое описание работы алгоритма быстрой сортировки

Выбрать опорный элемент из массива. Обычно опорным элементом является средний элемент.
Разделить массив на два подмассива: элементы, меньше опорного и элементы, больше опорного.
Рекурсивно применить сортировку к двум подмассивам.

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

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

Исходный массив

Выбор опорного элемента. В данном случае мы взяли первый элемент 3

Разбиваем массив на подмассивы: те, что больше 3 и те, что меньше 3

Проделаем то же самое с левый подмассивом

Выбор опорного элемента

Разбиение на подмассивы

Выбор опорного и разбиение на подмассивы. Не забываем, что мы проделываем эти шаги пока не будет один элемент в подмассиве.

Как видим, левая часть отсортирована. То же самое проделывается и для правой части от опорного элемента 3.

Эти картинки я взял вот отсюда: http://me.dt.in.th/page/Quicksort/. Там Вы найдете завершение для этого массива. Главное, что суть понятна.

Теперь осталось реализовать код. Так, как у нас сайт про Java программирование, то и реализация будет на java. В Интернете очень много реализаций для других языков программирования.

Код

import java.util.Arrays;
 
public class QuickSort {
 
    public static void quickSort(int[] array, int low, int high) {
        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));
    }
}

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

5

Alex:

Ноябрь 12, 2017 в 3:27 пп

познавательно. спасибо))

Ответить
vasya:

Февраль 19, 2018 в 5:36 дп

написанный алгоритм с ошибками, поглядите другие реализации и исправьте свою..

if (i <= j) {//меняем местами — ага, когда i == j многое поменяем?

quickSort(array, low, j);
quickSort(array, i, high); — не лишка ли с i-того то начинать? вообще с j+1

Ответить
1. Я:
  
  Июль 4, 2018 в 12:25 пп
  
  if (array.length == 0)
  return;//завершить
  а есои == 1, то будем сортировать?
  
  Ответить
  1. Vic:
    
    Август 31, 2018 в 11:50 дп
    
    Поведай что такое есои, о разработчик?
    
    Ответить
    1. Alex:
      
      Май 12, 2019 в 7:39 пп
      
      Видимо «Если»
      
      Ответить