Стр. 76 - Основы алгоритмов и структур данных

74 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4. Распределение. Имена распределяются по группам, и содержимое групп
затем объединяется таким образом, чтобы частично отсортировать таблицу;
процесс повторяется до тех пор, пока таблица не будет отсортирована
полностью.
5. Слияние. Таблица делится на подтаблицы, которые сортируются по
отдельности и затем сливаются в одну.
000…….0
000…….0
Отсортированная
таблица
Отсортированные
подтаблицы
000…….0
000…….0
Эти классы нельзя назвать ни взаимоисключающими, ни исчерпывающи-
ми: одни алгоритмы сортировки можно с полным основанием отнести более
чем к одному классу (пузырьковую сортировку можно рассматривать и как
выбор, и как обмен), а другие не укладываются ни в один из классов. Тем не
менее перечисленные пять классов достаточно удобны для классификации
алгоритмов сортировки.
5.1. Сортировка вставками или включениями
Данный алгоритм проходит через этапы j=2, 3, ..., n. На этапе j имя xj
вставляется на свое правильное место среди x1 , х2 , …,x j-1 . При вставке имя xj
временно размещается в X и просматриваются имена х j-1,xj -2,..., x 1; они
сравниваются с X и сдвигаются вправо, если обнаруживается, что они больше
X.