Один из самых быстрых известных универсальных алгоритмов сортировки. В среднем O(n log(n)) обменов при упорядочивании n элементов.
Общее описание алгоритма:
- Выбирается элемент каким-либо образом. Существуют разные способы выбора элемента, но алгоритм работает с любым выбранным элементом. Это может быть самый первый, либо самый последний элемент массива, либо элемент где-то посередине. Этот элемент называется опорным.
- Элементы в массиве перемещаются так, что элементы меньше опорного оказываются слева от него, а элементы больше опорного — справа.
- К подмассивам слева и справа от опорного применяются первые два шага, если в этих подмассивах больше одного элемента.
От выбора опорного элемента работоспособность алгоритма не ломается, но может ухудшаться или улучшаться производительность. Может выбираться первый элемент, или последний, или средний и т. д.
Реализуем этот алгоритм на Java.
Внимание! Не стоит реализовывать этот алгоритм в реальных проектах. Всегда используйте готовые алгоритмы сортировки коллекций и готовые алгоритмы из класса java.util.Arrays.
Код на Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
import java.util.Arrays; /** * Пример обучающей программы с реализацией быстрой сортировки Quicksort * @see https://urvanov.ru */ public class Main { public static void main(String [] args) { int [][] array1 = { {9, 0, -2, 89, 1, 2, 3, -3, -99, 6}, {5, 3, 1, 2, 2, 1, 0}, {1, 1}, {3, 1, 1}, {2, 1, 1, 2, 1, 2}, {2, 5, 3, 1}, {-1, 3, 2, 4, 0, 1}, {-1, 0} }; sortAndPrintln(array1); } public static void sortAndPrintln(int[][] array1) { for (int n = 0; n < array1.length; n++) { quicksort(array1[n], 0, array1[n].length - 1); System.out.println(Arrays.toString(array1[n])); } } /** * Реализуем алгоритм быстрой сортировки * @param array1 Массив, в котором нужно упорядочить элементы. * @param startIndex Начальный индекс в массиве (включая). * @param endIndex Конечный индекс в массиве (не включая) */ public static void quicksort(int[] array1, int startIndex, int endIndex) { int pivotValue = getPivot(array1, startIndex, endIndex); int currentStartIndex = startIndex; int currentEndIndex = endIndex; while (currentStartIndex < currentEndIndex) { while (array1[currentStartIndex] < pivotValue) { currentStartIndex++; } while ((array1[currentEndIndex] > pivotValue) && (currentEndIndex > currentStartIndex)) { currentEndIndex--; } if (currentStartIndex < currentEndIndex) { swap(array1, currentStartIndex, currentEndIndex); if (currentEndIndex - currentStartIndex > 1) { currentStartIndex++; currentEndIndex--; } else { break; } } } if ((currentStartIndex > startIndex) && (currentStartIndex - startIndex > 1)) quicksort(array1, startIndex, currentStartIndex); if ((endIndex > currentEndIndex) && (endIndex - currentEndIndex > 1)) quicksort(array1, currentEndIndex , endIndex); } /** * Меняет местами элементы массива с индексами index1 и index2. * @param array1 Массив. * @param index1 Индекс элемента 1. * @param index2 Индекс элемента 2. */ private static void swap(int[] array1, int index1, int index2) { int buffer = array1[index1]; array1[index1] = array1[index2]; array1[index2] = buffer; } /** * * @param array1 * @param lowIndex * @param highIndex * @return Значение опорного элемента. В этой реализации опорный элемент - * это последний элемент в массиве. */ public static int getPivot(int[] array1, int startIndex, int endIndex) { return array1[endIndex - 1]; } } |
Достоинства алгоритма:
- Достаточно прост.
- Довольно быстр.
- Допускает распараллеливание, так как подмассивы могут сортироваться параллельно.
- Можно использовать для связанных списков.
Недостатки:
- При неудачных входных данных может дать до O(n²) по скорости (если исходный массив уже отсортирован)
- Если делать прямую реализацию с рекурсивными вызовами, то может привести к переполнению стека.
- Неустойчив, так как меняет порядок равных элементов.
Вас также может заинтересовать сортировка слиянием и сортировка вставками.
Весь код выложен в репозиторий на GitHub (ставьте звёздочки).
В этой реализации есть ошибка, если прогнать такой массив: {5,3,1,2,2,1,0}, то он застрянет в последнем шаге на 1-ом и 2-ом индексах бесконечно меняя единицы местами.
Спасибо за найденную ошибку. Исправил и выложил новую версию.
Массив {2, 5, 3, 1} сортируется неправильно. Исходящий массив: {2, 1, 3, 5}
Исправил, спасибо за найденную ошибку.