void shell sort()
for (h = l.h<n. h = 3*h + l)
if (h < 1) break for i = [h, n)
for (j = l, j >= h. j -= h) if С x [ j - h ] < x [ j ]) break swap(j-h, j)
9. Приведенный ниже алгоритм выбора принадлежит Хоару. Он представляет собой слегка измененную версию qsort4:
void select1(1 . u. k)
предусловие 1 <= k <= u
постусловие x[1 k-1] <= x[k] <= x[k + l u] if 1 >= u retu rn swap(1, randint(1 . u )) t = x[1]; i = 1. j = u +1 1 oop
do i++. while i <= u && x[i] < t do j- -, whi1e x[j] > t if i > J break
temp = x[i]. x[i] = x[j]. x[j] = temp swap(1. j)
if J < k
select1(j+1. u. k) else if j > k
select 1 (1 . j-1, k)
Поскольку рекурсивный вызов стоит в конце функции, ее можно преобразовать в цикл while. В задаче 5.2.2-32 тома «Сортировка и поиск» Д. Кнут показывает, что в среднем такая программа находит медиану п элементов за 3,4л сравнений. Вычисление ведется в том же духе, что и для худшего случая в решении задачи 1 из раздела 2.1 главы 2.
Опубликовал vovan666
April 17 2013 00:06:56 ·
0 Комментариев ·
2654 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.