插入排序

排序

说明

把当前值插入已排序前缀；近乎有序时很快，最坏 O(n²)。

分析

循环开始时，左侧前缀始终有序；当前值向左寻找位置，并把较大的元素右移。输入接近有序时移动次数很少，因此小数组或排序算法的收尾阶段常会采用它。

图解推演

[3,1,2] 首先把 1 插入已排序前缀 [3]，将 3 右移；然后把 2 插入 [1,3]，只移动 3。循环不变量是当前位置之前已经有序。保存 key 后再移动元素，不能直接覆盖 key；相等元素不移动可保留稳定性。

查看图表代码

适用前提与边界

完全逆序时仍需 O(n²) 次移动。

示例输入与调用

a := []int{3, 1, 2}
	InsertionSort(a)
	fmt.Println(a)

运行输出

[1 2 3]

完整 Go 示例

package main

import "fmt"

func InsertionSort(a []int) {
	for i := 1; i < len(a); i++ {
		x := a[i]
		j := i
		for j > 0 && a[j-1] > x {
			a[j] = a[j-1]
			j--
		}
		a[j] = x
	}
}

func main() {
	a := []int{3, 1, 2}
	InsertionSort(a)
	fmt.Println(a)
}