76
правок
Изменения
Нет описания правки
* Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее.
* Рекурсивно сотрируем "маленькие" и "большие" элементы.
var
a : array [ 1 . .N] of integer ;
procedure QSort ( left , right : integer ) ;
var
i , j : integer ;
key : integer ;
buf : integer ;
begin
key := a [ random ( right - left + 1) + left ] ;
i := left ;
j := right ;
repeat
while a [ i ] < key do
inc ( i ) ;
while key < a [ j ] do
dec ( j ) ;
if i <= j then begin
buf := a [ i ] ;
a [ i ] := a [ j ] ;
a [ j ] := buf ;
inc ( i ) ;
dec ( j ) ;
end ;
unti l i > j ;
if l e f t < j then
QSort ( l e f t , j ) ;
if i < r i g h t then
QSort ( i , r i g h t ) ;
end ;
begin
. . .
QSort ( 1 , N) ;
end .
===Оптимизация глубины рекурсии до O(logn) в худшем случае===
