Сортировка вставками — это способ упорядочения элементов в порядке возрастания или убывания.
Для запоминания. При сортировке вставками небольшой элемент вставляется в правильное место в заданном массиве. Кроме того, тяжелый элемент перемещается к правому концу массива.
Шаги
- Мы предполагаем, что первый элемент данного массива отсортирован.
- Теперь мы сравниваем первый элемент со следующим текущим элементом массива.
- Если текущий элемент массива ‹ первый элемент
а. Вставьте текущий элемент в точное местоположение части отсортированного массива . Поместите первый элемент в правый конец отсортированного массива.
а. Повторите описанный выше процесс с отсортированной частью и текущими элементами массива, пока данный массив не будет отсортирован.
Визуализация
Реализация кода
функция вставкиСортировка(массив){
for(пусть i = 1; i ‹ array.length; i++){
for(пусть j = 0; j ‹ i; j++){
если (массив [i] ‹ массив [j]) {
пусть темп = массив [я]
массив [i] = массив [j]
массив [j] = темп.
}
}
}
возвращаемый массив
}
console.log (insertionSort ([9,5,6,2,10,1]))
Временная сложность — O (n²)
Удачного кодирования!
