Изменения

Перейти к: навигация, поиск

Быстрая сортировка

6 байт убрано, 00:12, 13 июня 2016
Алгоритм
==Алгоритм==
* Массив <tex> A[l \ldots r]</tex> разбивается на два (возможно пустых) подмассива <tex> A[l \ldots q-1]</tex> и <tex> A[q+1 \ldots r]</tex>, таких, что каждый элемент <tex> A[l \ldots q-1]</tex> меньше или равен <tex> A[q]</tex>, который в свою очередь, не превышает любой элемент подмассива <tex> A[q+1 \ldots r]</tex>. Индекс вычисляется в ходе процедуры разбиения.* Подмассивы <tex> A[l \ldots q-1]</tex> и <tex> A[q+1 \ldots r]</tex> сортируются с помощью рекурсивного вызова процедуры быстрой сортировки.
* Поскольку подмассивы сортируются на месте, для их объединения не требуются никакие действия: весь массив <tex> A[l \ldots r]</tex> оказывается отсортированным.
635
правок

Навигация