排序
对整数，浮点数，字符串切片排序
对于[]int, []float, []string这种元素类型是基础类型的切片使用sort包提供的下面几个函数进行排序。
具体实现见sort.Interface的IntSlice和Float64Slice的实现
sort.Intssort.Floatssort.Strings
s := []int{4, 2, 3, 1}
sort.Ints(s)
fmt.Println(s) // 输出[1 2 3 4]使用自定义比较器排序sort.Slice 和sort.SliceStable
使用sort.Slice函数排序，它使用一个用户提供的函数来对序列进行排序，函数类型为func(i, j int) bool，其中参数i, j是序列中的索引。
sort.SliceStable在排序切片时会保留相等元素的原始顺序。
上面两个函数让我们可以排序结构体切片(order by struct field value),也可以自定义排序规则.
1,2的参数都是一样的，建议用2(官方说更稳定)
func SliceStable(slice interface{}, less func(i int, j int) bool)有两个参数：第一个：
slice interface{}是切片的接口第二个：
less func(i int, j int) bool是一个less函数，less函数需要自行定义
family := []struct {
Name string
Age int
}{
{"Alice", 23},
{"David", 2},
{"Eve", 2},
{"Bob", 25},
}
// 用 age 排序，年龄相等的元素保持原始顺序
sort.SliceStable(family, func(i, j int) bool {
return family[i].Age < family[j].Age
})
fmt.Println(family) // [{David 2} {Eve 2} {Alice 23} {Bob 25}]
//示例2
people := [][]int{{9, 0}, {7, 0}, {1, 9}, {3, 0}, {2, 7}, {5, 3}, {6, 0}, {3, 4}, {6, 2}, {5, 2}}
less := func(i, j int) bool {
if people[i][0] == people[j][0] {
return people[i][1] < people[j][1]
}
return people[i][0] > people[j][0]
}
// 调用排序函数
sort.SliceStable(people, less)排序任意数据结构 实现sort.Interface
实现
模拟 IntSlice 排序
- 实现了sort.Interface接口的任意类型
一个内置的排序算法需要知道三个东西：序列的长度，表示两个元素比较的结果，一种交换两个元素的方式；这就是sort.Interface的三个方法：
type Interface interface {
Len() int
Less(i, j int) bool // i, j 是元素的索引
Swap(i, j int)
}我们为切片类型自定义一个类型名，然后在自定义的类型上实现 srot.Interface 接口
type Person struct {
Name string
Age int
}
// ByAge 通过对age排序实现了sort.Interface接口
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func main() {
family := []Person{
{"David", 2},
{"Alice", 23},
{"Eve", 2},
{"Bob", 25},
}
sort.Sort(ByAge(family))
fmt.Println(family) // [{David, 2} {Eve 2} {Alice 23} {Bob 25}]
}实现了sort.Interface的具体类型不一定是切片类型；下面的customSort是一个结构体类型。
type customSort struct {
p []*Person
less func(x, y *Person) bool
}
func (x customSort) Len() int {len(x.p)}
func (x customSort) Less(i, j int) bool { return x.less(x.p[i], x.p[j]) }
func (x customSort) Swap(i, j int) { x.p[i], x.p[j] = x.p[j], x.p[i] }
sort.Sort(customSort{persons, func(x, y *Person) bool {
if x.Age != y.Age {
return x.Age < y.Age
}
if x.Name != y.Name {
return x.Name > y.Name
}
return false
}})Reverse()
sort包提供了 Reverse() 方法，可以允许将数据按 Less() 定义的排序方式逆序排序，而不必修改 Less() 代码。方法定义如下：
func Reverse(data Interface) Interface我们可以看到 Reverse() 返回的一个 sort.Interface 接口类型，整个 Reverse() 的内部实现比较有趣：
// 定义了一个 reverse 结构类型，嵌入 Interface 接口
type reverse struct {
Interface
}
//reverse 结构类型的 Less() 方法拥有嵌入的 Less() 方法相反的行为
//Len() 和 Swap() 方法则会保持嵌入类型的方法行为
func (r reverse) Less(i, j int) bool {
return r.Interface.Less(j, i)
}
// 返回新的实现 Interface 接口的数据类型
func Reverse(data Interface) Interface {
return &reverse{data}
}了解内部原理后，可以在学生成绩排序示例中使用 Reverse() 来实现成绩升序排序：
sort.Sort(sort.Reverse(stus))
fmt.Println(stus)Search()
func Search(n int, f func(int) bool) int该方法会使用“二分查找”算法来找出能使 f(x)(0<=x<n) 返回 ture 的最小值 i。 前提条件 : f(x)(0<=x<i) 均返回 false, f(x)(i<=x<n) 均返回 ture。 如果不存在 i 可以使 f(i) 返回 ture, 则返回 n。
注意 切片必须排序好
Search() 函数一个常用的使用方式是搜索元素 x 是否在已经升序排好的切片 s 中：
x := 11
s := []int{3, 6, 8, 11, 45} // 注意已经升序排序
pos := sort.Search(len(s), func(i int) bool { return s[i] >= x })
if pos < len(s) && s[pos] == x {
fmt.Println(x, " 在 s 中的位置为：", pos)
} else {
fmt.Println("s 不包含元素 ", x)
}IntSlice 类型和Float64Slice和StringSlice
1.IntSlice 类型及[]int 排序
sort包原生支持[]int、[]float64 和[]string 三种内建数据类型切片的排序操作，即不必我们自己实现相关的 Len()、Less() 和 Swap() 方法。
sort包定义了一个 IntSlice 类型，并且实现了 sort.Interface 接口：
type IntSlice []int
func (p IntSlice) Len() int { return len(p) }
func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p IntSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
//IntSlice 类型定义了 Sort() 方法，包装了 sort.Sort() 函数
func (p IntSlice) Sort() { Sort(p) }
//IntSlice 类型定义了 SearchInts() 方法，包装了 SearchInts() 函数
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }并且提供的 sort.Ints() 方法使用了该 IntSlice 类型：
func Ints(a []int) { Sort(IntSlice(a)) }所以，对[]int 切片排序更常使用 sort.Ints()，而不是直接使用 IntSlice 类型：
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Ints(s)
fmt.Println(s) // 将会输出[1 2 3 4 5 6]如果要使用降序排序，显然要用前面提到的 Reverse() 方法：
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s) // 将会输出[6 5 4 3 2 1]如果要查找整数 x 在切片 a 中的位置，相对于前面提到的 Search() 方法，sort包提供了 SearchInts():
func SearchInts(a []int, x int) int注意，SearchInts() 的使用条件为：切片 a 已经升序排序 以下是一个错误使用的例子：
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
fmt.Println(sort.SearchInts(s, 2)) // 将会输出 0 而不是 12.Float64Slice 类型及[]float64 排序
实现与 Ints 类似，只看一下其内部实现：
type Float64Slice []float64
func (p Float64Slice) Len() int { return len(p) }
func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || isNaN(p[i]) && !isNaN(p[j]) }
func (p Float64Slice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p Float64Slice) Sort() { Sort(p) }
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }与 Sort()、IsSorted()、Search() 相对应的三个方法：
func Float64s(a []float64)
func Float64sAreSorted(a []float64) bool
func SearchFloat64s(a []float64, x float64) int要说明一下的是，在上面 Float64Slice 类型定义的 Less 方法中，有一个内部函数 isNaN()。 isNaN() 与math包中 IsNaN() 实现完全相同，sort包之所以不使用 math.IsNaN()，完全是基于包依赖性的考虑，应当看到，sort包的实现不依赖与其他任何包。
3. StringSlice 类型及[]string 排序
两个 string 对象之间的大小比较是基于“字典序”的。
实现与 Ints 类似，只看一下其内部实现：
type StringSlice []string
func (p StringSlice) Len() int { return len(p) }
func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p StringSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p StringSlice) Sort() { Sort(p) }
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }与 Sort()、IsSorted()、Search() 相对应的三个方法：
func Strings(a []string)
func StringsAreSorted(a []string) bool
func SearchStrings(a []string, x string) int排序具体的算法和复杂度
Go 的sort包中所有的排序算法在最坏的情况下会做 n log n次 比较，n 是被排序序列的长度，所以排序的时间复杂度是 O(n log n)。其大多数的函数都是用改良后的快速排序算法实现的。
