Прямые методы:
Сортировка с помощью прямого выбора
Выбираем элемент с наименьшим ключом
Меняем его местами с первым
Повторяем процесс начиная с элемента ai, I=2, 3, …, n-1
2 11 3 8 1 4 5
1 11 3 8 2 4 5
1 2 3 8 11 4 5
1 2 3 8 11 4 5
1 2 3 4 11 8 5
Прямые методы:
Сортировка с помощью прямого выбора
void selection_sort(int a[],int n)
1 {int i, j, k, x;
2for(i =1; i <n; i ++)
3{ k= i; x=a[i]
4for(j=i+1;j<=n;j++)
5 |
if (a[j]<x) {k=j; x=a[k];} |
6 |
a[k]=a[i]; a[i]=x; |
7}
} //end selection_sort
Прямые методы сортировки
Для всех прямых методов за каждый элементарный шаг элементы передвигаются на 1 позицию
Все прямые методы требуют порядка n2 шагов (n- количество элементов в массиве)
Улучшенные методы сортировки: Сортировка методом простого включения
Д. Шелл (1959)
Сначала сортируются элементы, отстоящие друг от друга на расстоянии 4
После первого прохода элементы перегруппируются: каждый элемент группы отстоит от другого на 2 позиции
Улучшенные методы сортировки: Сортировка методом простого включения
Д. Шелл (1959)
На третьем шаге – обычная сортировка
Улучшенные методы сортировки: Сортировка методом простого включения
Д. Шелл (1959)
44 54 12 42 94 18 06 67
44 18 06 42 94 54 12 67
44 18 06 42 94 54 12 67
06 18 44 42 12 54 94 67
06 12 18 42 44 52 64 94
Улучшенные методы сортировки: Сортировка методом простого включения
Д. Шелл (1959)
На каждом шаге сортируется
либо меньшее число элементов
Либо элементы уже довольно хорошо отсортированы
Улучшенные методы сортировки:
Сортировка методом простого
включения (Д. Шелл (1959))
Расстояния в группах можно уменьшать по-разному
В общем виде:
Пусть задана последовательность расстояний
r1, r2, …, rk,
для которых выполняется условие: rk =1; ri+1< ri, i=1, …, k-1
Сортировка методом простого
включения (Д. Шелл (1959))
Наиболее часто используются следующие значения для расстояний:
1. r1 =1; ri+1=3ri+1, i=2, …, k-1
В обратном порядке: 1, 4, 13, 40,121…
2. r1 =1; ri+1=2ri+1, i=2, …, k-1
В обратном порядке: 1, 3, 7, 15, 31, ….