Что такое сортировка вставкой?
В этом конкретном блоге мы будем говорить о технике вставочной сортировки. Этот метод принимает элементы в случайном порядке и сортирует их на основе сравнения. Один из способов подумать об этом алгоритме с другой точки зрения - это представить, что если бы вам дали несколько карточек, ваш непосредственный инстинкт состоит в том, чтобы отсортировать их в порядке возрастания. Это очень интуитивно понятный алгоритм, похожий на алгоритм сравнения. Однако оборотной стороной будет временная сложность O (n²). Этот метод считается наихудшим сценарием.
Как это работает?
Начните с создания доступной переменной с именем temp.
function insertionSort(array){ let temp; }
Итерируйте по массиву, начиная с индекса 1. Внутри этой первой итерации установите temp равным текущему индексу массива.
function insertionSort(array){ let temp; for(let i = 1; i < array.length; i++){ temp = array[i] } }
Следующий шаг требует итерации, однако здесь есть особый трюк, потому что мы будем устанавливать условие внутри цикла.
Мы начнем со второй итерации, которая состоит из начала с индекса до нашего первого индекса первой итерации. Кроме того, мы добавим условие, если индекс перед текущим массивом больше, чем фактический текущий массив. Это будет выглядеть примерно так.
function insertionSort(array){ let temp; for(let i = 1; i < array.length; i++){ temp = array[i] for(var j = i-1; array[j] > temp && j <-1; j--){ } } }
В этом конкретном цикле есть важный трюк, который упускается из виду. Индекс j должен быть больше -1. Это реализовано, потому что, если цикл непрерывно сравнивает и сортирует порядок элементов, он в конечном итоге выйдет за пределы индекса от 0 до -1. Поэтому мы добавили условие, что индекс j должен быть больше -1.
После того, как вторая итерация будет установлена и условия будут выполнены, мы переместим индекс j на 1 вместо temp.
function insertionSort(array){ let temp; for(let i = 1; i < array.length; i++){ temp = array[i] for(var j = i-1; array[j] > temp && j <-1; j--){ array[j + 1] = array[j] } } }
Затем мы выйдем из цикла for и поместим temp в открытое место. Как только все пройдет проверку, мы вернем массив.
function insertionSort(array){ let temp; for(let i = 1; i < array.length; i++){ temp = array[i] for(var j = i-1; array[j] > temp && j <-1; j--){ array[j + 1] = array[j] } array[j + 1] = temp } return array }
Вот полный взгляд на решение ниже. Надеюсь, вам понравилось до следующего раза.
function insertionSort(array){ let temp; for(let i = 1; i < array.length; i++){ temp = array[i] for(var j = i-1; array[j] > temp && j <-1; j--){ array[j + 1] = array[j] } array[j + 1] = temp } return array } let myInsertion = [1,2,4,3,5,6] console.log('insertionSort', insertionSort(myInsertion))