Вставка сортировки — очень простой метод сортировки чисел в порядке возрастания или убывания. Этот метод следует инкрементному методу. Это можно сравнить с техникой сортировки карт во время игры.
Числа, которые необходимо отсортировать, называются ключами . Вот алгоритм метода сортировки вставок.
Algorithm: Insertion-Sort(A) for j = 2 to A.length key = A[j] i = j – 1 while i > 0 and A[i] > key A[i + 1] = A[i] i = i -1 A[i + 1] = key
Анализ
Время выполнения этого алгоритма очень сильно зависит от заданного ввода.
Если данные числа отсортированы, этот алгоритм выполняется за O (n) раз. Если заданные числа в обратном порядке, алгоритм запускается за O (n 2 ) времени.
пример
Несортированный список: |
|
Несортированный список:
1- я итерация:
Ключ = [2] = 13
a [1] = 2 <13
Своп, без свопа |
|
Своп, без свопа
2- я итерация:
Ключ = [3] = 5
a [2] = 13> 5
Поменяйте местами 5 и 13 |
|
Поменяйте местами 5 и 13
Далее a [1] = 2 <13
Своп, без свопа |
|
Своп, без свопа
3- я итерация:
Ключ = [4] = 18
а [3] = 13 <18,
а [2] = 5 <18,
а [1] = 2 <18
Своп, без свопа |
|
Своп, без свопа
4- я итерация:
Ключ = [5] = 14
а [4] = 18> 14
Поменять местами 18 и 14 |
|
Поменять местами 18 и 14
Далее а [3] = 13 <14,
а [2] = 5 <14,
а [1] = 2 <14
Так что без обмена |
|
Так что без обмена
В заключение,
отсортированный список