Сортировка подсчётом
Материал из Википедии — свободной энциклопедии
Сортировка подсчётом — алгоритм сортировки массива, при котором подсчитывается число одинаковых элементов. Алгоритм выгодно применять, когда в массиве много элементов, но все они достаточно малы.
[править] Описание алгоритма
Идея сортировки указана в её названии — нужно подсчитывать число элементов, а затем выстраивать массив. Пусть, к примеру, имеется массив A из миллиона натуральных чисел, меньших 100. Тогда можно создать вспомогательный массив B из 99 (1..99) элементов, «пробежать» весь исходный массив и вычислять частоту встречаемости каждого элемента — то есть если A[i]=a, то B[a] следует увеличить на единицу. Затем «пробежать» счетчиком i массив B, записывая в массив A число i B[i] раз.
[править] Временная и ёмкостная сложности алгоритма
Пусть n — длина исходного массива, k — максимальное число в массиве.
Тогда временная сложность алгоритма равна O(n+k), а ёмкостная — O(n+k).
[править] См. также
- Алгоритм сортировки
- O-большое
- Временная сложность алгоритма
- Ёмкостная сложность алгоритма
 |
Это незавершённая статья о компьютерах. Вы можете помочь проекту, исправив и дополнив её. |
