插入排序 ~ 算法之二

1. 简介

插入排序，有时也称直接插入排序，这里“插入”是指将一个数，插入到有序数列中的合适位置

2. 算法过程

• 我们有多轮的过程，每轮过程是将一个数放入到有序数列的合适位置
• 每一轮，有序数列中会多一个元素，无序数列中会少一个元素
• 每轮比较的过程，就是从后往前，挨个两个元素进行比较，如果比当前元素小，则交换两个元素，直到大于等于这个元素才结束
  或是已经排到最前面了，也会结束
• 直到最后一个数排好了，我们整个排序过程就结束了

3. 简单数据演示

原始数据，默认第1个数是有序的，也就是9
9 8 6 10 7
第一轮，排序数为8，需要把8，加入到前面的有序数列中，当然现在只有一个9，因为8比9要小，所以交换两个元素，这时我们的有序数列就有8，9
8 9 6 10 7
第二轮，排序数为6，需要插入到[8,9]中，从后往前比较，比9要小，要交换一下位置，变成[8,6,9],继续往前比较，再和8交换位置，变为[6,8,9]
6 8 9 10 7
第三轮，排序数为10，需要插入到[6,8,9]中，第一次比较，发现就比9要大，开心了，不需要交换了,直接成功了，变成[6,8,9,10]
6 8 9 10 7
第四轮，排序数为7，挨个往前比较，发现，需要分别和10，9，8进行交换，直到碰到6，比它还要小，才结束，这样就变成了全排序好了
6 7 8 9 10

3. 其它

1）时间复杂度为o(n^2)，效率不太高，数据量较大的情况下，不建议使用
2）如果是需要逆向排序，调整一下判断条件，每次把最小的放在最后就可以了