插入排序

共计 503 个字符，预计需要花费 2 分钟才能阅读完成。

概念
插入排序算法类似于打扑克抽牌。从未排序的数组中（牌堆）取出一个元素，在已排序元素中（手牌）从后向前扫描，插入到比这个元素小或者相等的后面。重复此步骤，直到整个序列有序为止。

代码实现
func insertSort(arr []int) []int {
n := len(arr)
for i := 1; i < n; i++ {
value := arr[i]
j := i - 1
for j >= 0 && arr[j] > value {
arr[j+1] = arr[j]
j--
}
arr[j+1] = value
}
return arr
}
其中，arr 是待排序的整数序列，n 是序列的长度。在每一轮遍历中，将未排序部分的第一个元素取出，与已排序部分中的元素依次比较，找到比这个元素小或者相等的位置插入。这样一轮下来，未排序部分中的第一个元素就被插入到了已排序部分的适当位置。通过多轮的遍历比较，最终实现整个序列的排序。

算法分析
最好的情况下，当序列已排序好时，每一次迭代的过程中，只需要做一次比较即可，这个请款下，算法的时间复杂度为 O(n)，最坏的情况下，当序列为逆序时，插入排序的时间复杂度为 O(n^2)，其中 n 是待排序序列的长度。它的空间复杂度为 O(1)，是一种稳定的排序算法。