Изучение сортировки вставками
Эта статья основана на новой книге JavaScript算法:基本原理与代码实现 автора RubyLouvre (司徒正美) (github.com), которая уже скончалась в 2020 году.
Эта книга удобна для разработчиков JavaScript, но существует только китайская версия и нет электронных книг. Поэтому я постараюсь записать их в качестве своих заметок, а также для большего количества людей, которые захотят ими насладиться.
Спасибо, РубиЛувр.
вступление
Существует еще один известный алгоритм сортировки, называемый сортировкой вставками. Когда вы играете в карты, вы пытаетесь упорядочить свои карты, и я уверен, что вы не будете делать это, как пузырьковую сортировку или сортировку выбором, чтобы снова и снова зацикливать свои карты. Вы всегда подберете карту, найдете, где она должна быть, затем вставите ее в нужное место.
Именно так работает сортировка вставками.
Для этой статьи не требуется никаких других предварительных знаний, но вы можете прочитать другие статьи об алгоритмах в JavaScript:
«Список: Алгоритмы в JavaScript | Куратор LikeDreamwalker | Середина"
Сортировка вставками в JavaScript
Мы все еще начинаем с этого массива:
8 7 9 0 6 5 4 3 1 2
И мы всегда считаем первый элемент упорядоченным. Итак, начнем со второго элемента.
// Start with element 7 8 [ 7 ] 9 0 6 5 4 3 1 2
И мы можем сравнить элемент 8 и элемент 7, потому что элемент 7 меньше элемента 8, поэтому мы считаем, что элемент 7 должен быть слева от элемента 8, как игральные карты:
// Compare with element 8 and element 7 [ 8 7 ] 9 0 6 5 4 3 1 2 // Element 7 is less than element 8 so we insert it at the left of element 8
Но для массива мы не можем просто вставить элемент, например карточки:
// Make a copy of element 7 [ 8 7 ] 9 0 6 5 4 3 1 2 [ 7 ] // Move element 8 to element 7 [ 8 8 ] 9 0 6 5 4 3 1 2 [ 7 ] // Insert element 7 [ 7 8 ] 9 0 6 5 4 3 1 2
Вы, наверное, кое-что знаете о массивах, но поверьте мне, это действительно важно в этом алгоритме, поэтому продолжим:
// After the first insert, we think the slice before element 8 is ordered // So we start with element 9 7 8 [ 9 ] 0 6 5 4 3 1 2 // And we found no elements which is larger than element 9 // So now element 9 is in the right place // Resutlt 7 8 9 0 6 5 4 3 1 2 // And now we start with element 0, and it should be at the left of the whole array // Make a copy [ 7 8 9 0 ] 6 5 4 3 1 2 [ 0 ] // Move elements 7, 8, and 9 to right [ 7 7 8 9 ] 6 5 4 3 1 2 [ 0 ] // Not surprised original element 0 is disappeared // But we have the copy, so we keep inserting [ 0 7 8 9 ] 6 5 4 3 1 2
Вот как на самом деле работает алгоритм вставки. На самом деле это несложно понять, но немного сложно закодировать.
Мы создаем функцию с внешним циклом, но начинаем с индекса 1, а не 0:
function insertionSort(array) { let arrayLength = array.length; for (let outerIndex = 1; outerIndex < arrayLength; outerIndex++) { // Rest codes here } }
И мы назвали нашу копию targetElement
. Кроме того, мы вызвали индекс места, чтобы вставить rightPlaceIndex
, а затем создали внутренний цикл, чтобы найти rightPlaceIndex
:
function insertionSort(array) { let arrayLength = array.length; for (let outerIndex = 1; outerIndex < arrayLength; outerIndex++) { // Target element is the element we need to insert it to right place let targetElement = array[outerIndex]; let rightPlaceIndex; for ( rightPlaceIndex = outerIndex - 1; rightPlaceIndex >= 0; rightPlaceIndex-- ) { // And we search rightPlaceIndex in ordered-area, which is left from outerIndex if (targetElement > array[rightPlaceIndex]) { break; } } } }
Затем перемещаем элементы и вставляем их:
function insertionSort(array) { let arrayLength = array.length; for (let outerIndex = 1; outerIndex < arrayLength; outerIndex++) { // Target element is the element we need to insert it to right place let targetElement = array[outerIndex]; let rightPlaceIndex; for ( rightPlaceIndex = outerIndex - 1; rightPlaceIndex >= 0; rightPlaceIndex-- ) { // And we search rightPlaceIndex in ordered-area, which is left from outerIndex if (targetElement > array[rightPlaceIndex]) { break; } } if (rightPlaceIndex !== outerIndex - 1) { // OuterIndex is actually the targetElement's index, so we only need to care // elements between rightPlaceIndex and outerIndex for ( let innerIndex = outerIndex - 1; innerIndex > rightPlaceIndex; innerIndex-- ) { // We move every element to right, this will cause original target element be occupied // But don't worry we have already cache it in targetElement array[innerIndex + 1] = array[innerIndex]; } // Finally we insert it into right place array[rightPlaceIndex + 1] = targetElement; } // Otherwise we need to do nothing, they have already been ordered } }
Но этот код действительно выглядит плохо. Для решения этой проблемы мы просто используем внешний цикл и два внутренних цикла. Давайте объединим внутренние циклы:
function insertionSort2(array) { // Same outer loop let arrayLength = array.length; for (let outerIndex = 1; outerIndex < arrayLength; outerIndex++) { let targetElement = array[outerIndex]; // Same inner loop but we combine them. // Now innerIndex will be the pointer to loop the ordered-area, also the key to the right place let innerIndex = outerIndex - 1; for (; innerIndex >= 0 && array[innerIndex] > targetElement; innerIndex--) { // Move elements array[innerIndex + 1] = array[innerIndex]; } // innerIndex here will be less than the real target cause the loop, so we add it back array[innerIndex + 1] = targetElement; } }
Аутро
И на самом деле в оригинальной книге есть проблема с внутренним индексом, я исправлю ее и свяжусь с издателем, чтобы исправить это в бумажной книге.
Спасибо, что дочитали до конца. Пожалуйста, следите за автором и этой публикацией. Посетите Stackademic, чтобы узнать больше о том, как мы демократизируем бесплатное образование в области программирования во всем мире.
Я LikeDreamwalker.
Добрый день.