Добавить комментарий

Delphi

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

Дальнейшее развитие сортировки выбором. Элементы исходной выборки уложим в структуру данных Двоичная куча, а потом извлечём обратно по одному из корневого элемента.

type
  TAI = array of integer;
...
procedure HeapSort(var A: TAI);
var
    bh : TBinaryHeap;
    i : integer;
begin
  // Создаём класс двоичной кучи
  //  с элементами типа Integer
    bh := TBinaryHeap.Create(A,
  // Описываем функцию сравнения элементов
            TComparer.Construct(
              function(const A, B: integer): integer
              begin
                Result := Sign(A - B);
              end
            )
          );
  // Исходный массив A сразу загружен и отсортирован в соответствии
  //  со свойствами двоичной кучи max-heap
  // Осталось только извлечь элементы
    for I := High(A) downto Low(A) do
      A[i] := bh.ExtractMax;
  // Массив отсортирован по возрастанию.
    bh.Free;
end;

Сложность:

Максимальная O(N log(N))
Минимальная O(N log(N))
Средняя O(N log(N))

 

Filtered HTML

  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Допустимые HTML-теги: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Строки и абзацы переносятся автоматически.
  • Вы можете цитировать другие сообщения, используя тэг [quote]

Plain text

  • HTML-теги не обрабатываются и показываются как обычный текст
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и абзацы переносятся автоматически.