Изменения

Перейти к: навигация, поиск

Сортировка Хана

129 байт добавлено, 01:39, 12 июня 2012
Нет описания правки
Данный алгоритм базируется на следующей лемме:
Номер один.
{{Лемма
|id=lemma1.
==Сортировка на маленьких целых==
Для лучшего понимания действия алгоритма и материала, изложенного в данной статье, в целом, ниже представлены несколько полезных лемм.
Номер два.
{{Лемма
|id=lemma2.
Доказательство данной леммы будет приведено далее в тексте статьи.
}}
Номер три.
{{Лемма
|id=lemma3.
Так как мы можем делать попарное сравнение <tex>g</tex> чисел в одном контейнере с <tex>g</tex> числами в другом и извлекать большие числа из одного контейнера и меньшие из другого за константное время, мы можем упаковать медианы из первого, второго, ..., <tex>g</tex>-ого чисел из 5 контейнеров в один контейнер за константное время. Таким образом набор <tex>S</tex> из медиан теперь содержится в <tex>n/(5g)</tex> контейнерах. Рекурсивно находим медиану <tex>m</tex> в <tex>S</tex>. Используя <tex>m</tex> уберем хотя бы <tex>n/4</tex> чисел среди <tex>n</tex>. Затем упакуем оставшиеся из <tex>n/g</tex> контейнеров в <tex>3n/4g</tex> контейнеров и затем продолжим рекурсию.
}}
Номер четыре.
{{Лемма
|id=lemma4.
Заметим, что когда <tex>g = O(logn)</tex> мы сортируем <tex>O(n)</tex> чисел в <tex>n/g</tex> контейнеров за время <tex>O((n/g)loglogn)</tex>, с использованием O(n/g) места. Выгода очевидна.
Лемма пять.
{{Лемма
|id=lemma5.
Если у нас длина контейнеров больше, сортировка может быть ускорена, как показано в следующей лемме.
 
Лемма шесть.
{{Лемма
|id=lemma6.
81
правка

Навигация