preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

start

Insert sort refers to inserting each element to be sorted into an ordered sequence. Insert sort builds the final sorted array, one item at a time. Let’s say the first term is already an ordered sequence. \

Next, it is compared with the second item — should the second item stay in place or be inserted before the first? The first two items are sorted correctly, then compared to the third item (should it be inserted first, second, or third), and so on.

Train of thought

Such as an array,5,1,4,2 [3]

  • As can be seen from line 5 on the left of the figure, thearray[2] 与 array[1]The comparison,array[2] > array[1]That will bearray[2]Inserted into thearray[1]The front (i.e.,array[1]1 and 5 switch places, and the array becomes,1,5,4,2 [3]
  • As you can see from line 6 on the left of the figure above, the array inserted the first time is compared again in a consistent wayarray[1] > array[0], the array becomes,3,5,4,2 [1], and so on, until the last element is compared
  • See the comments below for a concrete implementation

implementation

function insertionSort(array) {
  if (array.length <= 1) return array; // If the array length is 1, return it directly
  var sum = 0 // Count the number of loops
  for (var i = 1; i < array.length; i++) {
    var j = i; // Take index 1 as an example
    var temp = array[j]; // Store a value to compare and start comparing forward
    / / 1. If the temp < arr [1], the arr [1] ward (if arr = arr [j] [1]).
    // 2. If temp < ARR [J-2], arR [J-2] = arr[j-2];
    //   若temp>arr[j-2]，则arr[j-1] = temp
    while (j > 0 && array[j - 1] > temp) {
      sum++
      array[j] = array[j - 1]; // This can be seen as moving j-1 one bit back
      j--;
    }
    array[j] = temp;
  }
  console.log('sum: ', sum); / / 6
  return array;
}
var arr = [5.4.3.2.1];
console.info(insertionSort(arr));
Copy the code

To optimize the

No optimization ideas, welcome to comment

See digg friends with dichotomous search method for optimization, the subsequent analysis of dichotomous search method to supplement

The complexity of the

When sorting small arrays, this algorithm performs better than selective sort and bubble sort. Insertion sort is used more than bubble sort and selection sort. Because the first two are sort by swap, they essentially require three original operations. An algorithm with a time complexity of “O(n²)” contains two nested loops, which result in quadratic complexity

other

# Front-end algorithm learning – Algorithm complexity # Front-end required algorithm (I) : bubble sort # Front-end required algorithm (II) : select sort

The last

Dregs a, welcome all great god many correction, not praise, just supervision correction