Алгоритмы сортировки в JS - сортировка вставками
Сортировка вставками это упорядочивание коллекции путем вставки каждого встреченного значения на правильную позицию.
В этом случае мы не проходим всю коллекцию при каждой итерации (как в сортировке пузырьком и выбором). Вместо этого мы начинаем со сравнения значений элементов с индексами 0 и 1. Если последнее значение меньше первого, они меняются местами. После этого мы перемещаемся к элементу с индексом 2 и сравниваем его значение со значениями двух предыдущих элементов (сначала с индексом 1, потом с индексом .
Каждый раз, находя более высокое значение, вы размещаете его правее. Найдя правильную позицию, вы вставляете содержимое ячейки с индексом 2 в ячейку на нужной позиции.
Это как будто вы вынимаете содержимое следующей ячейки и возвращаетесь с ним к предыдущей. Если содержимое предыдущей ячейки имеет больше значение, что то, которое вы «держите», вы перемещаете содержимое предыдущей ячейки в следующую. Это продолжается, пока вы не найдете подходящую ячейку, куда можно поместить значение, находящееся у вас «в руках».
#sorting #algorithms #insertionsort #javascript
grhgrmgrhrm
$ var n = a.length;
$ for (var i=0; i<n; i++){ // Выполняется для каждого элемента массива.
$ var v = a[i], j = i-1; // Определяется значение текущего элемента, а также индекс предыдущего элемента.
$ while(j >= 0 && a[j] > v){ // Пока индекс предыдущего элемента >= 0 и его значение больше значения текущего элемента.
$ a[j+1] = a[j]; // Значением следующего за текущим элемента массива становится значение предыдущего элемента.
$ j--;
$ }
$ a[j+1] = v; // Значением следующего за текущим элемента массива становится значение текущего элемента
$ }
$ return a;
$ };
$
$ let array = [85, 92, 12, 11, 0, 85, 1, 1, 20, 77, 01, 10.5, 10.15];
$
$ console.log(insertionSort(array));
Удалить комментарий
Вы уверены, что хотите удалить этот комментарий?