插入排序

插入排序的基本方法：
每一步将一个待排序的对象，按其排序码大小，插入到前面已经排好序的一组对象的适当位置上，知道所有对象全部插入为止。
插入排序的实施方案：
1. 直接插入排序
2. 折半插入排序
3. 希尔排序

一、直接插入排序
1. 算法代码：

/**
* 直接插入排序
**/
func InsertSort(data []int) {
	for i := 1; i < len(data); i++ {
		for j := i; j > 0; j-- { //向前搜索插入位置
			if data[j] < data[j-1] { //边比较边移位
				data[j], data[j-1] = data[j-1], data[j]
			} else { //已找到插入位置
				break
			}
		}
	}
}

2. 空间复杂度：O(1)
3. 时间复杂度：O(n*n)
4. 稳定性：稳定

二、折半插入排序
1. 算法描述
对于每一个数据对象，先使用二分查找法找到插入位置，然后再移位，插入。
2. 算法代码：

/**
* 折半插入排序
**/
func BinInsertSort(data []int) {
	for i := 1; i < len(data); i++ {
		head, tail := 0, i-1
		for head <= tail { //使用二分查找法找到插入位置
			mid := (head + tail) / 2
			if data[i] < data[mid] {
				tail = mid - 1
			} else {
				head = mid + 1
			}
		}
		temp := data[i]
		for j := i - 1; j >= head; j-- { //移位
			data[j+1] = data[j]
		}
		data[head] = temp
	}
}

3. 空间复杂度：O(1)

4. 时间复杂度：O(n*n)

折半插入排序与直接插入排序相比，减少了排序码之间的比较次数，但对象的移动次数是相同的。

5. 稳定性：稳定

三、希尔排序

1. 算法描述

把对象记录按一定增量分组，对每组使用直接插入排序算法排序，不断缩小增量直至1，所有记录对象变成一个组。利用原有子序列的有序性来减少比较和移动的次数。适用于大数据量的排序。

2. 算法代码：

/**
* 希尔排序
**/
func ShellSort(data []int) {
	for add := len(data) / 2; add > 0; add /= 2 { //增量控制
		for i := add; i < len(data); i++ {
			for j := i; j >= add; j -= add { //以指定增量向前搜索插入位置
				if data[j] < data[j-add] { //边比较边移位
					data[j], data[j-add] = data[j-add], data[j]
				} else { //已找到插入位置
					break
				}
			}
		}
	}
}

3. 时间复杂度

当n很大时，排序码平均比较次数和对象平均移动次数大约在n的1.25次幂的1至1.6倍之间。

折半插入排序与直接插入排序相比，减少了排序码之间的比较次数，但对象的移动次数是相同的。

4. 稳定性：不稳定