go语言插入排序

# 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 代码 ```go 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 } ```