Массив разделяется на две части: отсортированную ( 
) и неотсортированную ( 
). Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушать в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент, а в качестве неотсортированной части – все остальные элементы.
Принцип метода:
Таким образом, алгоритм будет состоять из n-1-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:
1) взятие очередного i-го неотсортированного элемента и сохранение его в дополнительной переменной;
2) поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
3) сдвиг элементов массива от i-1 до j-го вправо, чтобы освободить найденную позицию вставки;
4) вставка взятого элемента в найденную j-ю позицию.
Пример 3. Выполним сортировку массива по возрастанию элементов по методу вставки.
|
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| Фрагмент программы сортировки методом вставки
for(i=1;i<n;i++)
{
int temp=a[i];
int j=i;
while(temp<a[j-1] && j-1>=0)
{ a[j]=a[j-1];
j--;
}
a[j]=temp;
}
|
|
|
|
| -5
| -1
| -7
|
| -2
|
|
| | j=0
| i=1
| | | | | | |
|
|
|
|
|
|
|
|
|
|
|
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
|
|
|
|
| -5
| -1
| -7
|
| -2
|
|
|
| j=0
|
| i=2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -5
|
|
| -1
| -7
|
| -2
|
|
| | | j=1
| | i=3
| | | | |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -5
| -1
|
|
| -7
|
| -2
|
|
|
| j=0
|
|
|
| i=4
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| -7
| -5
| -1
|
|
|
| -2
|
|
|
|
|
|
|
| j=3
|
| i=5
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
|
|
|
| -7
| -5
| -1
|
|
|
| -2
|
|
|
|
|
|
| j=2
|
|
|
| i=6
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
|
|
|
| -7
| -5
| -2
| -1
|
|
|
|
|
|
|
|
|
|
|
| j=4
|
|
| i=7
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 0
| 1
| 2
| 3
| 4
| 5
| 6
| 7
|
|
| | -7
| -5
| -2
| -1
|
|
|
|
| |
