Следующий алгоритм сортировки называется сортировкой вставками. Он снова использует два цикла, что приводит к временной сложности O (n²). Это реализуется за счет того, что внешний цикл начинается с индекса 1 и движется к концу. Внутренний цикл выполняется, пока выполняются два условия: индекс внутреннего цикла ≥ 0 и вход[индекс внутреннего цикла] равен › input[индекс внешнего цикла]. На каждой итерации внутреннего цикла (при условии выполнения условий выполнения) arr[индекс внутреннего цикла + 1] устанавливается равным arr[индекс внутреннего цикла]. По сути, это сдвиг большего значения вправо. Если вы печатаете на каждом шаге, вы заметите повторяющееся значение. Это продолжается до тех пор, пока не будет выполнено условие остановки внутреннего цикла. На данный момент мы знаем, что arr[индекс внутреннего цикла] равен ‹ arr[индекс внешнего цикла]. Мы можем заменить arr[индекс внутреннего цикла + 1] на наш arr[индекс внешнего цикла]. Это называется сортировкой вставками, потому что вставка является последним шагом и происходит только один раз за итерацию внутреннего цикла. Варианты использования этого алгоритма немного ограничены, но существуют. Если ввод отсортирован и вам нужно вставить только одно значение, или если ввод почти отсортирован, его можно использовать. Если ввод случайный, это может быть не лучший вариант.
