With notes: insert sort --from WCC

Insertion sort

Insertion sort （ insertion sorting） It is an algorithm that sorts data from the left end of the sequence . During sorting , The data on the left is coming back , What's left on the right is the data that hasn't been sorted yet . The idea of insertion sort is to take out a data from the unsorted area on the right , Then insert it in the right place in the sorted area .

Ideas ：
1. The default from the i = 1 Start judging , such preIndex Nature is the cursor of the internal loop ;

2.current preservation arr[i], Determine by cycling current The final position of ;

3. At the beginning of each internal cycle ,arr[i] === current === arr[preIndex + 1], So for the first time in the inner cycle arr[preIndex + 1] = arr[preIndex] You don't have to worry about arr[i] The value of is missing ;

4. The general idea is , The elements that need to be ranked are cached first , Then apply the internal circulation , So that the element to be adjusted is assigned to a position behind it , Form and move in turn ,
Finally, because the inner loop stops when the judgment condition does not take effect, it means that the correct position of the element to be ranked is found , Then assign the value , To complete the order

The greatest thing about human beings is that they can always think of ways to solve problems --wcc