插入排序，和冒泡排序一样也是两层循环。外层循环遍历元素，将遍历到的元素 E 插入到它前面合适的位置（内层循环）使 E 前面的元素有序，插入过程中如果遇到比 E 小的元素 e 则停止此次内层循环遍历，因为 e 左侧已经是有序的了。
插入排序时间复杂度为 \(O(n^2)\)。
升序排序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 升序排序
func iSortASC(nums []int) []int {
for i := 0; i < len(nums); i++ {
// 前 i+1 个排序
for j := i; j > 0; j-- {
fmt.Printf("i=%v, j=%v, %v \n", i, j, nums)
// 把位置j的数放到前面合适的位置
if nums[j] < nums[j-1] {
nums[j], nums[j-1] = nums[j-1], nums[j]
} else {
break
}
}
}
return nums
}
修改下交换的判断条件，即可实现倒序排序：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 倒序排序
func iSortDesc(nums []int) []int {
for i := 0; i < len(nums); i++ {
// 前 i+1 个排序
for j := i; j > 0; j-- {
fmt.Printf("i=%v, j=%v, %v \n", i, j, nums)
// 把位置j的数放到前面合适的位置
if nums[j] > nums[j-1] {
nums[j], nums[j-1] = nums[j-1], nums[j]
} else {
break
}
}
}
return nums
}