Сортировка Хана — различия между версиями
(Новая страница: «'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>...») |
|||
| Строка 2: | Строка 2: | ||
== Алгоритм == | == Алгоритм == | ||
| − | Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона ( | + | Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево. |
== Andersson's exponential search tree == | == Andersson's exponential search tree == | ||
Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> Э.П.поддеревьев (<tex>0<e<1</tex>), в каждом из которых <tex>n^(1-e)</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>. | Э.П.дерево с <tex>n</tex> листьями состоит из корня <tex>r</tex> и <tex>n^e</tex> Э.П.поддеревьев (<tex>0<e<1</tex>), в каждом из которых <tex>n^(1-e)</tex> листьев; каждое Э.П.поддерево является сыном корня <tex>r</tex>. | ||
Версия 20:28, 10 июня 2012
Сортировка Хана (Yijie Han) — сложный алгоритм сортировки целых чисел со сложностью , где — количество элементов для сортировки.
Алгоритм
Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (Andersson's exponential search tree). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
Andersson's exponential search tree
Э.П.дерево с листьями состоит из корня и Э.П.поддеревьев (), в каждом из которых листьев; каждое Э.П.поддерево является сыном корня .
