|
Invisible |
|
|
Скажите в чем разница между двумя видами сортировок:
Цифровая сортировка и Сортировка подсчётом
вроде по описанию схоже
в чем разница между ними ? 
|
|
|
|
 |
|
maxal |
|
|
|
Разница в том, что в "сортировке подсчётом" сначала строится массив индексов элементов в отсортированном массиве и только потом элементы перемещаются в результирующий массив, согласно построенным индексам. При этом массив индексов проиндексирован значениями данных элементов, и их разброс должен быть мал.
В то же время, "цифровая сортировка" является частным случаем "блочной сортировки" и в ней предполагается наличие у каждого элемента массива еще и числового ключа, величина которого не убывает с ростом значений элементов. На первом проходе элементы массива помещаются в новый массив "корзин" (или "блоков"), согласно значениям своих ключей. При этом возможно, что в одну и ту же корзину попадет несколько элементов исходного массива (имеющих один и тот же ключ). На втором проходе корзины последовательно обрабатываются и их содержимое перемещается уже в результирующий массив. При этом, если в какой-то корзине находятся несколько элементов исходного массива, то они перед переносом в результирующий массив еще раз сортируются, на сей раз уже по своим значениям (а не значениям ключей как было до того).
|
|
|
|
|
