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

2.2.2.2. Сортировка бинарными включениями 
Поскольку поиск места для нового элемента ведется в отсортированной 
части массива, то его можно ускорить за счет применения рассмотренного 
выше алгоритма бинарного поиска. Данная идея реализована в программе, 
представленной в листинге 2.6. 
Листинг 2.6. Сортировка бинарными включениями 
public void SortBinInsert(int[] a) 
{ 
int N = a.Length; 
for (int i=1; i<= N-1; i++) 
{ 
int tmp=a[i], left=1, right=i-1; 
while (left<=right) 
{ 
int m=(left+right)/ 2;
23 / 23

---

24 
//
определение индекса среднего элемента 
if (tmpright=m-1; // 
сдвиг правой или 
else left=m+1; // 
левой границы 
} 
for (int j=i-1; j>=left; j--) 
a[j+1] = a[j];
// 
сдвиг элементов 
// 
размещение элемента в нужном месте 
a[left]=tmp;
} 
} 
Число сравнений C~N*log
2
N
, так как поиск места вставки осуществ-
ляется только в одной части массива. Но это улучшение касается только чис-
ла сравнений. К сожалению, это улучшение не является решающим, посколь-
ку пересылка элементов более трудоемкая операция. Поэтому число переста-
новок по-прежнему имеет временную сложность ~N
2
. Соответственно, ско-
рость роста и для этой модификации алгоритма O(N
2
).
Для массивов больших размеров сортировка вставками оказывается 
очень неэффективным методом ввиду большого числа перемещений элемен-
тов. Очевидно, что гораздо эффективнее переставлять только некоторые эле-
менты и на большие расстояния. Ниже будет рассмотрен метод сортировки, 
основанный на этой идее и известный как сортировка Шелла.
2.2.3. С