Изменения
Новая страница: «'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>...»
'''Сортировка Хана (Yijie Han)''' {{---}} сложный алгоритм сортировки целых чисел со сложностью <tex>O(nlog(logn))</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки.
== Алгоритм ==
Алгоритм построен на основе экспоненциального поискового дерева (далее - Э.П.дерево) Андерсона (<tex>Andersson's exponential search tree</tex>). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
== 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>Andersson's exponential search tree</tex>). Сортировка происходит за счет вставки целых чисел в Э.П.дерево.
== 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>.
