Сортировка вставками — это то, как мы обычно сортируем список элементов. Начинаем со второго пункта и сравниваем с первым. Меняем местами, если он меньше первого, иначе ничего не делаем. Таким образом, в общем случае для каждого элемента мы сравниваем его со всеми элементами, предшествующими ему, и вставляем его, где это уместно. В более подробном рассмотрении алгоритм сортировки вставками работает следующим образом: мы берем каждый элемент, начиная со второго, сохраняем его в переменной, а затем продолжаем сравнивать его со всеми элементами слева от него. При каждом сравнении, если элемент слева больше, чем элемент, хранящийся в переменной, мы перемещаем его на один шаг вправо и на один шаг влево, чтобы выполнить следующее сравнение. Этот процесс продолжается до тех пор, пока не встретится элемент, который меньше хранимой переменной. При этом сравнении мы просто копируем сохраненную переменную в предыдущую позицию. На этом мы закончили с элементом, хранящимся в переменной, и поэтому переходим к следующему элементу, чтобы выполнить аналогичные шаги. Это продолжается до тех пор, пока массив не будет полностью отсортирован.

Псевдокод для сортировки вставками:

Вот алгоритм сортировки вставками, который сортирует массив элементов A в порядке возрастания. InsertionSort (A) для ( от i=0 до A.length){ j=iv = A[i] while(A[j-1] › v){ A[j] = A[j-1] j = j - 1 } А[j] = v }

Реализация сортировки вставками в JavaScript:

function insertionSort (A){ for ( i=0; i‹ A.length; i++){ j=i; v = А[я]; в то время как (A [j-1] › v) { A [j] = A [j-1]; j = j — 1; } А[j] = v; } console.log(A); } вар А = [6,5,4,3,2,1];

Сортировка вставкой (А);

Первоначально опубликовано на сайте algorithmsmasterywithnawas.blogspot.com.