go语言插入排序

1 定义

​ 插入排序 实际上就是在有序的数据中找到属于你自己的位置。基本思想： 将一个记录插入到一个有序表中

2 理解

​ 生活中有许多插入排序的例子。

​ 例如：打扑克牌，我们正常人的思路都是：

第一张牌其实已经有序。所以不需要在排。

 当拿到第二张牌的时候。就开始比较。正常来讲拿在我们手上的牌是不动的，那么我们需要决定这个第二张牌的位置，放前面还是后面。当第二张牌大，放后面，反之，放前面。

  当拿到第三张牌的时候， 其实我们肉眼以及大脑是可以瞬间分析出来他的位置。但分析很简单。我们从最前面看到最后面。 每个和第三张牌比较一下。 然后具体的位置才有了。

 以此类推

3 过程

​ 插入排序的算法实现过程：

由图可得，每次取一个数，这个数和前一位进行比较，比前一个dada，交换，一直比，一直交换，直到前一个数比他大或者到第一个数了。结束比较和交换。

4 时间复杂度

​ 时间复杂度取决于 数据本身的有序性，

​ 如果数据基本有序，意味这O(n).因为每次和最后一次比较时，发现比他大，然后结束比较直接进入下一个数的比较，一共比较n次。则 n X 1 为 n 次。因此O(n)

​ 如果数据反序，那么，第一次要比较1 次，第二次比较2次，第三次比较3次，因此时间复杂度时n x （1+n）/2,因此是O（n2）

其他情况介于这两个之间。

5 代码

func insertSort(a []int)[]int{
   for i:=1;i<len(a);i++{
      temp := a[i]
      j := i-1
      for j >= 0 && a[j] > temp {
         a[j+1] = a[j]
         j--
      }
      if j != i-1 {
         a[j+1] = temp
      }
   }
   return a
}