Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23

2.2.2. С
ОРТИРОВКА ВКЛЮЧЕНИЯМИ
 
Как и в предыдущем методе сортировки, массив считается состоящим 
из отсортированной и неотсортированной частей. Однако теперь на каждом 
шаге сортировки первый элемент из неотсортированной части перемещают в 
нужное место отсортированной части. Далее будут рассмотрены две реализа-
ции этого метода, отличающиеся способом такой «вставки».
2.2.2.1. Сортировка простыми включениями 
В этом варианте алгоритма включение нового элемента в отсортиро-
ванную часть осуществляется путем последовательного сдвига входящих в 
нее элементов вправо. Этот процесс может завершиться при выполнении од-
ного из двух условий: 
− найден элемент меньший, чем включаемый; 
− достигнута левая граница массива. 
Функция, реализующая алгоритм сортировки простыми включениями, 
представлена в листинге 2.5. 
Листинг 2.5. Сортировка простыми включениями 
public void SortInsertion(int[] a) 
{ 
int tmp; 
int N = a.Length; 
for (int i = 1; i < N; i++) 
{ 
int j = i - 1; 
while (j >= 0 && tmp < a[j]) 
a[j + 1] = a[j--]; // 
сдвинуть элемент 
// 
поставить элемент на свое место
a[j + 1] = tmp;
} 
} 
В сортировке простыми вставками число сравнений при перемещении 
очередного элемента на свое место зависит от степени упорядоченности ис-
ходного массива. Оно минимально и на каждой итерации равно 1, если ис-
ходный массив упорядочен по возрастанию. В случае упорядоченности ис-
22 / 23

---

23 
ходного массива по убыванию на i-ой итерации будет выполняться i сравне-
ний (i=1,2,…,N–1). В этой части алгоритм сортировки простыми включе-
ниями демонстрирует более естественное поведение по сравнению с алго-
ритмом сортировки простым выбором. 
Среднее число сравнений на i-ой итерации равно C
ср
(i)=(i+1)/2
, а 
общее число перестановок равно: 
2
2
1
1
1
2
~
.
2
4
4
N
ср
i
i
N
N
N
C
−
=
+
+ −
=
=

(2.5) 
Среднее число пересылок i-ой итерации равно M
ср(i)
= C
ср(i)
+ 2. Поэтому 
2
2
9
10
~
.
4
4
ср
N
N
N
M
+
−
=
(2.6) 
Таким образом, скорость роста для алгоритма сортировки простыми 
включениями равна O(N
2
). Однако в сравнении с алгоритмом сортировки 
простым выбором имеется небольшой проигрыш в скорости, благодаря более 
сильной зависимости M
ср
от N (N
2
против N*log
2
N
в сортировке выбором). 
Отметим также, что этот алгоритм сортировки простыми включениями де-
монстрирует естественное поведение.