Лексикографическая или поразрядная сортировка — быстрый и устойчивый алгоритм сортировки за линейное время, использовалась в устройствах для сортировки перфокарт. Пригодна для сортировки любых элементов, состоящих из цепочек над фиксированным алфавитом, на котором задано отношение сравнения. Для сортировки следует применять любой устойчивый алгоритм, используя в качестве ключа сначала младшую букву, затем повторять этот процесс для более старших букв. Сложность алгоритма: O(n·k); требуется O(n) дополнительной памяти сортирует строки буква за буквой.
Реализация на С++
function pass(a, N, dig) // e.g. in JavaScript //A C 1 // pre: a[1..N] is sorted on digits [dig-1..0] l o 9 // post: a[1..N] is sorted on digits [dig..0] g m 9 { var counter = new Array(11); // for digit occurrences p 9 var temp = new Array(); //D . var i, d; //S S // c for( d = 0; d <= 9; d++ ) counter[d] = 0; // i for( i = 1; i <= N; i++ ) counter[ digit(a[i], dig) ] ++; for( d = 1; d <= 9; d++ ) counter[d] += counter[d-1];
for( i = N; i >= 1; i-- ) { temp[ counter[ digit(a[i], dig) ] -- ] = a[i]; }
for( i = 1; i <= N; i++ ) a[i] = temp[i]; }//pass
function radixSort(a, N) { var p; for( p=0; p < NumDigits; p++ ) pass(a, N, p); }//radixSort
Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.2.5: Sorting by Distribution, pp.168–179.
Efficient Trie-Based Sorting of Large Sets of Strings,
by Ranjan Sinha and Justin Zobel. This paper describes a method of
creating tries of buckets which figuratively burst into sub-tries when
the buckets hold more than a predetermined capacity of strings, hence
the name, "Burstsort."
