Структуры и алгоритмы обработки данных


Краткая теория - часть 2


Программы этих методов легко понимать, и они коротки. Напомним, что сами программы также занимают память.

2. Прямые методы особенно удобны для объяснения характерных черт основных принципов большинства сортировок.

3. Усложненные методы требуют небольшого числа операций, но эти операции обычно сами более сложны, и поэтому для достаточно малых n прямые методы оказываются быстрее, хотя при больших n их использовать, конечно,  не следует.

      Методы сортировки "на том же месте" можно разбить в соответствии с определяющими их принципами на 3 категории:

      1. Сортировки с помощью включения (by insertion)

      2. Сортировки с помощью выделения (by selection)

      3. Сортировки с помощью обменов (by exchange)

Сортировка методом прямого включения

Такой метод широко используется при игре в карты. Элементы (карты)  мысленно делятся на уже "готовую" последовательность a(1),...,a(i-1)  и исходную последовательность. При каждом шаге, начиная с i=2 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при  этом он вставляется на нужное место.

 

 




- Начало -  - Назад -  - Вперед -



Книжный магазин