Сортировка кучей(Heap Sort)

Сортировки   13 Март 2012  Автор статьи:  

Сортировка кучей или пирамидальная сортировка(англ HeapSort) является сортировкой, основанной на сравнениях. Эта сортировка обладет следующими свойствами:

  • нерекурсивная
  • нестабильная (т.е. не сохраняет исходный порядок данных с одинаковым ключом)
  • является асимптотически нормальной(т.е. работает за оптимальное для сортировки время — O(n logn)), однако не очень быстрая в серднем случае и на отсортированных или почти отсортированных данных)

Алгоритм основан на одном из свойств кучи — в голове(или вершине) кучи находится самый максимальный элемент.

Алгоритм

  1. Построим из требуемого массива кучу
  2. Меняем местами первый и последний элемент в куче
  3. Уменьшаем размер рассматриваемой кучи на 1
  4. Вызвать процедуру нормализации кучи(heapify) в корне кучи
  5. Вернуться в шаг 2 и продолжать выполнять алгоритм, пока куча имеет больше одного элемента

Так как heapyfy работает за O(logn), а функция вызывается столько, сколько элементов массиве, то асимптотическая сложность алгоритма будет составлять O(n logn). Однако, на всех вариантах, даже на полностью отсортированном массиве, время работы алгоритма будет максимальным. Именно поэтому сортировка кучей не используется в стандартных пакетах.

Научиться программировать

  • на Delphi

  • на Java

  • на C++