Quick Sort
Последнее обновление
Быстрая сортировка — это алгоритм «разделяй и властвуй», который сортирует вокруг «опорного элемента» (pivot). Он выбирает опорный элемент, затем разбивает массив так, чтобы всё меньшее оказалось до него, а всё большее — после, что закрепляет опорный элемент на его окончательной отсортированной позиции. Затем он рекурсивно обрабатывает левую и правую части. Эта визуализация использует схему Ломуто с последним элементом в качестве опорного. Нажмите воспроизведение, чтобы увидеть разбиение и размещение опорного элемента.
Быстрая сортировка обычно является самой быстрой универсальной сортировкой на практике благодаря хорошей работе с кэшем и разбиению на месте, со средней сложностью O(n log n). Её худший случай — O(n²) (например, уже отсортированный массив при плохом выборе опорного элемента), которого позволяют избежать хорошие стратегии выбора опорного элемента, такие как медиана трёх или рандомизация.
Временная и пространственная сложность
| Случай | Сложность | Примечания |
|---|---|---|
| Лучший случай | O(n log n) | Сбалансированные разбиения |
| Средний случай | O(n log n) | Случайный порядок |
| Худший случай | O(n²) | Постоянно несбалансированные опорные элементы |
| Память | O(log n) | Стек рекурсии (разбиение на месте) |
| Устойчивая | Нет | Обмены при разбиении переставляют равные элементы |
Шаг за шагом
| Шаг | Что происходит |
|---|---|
| 1 | Выберите опорный элемент (здесь — последний элемент диапазона). |
| 2 | Разбиение: переместите все элементы меньше опорного влево от него. |
| 3 | Поменяйте опорный элемент на границу — теперь он на своей окончательной позиции. |
| 4 | Рекурсивно примените быструю сортировку к левой части. |
| 5 | Рекурсивно примените быструю сортировку к правой части. |
Разобранный пример
Сортировка [5, 2, 4, 1] по схеме Ломуто (последний элемент — опорный):
| Проход | Массив | Действие |
|---|---|---|
| Начало | [5, 2, 4, 1] | Разбить весь диапазон; опорный элемент — 1 (последний элемент). |
| 1 | [1, 2, 4, 5] | Ничего меньше 1 нет, поэтому меняем 1 на индекс 0; опорный 1 теперь окончателен. Рекурсия вправо по [2, 4, 5]. |
| 2 | [1, 2, 4, 5] | Разбить [2, 4, 5] с опорным 5; и 2, и 4 меньше, поэтому 5 остаётся в конце и окончателен. Рекурсия влево по [2, 4]. |
| 3 | [1, 2, 4, 5] | Разбить [2, 4] с опорным 4; 2 меньше, поэтому 4 остаётся на месте и окончателен. 2 — единственный элемент, поэтому уже отсортирован. |
| Готово | [1, 2, 4, 5] | Каждый опорный элемент закреплён на своём месте; массив отсортирован. |
Когда использовать быструю сортировку
| Используйте, когда | Избегайте, когда |
|---|---|
| Нужна быстрая универсальная сортировка в памяти с малыми константами. | Нужно гарантированное время O(n log n) в худшем случае (используйте пирамидальную или сортировку слиянием). |
Памяти мало — разбиение выполняется на месте и требует лишь O(log n) стека. | Нужна устойчивая сортировка, сохраняющая порядок равных ключей. |
| Данные в случайном или неизвестном порядке, и вы используете случайный опорный элемент или медиану трёх. | Вход уже отсортирован или почти отсортирован, а опорный элемент фиксирован, что вызывает O(n²). |
| Важна локальность кэша, поскольку быстрая сортировка обращается к памяти последовательно. | Вы сортируете связный список, где сортировка слиянием избегает произвольного доступа, на который опирается быстрая сортировка. |
Код Quick Sort
Чистая, готовая к запуску реализация Quick Sort на Python, JavaScript, Java, C++, C. Выберите язык, скопируйте код или откройте его уже загруженным в плейграунде Coddy.
Код Quick Sort на Python
Python
1def quick_sort(a, low=0, high=None):2 if high is None:3 high = len(a) - 14 if low < high:5 p = partition(a, low, high)6 quick_sort(a, low, p - 1)7 quick_sort(a, p + 1, high)8 return a9
10
11def partition(a, low, high):12 # Lomuto partition: everything < pivot moves left of it13 pivot = a[high]14 i = low15 for j in range(low, high):16 if a[j] < pivot:17 a[i], a[j] = a[j], a[i]18 i += 119 a[i], a[high] = a[high], a[i]20 return i21
22
23nums = [10, 7, 8, 9, 1, 5]24print("Before:", nums)25quick_sort(nums)26print("After: ", nums)Код Quick Sort на JavaScript
JavaScript
1function quickSort(a, lo = 0, hi = a.length - 1) {2 if (lo >= hi) return a;3 const p = partition(a, lo, hi);4 quickSort(a, lo, p - 1);5 quickSort(a, p + 1, hi);6 return a;7}8
9// Lomuto partition: last element is the pivot10function partition(a, lo, hi) {11 const pivot = a[hi];12 let i = lo;13 for (let j = lo; j < hi; j++) {14 if (a[j] < pivot) {15 [a[i], a[j]] = [a[j], a[i]];16 i++;17 }18 }19 [a[i], a[hi]] = [a[hi], a[i]];20 return i;21}22
23const data = [5, 2, 9, 1, 7, 3];24console.log("Before:", data);25console.log("Sorted:", quickSort([...data]));Код Quick Sort на Java
Java
1import java.util.Arrays;2
3public class Main {4 static void quickSort(int[] arr, int low, int high) {5 if (low >= high) return;6 int p = partition(arr, low, high);7 quickSort(arr, low, p - 1);8 quickSort(arr, p + 1, high);9 }10
11 // Lomuto partition: last element is the pivot12 static int partition(int[] arr, int low, int high) {13 int pivot = arr[high];14 int i = low - 1;15 for (int j = low; j < high; j++) {16 if (arr[j] < pivot) swap(arr, ++i, j);17 }18 swap(arr, i + 1, high);19 return i + 1;20 }21
22 static void swap(int[] arr, int a, int b) {23 int tmp = arr[a];24 arr[a] = arr[b];25 arr[b] = tmp;26 }27
28 public static void main(String[] args) {29 int[] arr = {10, 7, 8, 9, 1, 5};30 System.out.println("Before: " + Arrays.toString(arr));31 quickSort(arr, 0, arr.length - 1);32 System.out.println("After: " + Arrays.toString(arr));33 }34}Код Quick Sort на C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10// Lomuto partition: place the pivot in its final position11int partition(std::vector<int>& a, int lo, int hi) {12 int pivot = a[hi];13 int i = lo;14 for (int j = lo; j < hi; ++j) {15 if (a[j] < pivot) std::swap(a[i++], a[j]);16 }17 std::swap(a[i], a[hi]);18 return i;19}20
21void quickSort(std::vector<int>& a, int lo, int hi) {22 if (lo >= hi) return;23 int p = partition(a, lo, hi);24 quickSort(a, lo, p - 1);25 quickSort(a, p + 1, hi);26}27
28int main() {29 std::vector<int> data = {10, 7, 8, 9, 1, 5};30 std::cout << "Before: ";31 printVec(data);32 quickSort(data, 0, static_cast<int>(data.size()) - 1);33 std::cout << "After: ";34 printVec(data);35 return 0;36}Код Quick Sort на C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void swap(int* x, int* y) {9 int tmp = *x;10 *x = *y;11 *y = tmp;12}13
14// Lomuto partition: place the pivot in its final position15int partition(int a[], int lo, int hi) {16 int pivot = a[hi];17 int i = lo;18 for (int j = lo; j < hi; j++) {19 if (a[j] < pivot) swap(&a[i++], &a[j]);20 }21 swap(&a[i], &a[hi]);22 return i;23}24
25void quickSort(int a[], int lo, int hi) {26 if (lo >= hi) return;27 int p = partition(a, lo, hi);28 quickSort(a, lo, p - 1);29 quickSort(a, p + 1, hi);30}31
32int main(void) {33 int data[] = {10, 7, 8, 9, 1, 5};34 int n = sizeof(data) / sizeof(data[0]);35 printf("Before: ");36 printArr(data, n);37 quickSort(data, 0, n - 1);38 printf("After: ");39 printArr(data, n);40 return 0;41}Частые вопросы о Quick Sort
Какова временная сложность быстрой сортировки?
Быстрая сортировка в среднем
O(n log n) и O(n log n) в лучшем случае, но деградирует до O(n²) в худшем случае, когда разбиения постоянно несбалансированны. Случайные опорные элементы или медиана трёх делают худший случай крайне маловероятным.Устойчива ли быстрая сортировка?
Нет. Стандартное разбиение на месте меняет местами удалённые элементы, что может изменить относительный порядок равных ключей. Устойчивые варианты существуют, но отказываются от преимущества быстрой сортировки работать на месте.
Почему быстрая сортировка часто быстрее сортировки слиянием?
Быстрая сортировка разбивает на месте с превосходной локальностью кэша и без дополнительного буфера, поэтому её константы малы. Сортировка слиянием достигает той же оценки
O(n log n), но платит буфером O(n) и большим перемещением данных.Быстрая сортировка или сортировка слиянием — что выбрать?
Выбирайте быструю сортировку для быстрой сортировки массивов в памяти на месте, где её малые константы обычно побеждают. Выбирайте сортировку слиянием, когда нужна устойчивая сортировка, гарантированный худший случай
O(n log n) или когда вы сортируете связные списки или внешние данные, не помещающиеся в ОЗУ.Почему быстрая сортировка становится O(n²) на отсортированном массиве?
При фиксированном опорном элементе, таком как первый или последний, уже отсортированный вход приводит к тому, что каждое разбиение отделяет лишь один элемент, создавая
n уровней рекурсии вместо log n. Выбор опорного элемента случайно или методом медианы трёх ломает этот шаблон и восстанавливает поведение O(n log n).В чём разница между схемами разбиения Ломуто и Хоара?
Схема Ломуто использует один индекс, сканирующий слева направо, и её проще кодировать, поэтому эта визуализация использует именно её. Схема Хоара использует два указателя, движущихся навстречу, и обычно делает меньше обменов, что делает её быстрее на практике, но она не помещает опорный элемент на его окончательную позицию на шаге разбиения.
Связанные ресурсы
Больше визуализаций
