preface

Hello everyone, I am CV Takuha, in order not to be confused by their own sort, so I will take 3 minutes to let myself know how to sort: insert sort

Insertion sort

Insert sort description: as the name implies, it is to extract a number from an array, scan the sorted array from back to front, and then insert the corresponding position.

  1. Starting from the first value of the array, the first value, which is subscript 0, can be considered sorted
  2. Then, take the next array value and scan from back to front in the sorted array sequence
  3. If the value is greater than the new value scanned in the array, the value is moved to the next position
  4. Repeat step 3 until you find a place where the sorted value is less than or equal to the new array
  5. After inserting the new value into the position
  6. Repeat steps 2 to 5

Still don’t understand? Demo diagram above:

Code implementation:

var arr = [5, 6, 3, 1, 8, 7, 2, 4]; function insertSort(arr) { var tmp; for (let i = 1; i < arr.length; i++) { tmp = arr[i]; for (let j = i; j >= 0; J -) {/ / get the current value, the left is the if (arr] [j - 1 > TMP) {arr [j] = arr [j - 1); } else { arr[j] = tmp; // If the value is smaller than the current value, the current position is set to break; } } } return arr; } insertSort(arr);Copy the code

Time complexity: O(n^2)

conclusion

Look at this. It’s three minutes. Do I get it? If you don’t understand, go back to the previous page and come in again. It’s another 3 minutes. If you think this article has helped me at all, please give it a thumbs up.