命令记不住

1.sort包介绍

使用sort包进行排序时无需具体考虑使用哪种排序方式

func insertionSort(data Interface,a,b int)
func heapSort(data Interface,a,b int)
func quickSort(data Interface,a,b,maxDepth int)

sort.Interface接口定义了三个方法。注意sort包中接口Interface这个名字，是以大些字母I开头，不要和interface关键字混淆，这里就是一个接口名而已

type Interface interface{
//Len 为集合内元素的总数
Len() int
//如果index为i的元素小于index为j的元素，则返回true,否则返回false
Less(i,j int)bool
//Swap 交换索引为i和j的元素
Swap(i,j int)
}

这三个方法分别是：获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法。只要实现了这三个方法，就可以对数据集合进行排序，sort包会根据实际数据自动选择高效的排序算法

sort包原生支持[]int、[]float64和[]string三种内建数据类型切片的排序操作，既不必程序员自己实现相关的Len()、Less()、和Swap()方法

1.sort包如何定义排序操作

type IntSlice []int

先通过[]int来定义新类型IntSlice,然后在IntSlice上定义三个方法Len(),Less(i,j int),Swap(i,j int),实现了这三个方法也就意味着实现了sort.Interface接口

方法func(p InSlice) Sort() 通过调用sort.Sort(P)函数来实现排序，而Sort(p)需要参数p是sort.Interface类型，但IntSlice实现了这三个接口方法，也就是sort.Interface类型，因此可以调用其排序结果，其他[]float64和[]string的排序也基本上按照这种方式来实现

其他类型并没有在包中给出实现方法，需要自己定义实现

func (p IntSlice)Len()int
func (p IntSlice)Less(i,j int)bool{return p[i]<p[j]}
func (p IntSlice)Swap(i,j int)
func (p IntSlice)Sort(){Sort(p)}

如下是[]int和[]string排序的实例

package main

import (
    "fmt"
    "sort"
)

func main() {
    a := []int{33, 5, 3, -6, 19, 11, -14}
    sort.Ints(a)
    fmt.Println("排序：", a)

    sort.Sort(sort.Reverse(sort.IntSlice(a)))
    fmt.Println("降序: ", a)

    s := []string{"surface", "ipad", "Lenovo", "mac", "thinkpad", "联想"}
    sort.Strings(s)
    fmt.Println("排序：", s)

    sort.Sort(sort.Reverse(sort.StringSlice(s)))
    fmt.Printf("降序: %v\n", s)
}

程序输出：

排序： [-14 -6 3 5 11 19 33]
降序:  [33 19 11 5 3 -6 -14]
排序： [Lenovo ipad mac surface thinkpad 联想]
降序: [联想 thinkpad surface mac ipad Lenovo]

默认结果都是升序排列，如果使用sort.Reverse则可进行降序排列

2.sort包相关方法功能的注释

package main

//将类型为floadt64的slice以升序方式排序
func Float64s(a []float64)

//判断是否已经进行排序
func Float64sAreSorted(a []float64) bool

//Ints以升序排列int切片
func Ints(a []int)

//判断int切片是否已经按升序排列
func IntsAreSorted(a []int) bool

//IsSorted判断数据是否已经排列。包括各种可排序的数据类型判断
func IsSorted(data Interface) bool

//String以升序排列string切片
func Strings(a []string)

//判断string切片是否按升序排列
func StringsAreSorted(a []string) bool

//search使用二分法进行查找,Search()方法会使用“二分查找”算法来搜索某制定切片[0:n]
//并返回能够使f(i)=true的最小的i(0<=i<n)值，并且会假定如果f(i)=true,则f(i+1)=true
//既对于切片[0:n]，i之前的切片元素会使f()函数返回false,i及i之后的元素会使f()函数返回true
//但是，当在切片中无法找到使f(i)=true的i时，此时切片元素都不能使f()函数返回true,Search()方法会返回n而不是返回-1

//Search常用于在一个已排序的、可索引的数据结构中寻找索引为i的值x，例如数组或切片
//这种情况下实参f一般是一个闭包，会捕获所要搜索的值，以及索引并排序该数据结构的方式
func Search(n int,f func(int)bool)int

