Algorithm - 插入排序

说明

通常人们整理桥牌的方法是一张一张的来，将每一张牌插入到其他已经有序的牌中的适当位置。 在计算机的实现中，为了给要插入的元素腾出空间，我们需要将其余所有元素在插入之前都向右移 动一位。这种算法叫做插入排序

特点

和选择排序不同的是，插入排序所需的时间取决于输入中元素的初始顺序。例如，对一个很大 且其中的元素已经有序(或接近有序)的数组进行排序将会比对随机顺序的数组或是逆序数组进行 排序要快得多。

Code

package main

import "fmt"

func main() {
	arr := []int{1, 6, 8, 3, 23, 454, 15, 334, 8, 6, 35}

	insertSort(arr[:])
	fmt.Println(arr)
}

func less(a, b int) bool {
	return a < b
}

func exch(arr []int, i, min int) {
	arr[i], arr[min] = arr[min], arr[i]
}

func insertSort(arr []int) {
	N := len(arr)
	for i := 1; i < N; i++ {
		for j := i; j > 0 && less(arr[j], arr[j-1]); j-- {
			exch(arr, j, j-1)
		}
	}
}