Алгоритм быстрой сортировки – это один из самых быстрых существующих алгоритмов сортировки (на момент написания данной статьи), который является примером стратегии “разделяй и властвуй”. Большинство готовых библиотек и методов по сортировке используют quick sort алгоритм как основу.
Перед тем, как мы перейдем к написанию кода сначала разберемся как именно работает данный алгоритм. К стати говоря, алгоритм быстрой сортировки как и алгоритм сортировки пузырьком в худшем случае работает за время O() что довольно медленно. Но не торопитесь делать поспешные выводы. В среднем алгоритм быстрой сортировки выполняется за время O(n logn); причем время сортировки очень зависит от выбора опорного элемента, о котором Вы узнаете далее.
Алгоритм быстрой сортировки – это рекурсивный алгоритм. Как уже было сказано выше quick sort использует стратегию “разделяй и властвуй”. Ее суть заключается в том, что задача разбивается на подзадачи до тех пор, пока не будет элементарной единицы. Так и с алгоритмом: массив делится на несколько массивов, каждый из который сортируется по отдельности и потом объединяется в один массив.
Пошаговое описание работы алгоритма быстрой сортировки
- Выбрать опорный элемент из массива. Обычно опорным элементом является средний элемент.
- Разделить массив на два подмассива: элементы, меньше опорного и элементы, больше опорного.
- Рекурсивно применить сортировку к двум подмассивам.
В результате таких действий рекурсии, программа дойдет до того, что массивы будут делиться пока не будет один элемент, который потом и отсортируется. Звучит немного запутано и странно. Для наглядности посмотрите анимацию и картинки ниже.
Подробный анализ алгоритма быстрой сортировки
Исходный массив
Выбор опорного элемента. В данном случае мы взяли первый элемент 3
Разбиваем массив на подмассивы: те, что больше 3 и те, что меньше 3
Проделаем то же самое с левый подмассивом
Выбор опорного элемента
Разбиение на подмассивы
Выбор опорного и разбиение на подмассивы. Не забываем, что мы проделываем эти шаги пока не будет один элемент в подмассиве.
Как видим, левая часть отсортирована. То же самое проделывается и для правой части от опорного элемента 3.
Эти картинки я взял вот отсюда: http://me.dt.in.th/page/Quicksort/. Там Вы найдете завершение для этого массива. Главное, что суть понятна.
Теперь осталось реализовать код. Так, как у нас сайт про Java программирование, то и реализация будет на java. В Интернете очень много реализаций для других языков программирования.
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));
}
}
Это все об алгоритме быстрой сортировки. Это очень быстрый и эффективный алгоритм, который идеально подходит для сортировки больших массивов. Он может быть немного сложным к восприятию и реализации. Не переживайте, если не поняли его с первого раза. Перечитайте статью еще раз и главное поймите смысл работы, а реализацию всегда можно найти в сети.
познавательно. спасибо))
написанный алгоритм с ошибками, поглядите другие реализации и исправьте свою..
if (i <= j) {//меняем местами — ага, когда i == j многое поменяем?
quickSort(array, low, j);
quickSort(array, i, high); — не лишка ли с i-того то начинать? вообще с j+1
if (array.length == 0)
return;//завершить
а есои == 1, то будем сортировать?
Поведай что такое есои, о разработчик?
Видимо “Если”
Добрый день, есть ощущение, что в условие на строке 9 никогда не попадёт
if (low >= high)
Из-за условия на строках 37 и 40
спасибо! Все работает