2.1.3插入排序

实现原理

将每一个元素插入到已经有序的元素中的适当位置。为了腾出空间，需要将后面的元素一次向右移动以为。

效率分析

插入排序所需的时间取决于输入元素的初始顺序。对一个部分有序的数组进行排列比随机数组效率高很多。

代码实现

方式1：使用当前元素和之前的每一个元素进行对比，如果位置不对就交换两个元素的位置

func sort(a []int) {
  N := len(a)
  for i := 1; i < N; i++ {
    for j := i; j > 0 && less(a[j], a[j - 1]); j-- {
      exch(a, j, j - 1)
    }
  }
}

方式2：将内循环中较大的元素向右移动而不是交换位置

func sort(a []int) {
  N := len(a)
  for i := 1; i < N; i++ {
    num := a[i]
    j := i
    for ; j > 0 && less(num, a[j - 1]); j-- {
      a[j] =  a[j - 1]
    }
    a[j] = num
  }
}