Алгоритим быстрой сортировки массива



Автор: Dimka Maslov
WEB-сайт: http://delphibase.endimus.com

{ **** UBPFD *********** by delphibase.endimus.com ****
>> Алгоритим быстрой сортировки массива
Функция, показывающая пример реализации алгоритма быстрой сортировки
целочисленного массива. Легко может быть переработан для массивов
другого типа или объектов типа TList, TStringList и т. д.
Используемые параметры
IntArray - указатель на первый элемент массива. ВАЖНО! Индекс первого элемента
массива обязательно должен быть нулевым.
Low - минимальный индекс элемента массива
High - максимальный индекс элемента массива
Зависимости: нет
Автор:       Dimka Maslov, [email protected], ICQ:148442121, Санкт-Петербург
Copyright:   http://www.rsdn.ru/article/?alg/bintree/sort.xml
Дата:        21 мая 2002 г.
***************************************************** }
type
PIntArray = ^TIntArray;
TIntArray = array[0..0] of Integer;
procedure QuickSort(IntArray: PIntArray; Low, High: Integer);
procedure Swap(Index1, Index2: Integer);
var
N: Integer;
begin
N := IntArray[Index1];
IntArray[Index1] := IntArray[Index2];
IntArray[Index2] := N;
end;
var
Mid: Integer;
Item: Integer;
ScanUp, ScanDown: Integer;
begin
// Здесь реализована сортировка по убыванию
// Для реализации по возрастанию замените операции
// сравнения на приведённые в комментариях
if High - Low <= 0 then
exit;
if High - Low = 1 then
begin
if IntArray[High] {<} > IntArray[Low] then
Swap(Low, High);
Exit;
end;
Mid := (High + Low) shr 1;
Item := IntArray[Mid];
Swap(Mid, Low);
ScanUp := Low + 1;
ScanDown := High;
repeat
while (ScanUp <= ScanDown) and (IntArray[ScanUp] {<=} >= Item) do
Inc(ScanUp);
while (IntArray[ScanDown] {>} < Item) do
Dec(ScanDown);
if (ScanUp < ScanDown) then
Swap(ScanUp, ScanDown);
until (ScanUp >= ScanDown);
IntArray[Low] := IntArray[ScanDown];
IntArray[ScanDown] := Item;
if (Low < ScanDown - 1) then
QuickSort(IntArray, Low, ScanDown - 1);
if (ScanDown + 1 < High) then
QuickSort(IntArray, ScanDown + 1, High);
end;

Пример использования:

procedure TForm1.Button1Click(Sender: TObject);
var
A: array[0..10] of Integer;
i: Integer;
begin
Randomize;
for i := 0 to 10 do
A[i] := Random(1000);
QuickSort(@A, 0, 10);
for i := 0 to 10 do
Memo1.Lines.Add(IntToStr(A[i]));
end;

Далее: Быстрая сортировка »»