Методы сортировок Опции

[virt]

Описание и реализация алгоритмов:

• Пузырьковая сортировка (простым выбором, простым обменом, линейная)
• Пузырьковая сортировка с просеиванием
• Сортировка простой вставкой
• Сортировка слияниями
• Быстрая сортировка Хоара
• Пирамидальная - турнирная - HeapSort сортировка
• Распределяющая сортировка - RadixSort - цифровая - поразрядная
• Древесная сортировка (TreeSort)
• Сортировка методом поиска нового номера
• Метод последовательного поиска минимумов

****** ******

Сравнительная скорость работы некоторых нижеприведенных алгоритмов сортировки:



Примечание:

size: размер сортируемой последовательности
n: количество сортировок для замера времени
*: RadixSort в последнем тесте прогонялся при параметрах: size=21000; n=100

[volvo]

Пирамидальная - турнирная - HeapSort сортировка

Скачать:  HIP_SORT.PAS ( 1.27 килобайт ) Кол-во скачиваний: 2203

Type
  arrType = Array[1 .. n] Of Integer;

Procedure HeapSort(Var ar: arrType; n: Integer);
Var
  i, Left, Right: integer;
  x: Integer;

  Procedure sift;
  Var i, j: Integer;
  Begin
    i := Left; j := 2*i; x := ar[i];
    While j <= Right Do Begin
      If j < Right Then
        If ar[j] < ar[Succ(j)] Then Inc(j);

      If x >= ar[j] Then Break;
      ar[i] := ar[j];
      i := j; j := 2 * i
    End;

    ar[i] := x
  End;

Var T: Integer;
Begin
  Left := Succ(n div 2); Right := n;
  While Left > 1 Do Begin
    Dec(Left); sift
  End;

  While Right > 1 Do Begin
    T := ar[ Left ]; ar[ Left ] := ar[ Right ]; ar[ Right ] := T;
    Dec(Right); sift
  End
End;

Сложность O(n*logn), самая стабильная сортировка, на любых входных данных работает за одинаковое время. Но зато немного медленнее чем слияниями и быстрая.