排序属于最基本、最常用的算法之一，而对于排序算法，也有多种排序算法，本节主要实现了选择排序、插入排序和希尔排序。

Golang的排序实现里定义了一个漂亮的接口：Interface，定义了三个方法：Len、Less和Swap。

//https://github.com/golang/go/blob/master/src/sort/sort.go
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

判断是否排序好的函数IsSorted

func IsSorted(data Interface) bool {
	n := data.Len()
	for i := n - 1; i > 0; i-- {
		if data.Less(i, i-1) {
			return false
		}
	}
	return true
}

再定义一个调用的方法：

const (
	//SELECT 选择排序
	SELECT uint8 = 1 << iota
	//INSERT 插入排序
	INSERT
	//SHELL 希尔排序
	SHELL
)

//FuncAPI 排序函数
type FuncAPI func(data Interface)

//Sort sort func
func Sort(data Interface, algo uint8) {
	sorter := map[uint8]FuncAPI{
		SELECT: selectSort,
		INSERT: insertSort,
		SHELL:  shellSort,
	}
	sorter[algo](data)
}

下面的实现就是具体的算法了。

选择排序

func selectSort(data Interface) {
	N := data.Len()
	for i := 0; i < N; i++ {
		min := i
		for j := i + 1; j < N; j++ {
			if data.Less(j, min) {
				min = j
			}
		}
		data.Swap(i, min)
	}
}

插入排序

func insertSort(data Interface) {
	N := data.Len()
	for i := 0; i < N; i++ {
		for j := i; j > 0 && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}

希尔排序

func shellSort(data Interface) {
	N := data.Len()
	h := 1
	for h < N/3 {
		h = 3*h + 1
	}

	for h >= 1 {
		for i := h; i < N; i++ {
			for j := i; j >= h && data.Less(j, j-h); j -= h {
				data.Swap(j, j-h)
			}
		}
		h = h / 3
	}
}