Изменения

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

Карманная сортировка

2 байта добавлено, 13:44, 12 июня 2012
Нет описания правки
Существует несколько разных реализаций карманной сортировки.
==== Рекурсивный bucket sort ====
Рассмотрим код работы рекурсивной реализации карманной сортировки, на вход которой подаются строки длины <tex> p </tex>вещественные числа.
<wikitex>
// j - the current index in string //base = 256 Bucketsort (array, jmin_element,max_element){ if (array.length < 2 || j min_element == p + 1max_element ) return array; initialize buckets <- new array of n empty lists initialize buckets_minimum initialize buckets_maximum for i = 0 to array.length - 1 index = int(array[i] * num_buckets / range) insert array[i] at end buckets[partition index] buckets_minimum[i] = minimum (arraybuckets[index], arra[i]) buckets_maximum[i] = maximum ( buckets[index], jarra[i])] for i = 0 to base num_buckets - 1 buckets[i] = Bucketsort (buckets[i],j+1min_bucktes[i],max_buckets[i]) intialize answer for i = 0 to base buckets_num - 1 for k = 0 to buckets[i].length - 1 insert buckets[i][k] аt end answer return answer } fuction partition( string s, j) return int(s[j])
</wikitex>
base {{---}} основание системы счисления, в случае со строками base <tex> = 256</tex>.
==== Нерекурсивная реализация ====
<wikitex>
42
правки

Навигация