73
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Сначала рассмотрим так называемую внутреннюю сортировку, т.е. все
записи расположены в оперативной памяти, следовательно, доступ ко всем
ключам занимает одно и то же время, которым можно пренебречь.
Методы внутренней сортировки разбиваются на 5 классов:
1.
Обмен
, или
сортировка перестановки
. Два ключа, расположение
которых не соответствует требуемому порядку, меняются местами. Процесс
продолжается, пока находятся такие пары ключей.
000…….0
Обмен
2.
Сортировка выбором
. На
i
-м этапе из неотсортированных имен
выбирается
i
-е наибольшее (наименьшее) имя и помещается на
соответствующее место.
000…….0
Не отсортированы
000…….0
Уже отсортированы
3.
Вставка
. На
i
-м этапе
i
-e имя помещается на надлежащее место между
i
-1 уже отсортированными именами:
000…….0
Не отсортированы
000…….0
Уже отсортированы
1...,65,66,67,68,69,70,71,72,73,74 76,77,78,79,80,81,82,83,84,85,...106