Сортировка вставками – наверное, самый простой способ сортировки. Заключается он в следующем: идём по массиву и как только встречаем нарушение порядка, начинаем перемещать элемент, который нарушил порядок до тех пор, пока он не встанет на место, где не нарушает порядок. Таким образом обходим все элементы.
Пусть мы хотим отсортировать массив 1,9,4,2,8,6
1,9,4,2,8,6 |
Элементы 1 и 9 идут по порядку. 4 нарушает порядок. Начинаем его «протаскивать» вперёд до тех пор, пока порядок не установится
1,4,9,2,8,6 |
Четвёртый элемент нарушает порядок. Тащим его налево, пока порядок не установится
1,4,2,9,8,61,2,4,9,8,6 |
И так далее
1,2,4,8,9,61,2,4,8,6,91,2,4,6,8,9 |
Массив отсортирован.
Каждый элемент, который нарушает порядок вставляется на своё место, поэтому алгоритм получил название сортировки вставками.
