Изменения

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

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

140 байт добавлено, 19:55, 18 мая 2014
Определения
==Определения==
# {{ Определение | definition = '''Контейнер ''' {{---}} объект, в которым хранятся наши данные. Например: 32-битные и 64-битные числа, массивы, вектора.}}# {{ Определение | definition = Алгоритм, сортирующий <tex>n</tex> целых чисел из множества <tex>\{0, 1, \ldots, m - 1\}</tex>, называется '''консервативным''', если длина контейнера (число бит в контейнере) равна <tex>O(\log(m + n))</tex>. Если длина больше, то алгоритм '''неконсервативный'''.# }}{{ Определение | definition = Если сортируются целые числа из множества <tex>\{0, 1, \ldots, m - 1\}</tex> с длиной контейнера <tex>k \log (m + n)</tex> с <tex>k</tex> <tex>\ge</tex> 1, тогда сортировка происходит с '''неконсервативным преимуществом ''' <tex>k</tex>.# }}{{ Определение | definition = Для множества <tex>S</tex> определим
<tex>\min(S) = \min\limits_{a \in S} a</tex>
Набор <tex>S1</tex> < <tex>S2</tex> если <tex>\max(S1) \le \min(S2)</tex>
# }}{{ Определение | definition = Предположим, есть набор <tex>T</tex> из <tex>p</tex> чисел, которые уже отсортированы как <tex>a_{1}, a_{2}, \ldots, a_{p}</tex>, и хочется использовать числа в <tex>T</tex> для разделения набора набор <tex>S</tex> из <tex>q</tex> чисел <tex>b_{1}, b_{2}, \ldots, b_{q}</tex> в . Тогда '''разделением''' <tex>q</tex> чисел <tex>p</tex> числами называется <tex>p + 1</tex> наборов набор <tex>S_{0}, S_{1}, \ldots, S_{p}</tex>, таких что где <tex>S_{0}</tex> < {<tex>a_{1}</tex>} < <tex>S_{1}</tex> < <tex>\ldots</tex> < {<tex>a_{p}</tex>} < <tex>S_{p}</tex>. Назовем это разделением <tex>q</tex> чисел <tex>p</tex> числами.}}
==Сортировка с использованием O(n log log n) времени и памяти==
38
правок

Навигация