开发者学堂课程【Go 语言核心编程 - 数据结构和算法：数据结构和算法-插入排序分析】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/627/detail/9849
数据结构和算法-插入排序分析
内容介绍
一、插入排序法
二、插入排序法思想
三、思想的示意图
插入排序的速度会比选择排序更快。
一、插入排序法
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
二、插入排序法思想
从代码理解，插入排序要比选择排序更麻烦，但是它的思想很先进，一般来说会比选择排序快一倍，
插入排序(Insertion Sorting)的基本思想是：把n个待排序的元素看成为一个有序表和一个无序表（意思就是先把第一个元素，因为只有一个元素无论是从小到大还是从大到小它都是有序的），开始时有序表中只包含一个元素，无序表中包含有 n-1个元素（就是把第一个看成是有序的，n-1看成是无序的），排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
三、思想的示意图：
把它画成两个部分，一个部分是演示部分，另一个部分是排序思想。
1. 演示：
假设现在有一个数组，这个数组就当是按小牛的成绩排序，分别是23，0，12，56，34从大到小排序，假设原始的数组是[23，0，12，56，34]
（1）第一次找到插入位置，先是0和23比较，很容易找到位置，这个数组就变成[23,0]12，56，34是无序的
（2）第二次 insertval 的值就变成12，第二次找到插入位置，它如果比0大就后移，那么变完的结果[23,0,0]56，34这时候12已经被保存下来了，让23与12进行比较，是大于12的，位置就已经找到，找到之后，只需要在+1的位置就可以了，就变成[23,12,0]56，34
（3）第三次找到插入位置，并插入，56比0大，就会向后移，这个时候它就变成了[23,12,0,0] 34，移动下标指向12，insertval 还是56，56比12大，说明没有位置，就往后移动，就变成[23,12,12,0]，23不大于12就继续向后移动，就变成[23,23,12,0]34，这个时候再向下移动，发现移动不了了，说明它是最大的,但是它还是会稍微移动一下才会退出循环，最后会变成[56,23,12,0]23 ，也就是它会不停的找位置找到之后加进去。但是这个优越的地方是 ，它总是有序数组在找位置，它比较的次数是在减少的。所以插入排序是比冒泡排序和选择排序快的，至少快一倍
（4）第四次也是一样的道理，第四次插入的值就找34就可以，每次都是从最后找。于是就变成[56,23,12,0,0]下标就指向了12，12比34 仍然是小的，所以还没有找到位置，往后面移动就是[56,23,12,12,0]继续向后移动就是[56,23,23,12,0]最后会变成[56,34,23,12,0]
不确定每次比较的次数到底是多少，它可能很快就退出来了，也可能会遍历完才退出，假如最后不是34是-1那比较一次就可以了，如果最后就是最大的，它就得遍历完
2.排序思想：
（1）将23当作是有序的数组
（2）给0找一个位置插入
（3）思路：先把0保存到一个变量 insertval 中，将这个变量插到23这个有序变量中，插入时候就相当于这个值被保存了，现在它的指针就指向它前一个位置，就是0的前一个位置，然后将插入的位置用一个变量保存，就是0的下标的前一个下标
（4）从后开始比较，给 insertval 找到一个位置，插入
（5）找的过程中有序数组的元素位置是要后移的
