Информатика. Общая информатика. Основы языка C++. Мамонова Т.Е. - 141 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

Усложненные методы требуют меньшего числа операций, но сами опе-
рации более сложные, поэтому для небольших массивов простые мето-
ды более эффективны.
Простые методы подразделяются на три основные категории:
1) сортировка методом простого включения;
2) сортировка методом простого выделения;
3) сортировка методом простого обмена;
Сортировка методом простого включения (вставки)
Элементы массива делятся на уже готовую последовательность
и исходную. При каждом шаге, начиная с I = 2, из исходной последова-
тельности извлекается I-й элемент и вставляется на нужное место гото-
вой последовательности, затем I увеличивается на 1 и т.д.
В процессе поиска нужного места осуществляются пересылки эле-
ментов больше выбранного на одну позицию вправо, т.е. выбранный
элемент сравнивают с очередным элементом отсортированной части,
начиная с J = I – 1. Если выбранный элемент больше a[I], то его включа-
ют в отсортированную часть, в противном случае a[J] сдвигают на одну
позицию, а выбранный элемент сравнивают со следующим элементом
отсортированной последовательности. Процесс поиска подходящего ме-
ста заканчивается при двух различных условиях:
1) если найден элемент a[J] > a[I];
2) достигнут левый конец готовой последовательности.
Пример 43. Сортировка методом вставки.
int i,j,x;
for(i=1;i<n;i++)
{
x=a[i];//запомнили элемент, который будем встав-
лять
j=i-1;
while(x<a[j]&&j>=0)//поиск подходящего места
{
a[j+1]=a[j];//сдвиг вправо
j--;
}
a[j+1]=x;//вставка элемента
}
Сортировка методом простого выбора
141

Страницы