插入排序

就像打扑克牌，发牌时，每接到1张新牌，都将其插入老牌中，保证有序

如下图，初始序列为[4,5,6,1,3,2]，左侧为已排序区间，右侧为未排序区间

移动操作的次数是固定的， 等于逆序度，如下图满有序度=n*(n-1)/2=15，初始有序度为5，逆序度为10，移动操作总次数为10=3+3+4

package main

import "log"

func main() {
	arr := []int64{4, 5, 6, 1, 3, 2}
	log.Print("InsertSort: ", NewInsertSort(arr).Sort())
}

package main

type insertSort struct {
	arr []int64
}

func NewInsertSort(arr []int64) *insertSort {
 return &insertSort{arr: arr}
}

func (s *insertSort) Sort() []int64 {
 for i := range s.arr { // i: 每个新元素
		value := s.arr[i] // 因为有后移操作，会破坏下标寻址，故须提前保存到变量里
		k := i - 1
  for ; k >= 0; k-- { // k: 每个已有元素, 从后向前
   if value < s.arr[k] { // 有逆序
				s.arr[k+1] = s.arr[k] // 后移
			} else {
    break
			}
		}
		s.arr[k+1] = value // 为value找到了正确的插入位置
	}
 return s.arr
}

InsertSort: [1 2 3 4 5 6]

复杂度

• 空间复杂度O(1)

• 稳定排序，因为我们可选择将后面出现的元素，插入到前面出现的元素后面，即可保持前后顺序不变

• 最好时间复杂度O(N)，即已有序，需处理N次新元素，每次新元素从尾到头遍历为O(1), 故总共为O(N)

• 最坏时间复杂度O(N^2), 即已倒序，需移动大量数据

• 平均时间复杂度O(N^2), 因为处理N个元素，每个元素都是在数组中插入一个元素即O(N), 故总共为O(N^2)