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

quick sort algorithm

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

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

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

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

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

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

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

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

1 шаг

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

2 шаг

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

3 шаг

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

4 шаг

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

5 шаг

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

6 шаг

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

7 шаг

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

Как видим, левая часть отсортирована. То же самое проделывается и для правой части от опорного элемента 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));
    }
}

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

Понравилась статья? Поделиться с друзьями:
Комментарии: 7
  1. Alex

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

  2. vasya

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

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

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

    1. Я

      if (array.length == 0)
      return;//завершить
      а есои == 1, то будем сортировать?

      1. Vic

        Поведай что такое есои, о разработчик?

        1. Alex

          Видимо «Если»

  3. Саша

    Добрый день, есть ощущение, что в условие на строке 9 никогда не попадёт
    if (low >= high)
    Из-за условия на строках 37 и 40

  4. Анна

    спасибо! Все работает

Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: