插入排序

在上一章中我们讲了算法排序中的最简单的冒泡排序，今天我们来讲解一下插入排序，后续将讲解快速排序，归并排序，希尔排序，二叉排序，这些等等，后续的排序都是在时间复杂度和空间复杂度上面优于这两种的，所以我们今天先来讲解一下插入排序

我们先来看以下的一张图

为了方便排序，我们一般将数据的第一个元素作为有序组，其他视为待插入组，图中以升序为例子进行讲解。

我们将第一个元素作为有序的数组，然后将后面的元素视为无序的，将后面的无序组第一个元素和有序组最后一个元素比较，如果符合要求就插入进去然后有序组就多一个，无序组就少一个
第二次排序的时候有序组就为两个元素，有序组的最后一个元素拿出来继续和无序组的第一个相比，然后再插入一个，这样有序组就又多了一个，无序组少一个
这样一直循环到某个条件，这样无序组就没有了，剩下的都是有序组，这样排序就完成了。
我们来看一下代码怎样实现，在这里我们就用GO语言来实现，在某些方面个人觉得go写的代码比C/C++要少很多，更加方便一点

package main
import "fmt"
func main() {
	var arr [10]int = [10]int{9, 1, 3, 4, 7, 5, 2, 10, 11, 8} //插入排序
	var temp ,j int                                              //临时变量temp
	for i := 1; i < len(arr); i++ { //遍历无序数组,下标1开始
		if arr[i] < arr[i-1] { //无序组第一个小于有序组最后一个才进入否则直接下一个元素
			temp=arr[i]        //用变量temp取出arr[i]的元素值
			for j=i-1;j>=0&&arr[j]>temp;j--{   //这里面temp不能写成arr[i]是因为下面
				arr[j+1]=arr[j]                   // 有一个arr[j+1]=arr[j]那样会导致arr[i]会变
			}
			arr[j+1]=temp //因为上面经过了j--所以这里需要arr[j+1]，for循环后就找到位置填充temp，也就是之前取出来的arr[i]
		}
	}
   fmt.Println(arr)
}

下面你可以自己去实现一下了，后续将讲解更难的排序方法。