What is insertion sort?
It’s going from left to right in the array, taking a number, and then putting it in the right place
Algorithm description
Suppose an array has two regions
Five, eight, two, three, one
The ordered region is empty, and the unordered region is 5, 8, 2, 3, 1
-----------------------------------
First, select the first value (5) in the unordered area and place it at the end of the ordered area. The first step is basically left untouched
Results: 5, 8, 2, 3, 1
The ordered region is 5, and the unordered region is 8, 2, 3, 1
-----------------------------------
Then take the first value (8) in the unordered region and record it. Then continue to look for a value (1) that is smaller than it in the unordered region. Then insert it from right to left in the ordered region (between less than 1 and greater than 1)
Results: 5, 8, 2, 3, 1
The ordered region is 1, 5, and the unordered region is 8, 2, 3
-----------------------------------
Then take the first value (8) in the unordered region and record it. Then continue to look for a value (2) that is smaller than it in the unordered region, and then insert it from right to left (between less than 2 and more than 2)
Results: 5, 8, 2, 3, 1
The ordered region is 1, 2, 5, and the unordered region is 8, 3
-----------------------------------
. And so on until the unordered region is empty
<img src=”https://noxussj.top:3000/23/1.gif”></img>
Reference is worth collecting ten classic sorting algorithm
additional
- This article is published through multiple platforms of “We Media” and will not be maintained after publication. If you have any objection to the content, you can discuss it in the GitHub below
- The ongoing maintenance / 500 + face questions before update/notes 】 https://github.com/noxussj/In…
- [3D city modeling using three. JS (Zhuhai City)] https://3d.noxussj.top/