В цикле инвариант сохраняется с помощью двух операций. Поскольку элемент х[1] является наибольшим среди первых i элементов, перестановка его с i-м элементом добавляет к упорядоченной последовательности еще один элемент. Эта перестановка нарушает свойство кучи, которое восстанавливается просеиванием нового верхнего элемента вниз. Код, выполняемый на втором этапе, приведен в листинге 14.9.
Листинг 14.9. Второй этап сортировки heapsort: формирование упорядоченной последовательности
for (1 = n; i >= 2; т - - )
/* heap(1. i) && sorted(i+l. n) && х[1 .i] <= x[i+l, n] */ swap(1. i )
/* heap(2. I-I) && sorted(i. n) && x[l i-l] <= x[i n] */ s i ftdown(i-1)
/* heap(l. i-I) && sorted(i, n) && x[l i-l] <= x[i n] */
Теперь, с готовыми функциями, мы можем записать весь алгоритм сортировки heapsort в пять строк (листинг 14.10).
Листинг 14.10. Алгоритм сортировки с помощью кучи (heapsort)
for i = [2. п]
S 1 ft U р ( 1 ) for (i = п. i >= 2 ; i - -) swap( 1. i ) siftdown(i-1)
Поскольку в алгоритме выполняется по п-1 вызовов siftup и siftdown, каждый из которых работает не медленнее, чем за 0(\ogn)f программа целиком работает за время 0(п log п) даже в худшем случае.
В решениях задач 2 и 3 описаны методы, позволяющие ускорить (и упростить) алгоритм сортировки с помощью кучи (heapsort). Хотя этот алгоритм гарантирует хорошую скорость в худшем случае — 0(nlogn) — самый быстрый вариант его реализации работает обычно медленнее, чем простой алгоритм быстрой сортировки из раздела 11.2 главы 11.
Опубликовал vovan666
April 17 2013 00:04:26 ·
0 Комментариев ·
3240 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
