InsertSort.md

插入排序是一种从序列左端开始依次对数据进行排序的算法。在排序过程中，左侧的数据陆续归位，而右侧留下的就是还未被排序的数据。插入排序的思路就是从右侧的未排序区域内取出一个数据，然后将它插入到已排序区域内合适的位置上。

在一些特殊场景，如文件很多，内存装不下。可以从文件中一个个选择出来在进行插入。

代码实现：

package main

import "fmt"

// InsertSort 那要是14个数，按你这个公式是6层，但是实际是4层，所以公式该是以2为底取对数，再取向上取整
func InsertSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	} else {
		for i := 1; i < length; i++ {
			backup := arr[i]
			j := i - 1
			// 数据从前往后移 直接覆盖
			for j >= 0 && backup < arr[j] {
				arr[j+1] = arr[j]
				j--
			}
			// 将备份插入。因为前面的j--,这里的j+1是前面的j
			arr[j+1] = backup
		}
	}
	return arr
}

func main() {
	var arr = []int{1, 999, 2, 2, 5, 3, 8, 0, 4, 7, 0, 1, 1, 1, 1, 1000, 3, 1, 3, 6, 8, 9, 99, 33, 0}
	fmt.Println(InsertSort(arr))
}

算法关键点在于选择，当右边的数字比左边的数字小时。备份右边更小的数字，左边向右边移位。最后再将备份的数字插入移位出来的位置。

Tips:

在插入排序中，需要将取出的数据与其左边的数字进行比较。就跟前面讲的步骤一样，如果左边的数字更小，就不需要继续比较，本轮操作到此结束，自然也不需要交换数字的位置。然而，如果取出的数字比左边已归位的数字都要小，就必须不停地比较大小，交换数字，直到它到达整个序列的最左边为止。具体来说，就是第k轮需要比较k-1次。因此，在最糟糕的情况下，第2轮需要操作1次，第3轮操作2次……第n轮操作n-1次，所以时间复杂度和冒泡排序的一样，都为O（n2）。和前面讲的排序算法一样，输入数据按从大到小的顺序排列时就是最糟糕的情况。