Стр. 101 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
99
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Пример:
Ищем 5 – е наименьшее.
27 99 00 08 13 64 86 16 07 10 88 25 90 – начальный массив, ГЭ – 27.
16 25 00 08 13 10 07 27 86 64 88 99 90
16 25 00 08 13 10 07 – ГЭ - 16
10 07 00 08 13 16 25
10 07 00 08 13
08 07 00 10 13
13
Алгоритм быстрой сортировки для отыскания
k
– го наибольшего
QuickSort(x,h,l,k) // h – верхняя, l – нижняя
{
if (h>=l) return;
i=h+1;
while((x
i
<x
h
)
&&
(i<=l)) i=i+
1
;
j=l;
while((x
j
>x
h
)
&&
(j>=h)) j=j-
1
;
while(i<j)
{
<x
i
меняем местами с x
j
>
i=i+
1
;
while((x
i
<x
h
)
&&
(i<=l)) i=i+
1
;
j=j-
1
;
while((x
j
>x
h
)
&&
(j>=h)) j=j-
1
;
}
<x
h
меняем местами с x
j
> // меняем верхнюю границу
//с j-м элементом
if(k==j) return; //успех
if(k<j) QuickSort(x,h,j-
1
,k);
if(k>j) QuickSort(x,j+
1
,l,k);}
