Изучение сортировки вставками
Эта статья основана на новой книге 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.
Добрый день.