//SearchFloat64s 在float64切片中搜索x并返回索引，如Search函数那样
//返回可以插入x值的索引位置，如果x不存在，返回数组a的长度切片必须以升序排列
func SearchFloat64s(a []float64,x float64)int

//SearchInts在ints切片搜索x并返回索引，如Search函数那样，返回可以插入x值的索引位置，如果x不存在，返回数组a的长度切片必须以升序排列
func SearchInts(a []int,x int)int

//SearchFloat64s 在string切片中搜索x并返回索引，如Search函数所述，返回可以插入x值的索引位置，如果x不存在，返回数组a的长度切片必须以升序排序
func SearchStrings(a []string,x string)int

//其中需要注意的是，以上三种查找方法对应的slice必须按照升序进行排序，否则会出现奇怪的结果

//Sort 对 data进行排序，它调用一次data.Len 来决定排序的长度n 调用data.Less和data.Swap的开销为O(n*log(n)),此排序为不稳定排序，它根据不同形式决定使用
//不同的排序方法（插入排序、堆排序、快速排序）
func Sort(data Interface)

//Stable对data进行排序，排序过程中，如果data中存在相等的元素，则它们原来的顺序不会改变，既如果有两个相等的元素num 他们初始index分别为i和j,并且
//i < j ,则利用Stable 对data进行排序后，i依然小于j,直接利用sort进行排序则不能够保证这一点
func Stable(data Interface)

2.自定义sort.Interface排序

如果是[]int、[]float64和string之外的某个具体结构的排序，就需要自己实现sort.Interface了，数据集合（包括自定义数据类型的集合）排序需要实现sort.Interface接口的三个方法，既:Len()、Swap(i,j int)、Less(i,j int)数据集合实现这三个方法后，既可调用该包的Sort()方法进行排序。Sort(data Interface)方法内部会使用quickSort()来进行集合的排序。而quickSort()会根据实际情况来选择排序算法

任何实现了sort.Interface的类型(一般为集合)，均可使用该包中的方法进行排序。这些方法要求集合内列出元素的索引为整数。

例如

package main

import (
    "fmt"
    "sort"
)

type person struct {
    Name string
    Age  int
}

type personSlice []person

func (s personSlice) Len() int           { return len(s) }
func (s personSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s personSlice) Less(i, j int) bool { return s[i].Age < s[j].Age }

func main() {
    a := personSlice{
        {Name: "Jim", Age: 15},
        {Name: "石惊天", Age: 22},
        {Name: "Горький", Age: 57},
        {Name: "박 빅 브라더", Age: 32},
        {Name: "Li Wei", Age: 42},
    }
    sort.Sort(a)
    fmt.Println("Sort:", a)

    sort.Stable(a)
    fmt.Println("Stable:", a)

}

该示例程序的自定义类型personSlice实现了sort.Interface接口，所以可以将其对象作为sort.Sort()和sort.Stable()的参数传入，运行结果如下

Sort: [{Jim 15} {石惊天 22} {박 빅 브라더 32} {Li Wei 42} {Горький 57}]
Stable: [{Jim 15} {石惊天 22} {박 빅 브라더 32} {Li Wei 42} {Горький 57}]

3.sort.Slice排序

为每种类型提供一个特定的sort.Interface的实现很繁琐，可以利用sort.Slice函数，把Less(i,j int)作为一个比较回调函数，简单地传递给sort.Slice进行排序。这种方法虽然方便，但是不建议使用，因为在sort.Slice中使用了reflect

例如：

package main

import (
    "fmt"
    "sort"
)

type River struct {
    Name   string
    Length int
}

func main() {
    Rivers := []River{
        {"刚果河", 4640},
        {"尼罗河", 6670},
        {"亚马孙河", 6400},
        {"黄河", 5464},
        {"鄂毕河", 3650},
        {"恒河", 2510},
        {"密西西比河", 6021},
        {"叶尼塞河", 5539},
        {"长江", 6300},
    }

    // less作为回调函数
    sort.Slice(Rivers, func(i, j int) bool {
        return Rivers[i].Length >= Rivers[j].Length
    })
    fmt.Println(Rivers)

}

程序输入:

[{尼罗河 6670} {亚马孙河 6400} {长江 6300} {密西西比河 6021} {叶尼塞河 5539} {黄河 5464} {刚果河 4640} {鄂毕河 3650} {恒河 2510}]