Сортировка вставками работает, предполагая сравнение подмассива (слева от массива) с остальной частью массива (справа) и вставку значения в нужное место.
При времени выполнения O(n2) сортировка вставками работает медленно. В лучшем случае или почти отсортированном массиве сортировка вставками занимает O (n) времени.
Сначала мы сравниваем первые два элемента.
Поскольку 3 ‹ 8, 3 теперь является началом нашего отсортированного подмассива, с которым мы будем сравнивать все остальные значения. Заштрихованный зеленым квадрат будет представлять подмассив.
Далее сравниваем 8 и 1.
Поскольку 1 ‹ 8, сдвигаем на единицу влево. Однако 1 также меньше 3, поэтому мы снова сдвигаем 1 влево.
Мы продолжаем сравнивать, пока весь массив не будет отсортирован в порядке возрастания.
Теперь, когда у нас есть общее представление о том, как работает сортировка выбором, давайте рассмотрим псевдокод для ее реализации.
- Начните с выбора второго элемента в массиве.
- Теперь сравните 2-й элемент с предыдущим.
- Перейдите к следующему элементу и, если он находится в неправильном порядке, повторите отсортированную часть, чтобы поместить элемент в правильное место.
- Повторяйте, пока массив не будет отсортирован.
