Сортировка вставками
Берём исходные элементы и складываем в результат в отсортированном порядке. Для каждого нового элемента в результате находим правильное место и вставляем, раздвигая результат.
Сортировать будем начало массива, текущий элемент будем менять местами с предыдущим, пока он не займет правильного места. Так мы одновременно реализуем и поиск нужной позиции, и вставку.
procedure InsertionSort(var A: TAI); var i, j: integer; begin for i := Low(A)+1 to High(A) do begin j := i; while (j > Low(A)) and (A[j] < A[j-1]) do begin swap(A[j], A[j-1]); dec(j); end; end; end;
Максимальная | O(N2) |
Минимальная | O(N) |
Средняя | O(N2) |
Метки:
- Войдите или зарегистрируйтесь, чтобы отправлять комментарии