42
правки
Изменения
Нет описания правки
Base - основание системы счисления в случае со строками Base = 256.
Приведенный код, работает не только для строк , а в принципе для любых объектов для которых можно определить порядок, систему счисления и функцию partition.
==Асимптотика==
Пусть <tex>n</tex> — количество элементов в массиве, <tex>k</tex> — основание системы исчисления и <tex>p</tex> — количество разрядов в объекте.
Тогда алгоритм "Bucket sort" в процессе работы, сделает не более чем <Tex>O(p * (n + k))</Tex> итераций.
Заметим ,что в случае случайного распределения мат. ожидания количество элементов в каждом блоке <tex> n/k</tex>. Следовательно в средним алгоритм "карманной сортировки" совершает <Tex>O(n * log_k n)</Tex> действий.При этом на некотором множестве наборов, где <tex> k = O(n)</tex> , алгоритм отработает за линейное время.
