Метод линейной вставки
При сортировке исходного вектора A методом линейной вставки последовательно просматриваются элементы вектора A и формируется упорядоченный вектор B. До начала сортировки считается, что длина упорядоченного вектора равно 0. Как только длина упорядоченного вектора станет равной длине исходного вектора, сортировка закончена.
Первый элемент вектора A помещается в первую позицию вектора B. Длина вектора становится равной 1.
Второй элемент вектора A сравнивается со всеми элементами вектора B. Если он больше всех элементов вектора В, то помещаем его в конец вектора и при этом длина вектора В увеличивается на единицу. Если в векторе В найдется элемент, меньший сравниваемого, то фиксируем позицию этого элемента, и все элементы вектора В, начиная с этой позиции, перемещаем на одну позицию вправо, начиная с последнего. На освободившееся место помещаем сравниваемый элемент. Длину вектора В увеличиваем на единицу.
В дальнейшем, последовательно просматривая элементы вектора А, сравниваем их с элементами вектора В, начиная с первого, до тех пор, пока не встретиться больший. Этот больший элемент и все последующие элементы вектора В передвигаются на одну позицию вправо. Таким образом освобождается место, на которое вставляется новый элемент.
Просмотр | Исходный вектор А | Полученный вектор В |
1-ый | 2 4 8 5 6 1 | 2 |
2-ой | 2 4 8 5 6 1 | 2 4 |
3-ий | 2 4 8 5 6 1 | 2 4 8 |
4-ый | 2 4 8 5 6 1 | 2 4 8 2 4 5 8 |
5-ый | 2 4 8 5 6 1 | 2 4 5 8 2 4 5 6 8 |
6-ой | 2 4 8 5 6 1 | 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 2 4 5 6 8 1 2 4 5 6 8 |
B[1]:=A[1];
k:=1;
For i:=2 to n do
Begin
j:=1;
While (j<=k) and (a[i]>b[j]) do
j:=j+1;
If j=k+1 then
Begin
b[j]:=a[i];
k:=k+1;
End
Else
Begin
For l:=k+1 downto j+1 do
b[l]:=b[l-1];
b[j]:=a[i];
k:=k+1;
end;
end;
Сравнение методов по основным характеристикам
для вектора размерности n
Метод сортировки | Минимальное и максимальное число сравнение | Количество перемещений или обменов |
Линейный выбор | , | n перемещений |
Линейный выбор с обменом | , | n обменов |
Линейны выбор с подсчетом | , | n перемещений и подсчетов |
Парный обмен | n, | обменов |
Метод стандартного обмена | n, | обменов |
Метод просеивания | n, | обменов |
Метод линейной вставки | n, | перемещений |
Дата добавления: 2015-04-15; просмотров: 1170;