# 3.1 sort —— 排序算法 #
该包实现了四种基本排序算法：插入排序、归并排序、堆排序和快速排序。
但是这四种排序方法是不公开的，它们只被用于sort包内部使用。所以在对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了sort.Interface定义的三个方法：获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法，就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。
除此之外，为了方便对常用数据类型的操作，sort包提供了对[]int切片、[]float64切片和[]string切片完整支持，主要包括：
- 对基本数据类型切片的排序支持
- 基本数据元素查找
- 判断基本数据类型切片是否已经排好序
- 对排好序的数据集合逆序
## 3.1.1 数据集合排序 ##
前面已经提到过，对数据集合（包括自定义数据类型的集合）排序需要实现sort.Interface接口的三个方法，我们看以下该接口的定义：
type Interface interface {
// 获取数据集合元素个数
Len() int
// 如果i索引的数据小于j所以的数据，返回true，不会调用
// 下面的Swap()，即数据升序排序。
Less(i, j int) bool
// 交换i和j索引的两个元素的位置
Swap(i, j int)
}
数据集合实现了这三个方法后，即可调用该包的Sort()方法进行排序。
Sort()方法定义如下：
func Sort(data Interface)
Sort()方法惟一的参数就是待排序的数据集合。
该包还提供了一个方法可以判断数据集合是否已经排好顺序，该方法的内部实现依赖于我们自己实现的Len()和Less()方法：
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
}
下面是一个使用sort包对学生成绩排序的示例：
```golang
package main
import (
"fmt"
"sort"
)
//学生成绩结构体
type StuScore struct {
//姓名
name string
//成绩
score int
}
type StuScores []StuScore
//Len()
func (s StuScores) Len() int {
return len(s)
}
//Less():成绩将有低到高排序
func (s StuScores) Less(i, j int) bool {
return s[i].score < s[j].score
}
//Swap()
func (s StuScores) Swap(i, j int) {
s[i], s[j] = s[j], s[i]
}
func main() {
stus := StuScores{
{"alan", 95},
{"hikerell", 91},
{"acmfly", 96},
{"leao", 90}}
fmt.Println("Default:")
//原始顺序
for _, v := range stus {
fmt.Println(v.name, ":", v.score)
}
fmt.Println()
//StuScores已经实现了sort.Interface接口
sort.Sort(stus)
fmt.Println("Sorted:")
//排好序后的结构
for _, v := range stus {
fmt.Println(v.name, ":", v.score)
}
//判断是否已经排好顺序，将会打印true
fmt.Println("IS Sorted?", sort.IsSorted(stus))
}
```
程序该示例程序的自定义类型StuScores实现了sort.Interface接口，所以可以将其对象作为sort.Sort()和sort.IsSorted()的参数传入。运行结果：
======Default======
alan : 95
hikerell : 91
acmfly : 96
leao : 90
======Sorted=======
leao : 90
hikerell : 91
alan : 95
acmfly : 96
IS Sorted? true
该示例实现的是升序排序，如果要得到降序排序结果，其实只要修改Less()函数：
```golang
//Less():成绩降序排序,只将小于号修改为大于号
func (s StuScores) Less(i, j int) bool {
return s[i].score > s[j].score
}
```
此外，*sort*包提供了Reverse()方法，可以允许将数据按Less()定义的排序方式逆序排序，而不必修改Less()代码。方法定义如下：
func Reverse(data Interface) Interface
我们可以看到Reverse()返回的一个sort.Interface接口类型，整个Reverse()的内部实现比较有趣：
```golang
//定义了一个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()来实现成绩升序排序：
```golang
sort.Sort(sort.Reverse(stus))
for _, v := range stus {
fmt.Println(v.name, ":", v.score)
}
```
最后一个方法：Search()
func Search(n int, f func(int) bool) int
官方文档这样描述该方法：
>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。
Search()函数一个常用的使用方式是搜索元素x是否在已经升序排好的切片s中：
```golang
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)
}
```
官方文档还给出了一个猜数字的小程序：
```golang
func GuessingGame() {
var s string
fmt.Printf("Pick an integer from 0 to 100.\n")
answer := sort.Search(100, func(i int) bool {
fmt.Printf("Is your number <= %d? ", i)
fmt.Scanf("%s", &s)
return s != "" && s[0] == 'y'
})
fmt.Printf("Your number is %d.\n", answer)
}
```
## 3.1.2 *sort*包已经支持的内部数据类型排序
前面已经提到，*sort*包原生支持[]int、[]float64和[]string三种内建数据类型切片的排序操作，即不必我们自己实现相关的Len()、Less()和Swap()方法。
**1. IntSlice类型及[]int排序**
由于[]int切片排序内部实现及使用方法与[]float64和[]string类似，所以只详细描述该部分。
*sort*包定义了一个IntSlice类型，并且实现了sort.Interface接口：
```golang
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类型：
```goalng
func Ints(a []int) { Sort(IntSlice(a)) }
```
所以，对[]int切片排序是更常使用sort.Ints()，而不是直接使用IntSlice类型：
```golang
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Ints(s)
fmt.Println(s) //将会输出[1 2 3 4 5 6]
```
如果要使用降序排序，显然要用前面提到的Reverse()方法：
```golang
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():
```golang
func SearchInts(a []int, x int) int
```
注意，SearchInts()的使用条件为：**切片a已经升序排序**
```golang
s := []int{5, 2, 6, 3, 1, 4} // 未排序的切片数据
sort.Ints(s) //排序后的s为[1 2 3 4 5 6]
fmt.Println(sort.SearchInts(s, 3)) //将会输出2
```
**2. Float64Slice类型及[]float64排序**
实现与Ints类似，只看一下其内部实现：
```golang
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类似，只看一下其内部实现：
```golang
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
# 导航 #
- [第三章 数据结构与算法](/chapter03/03.0.md)
- 下一节：index/suffixarray — 后缀数组实现子字符串查询
- 简介
- 第一章 输入输出 (Input/Output)
- 1.1 io — 基本的 IO 接口
- 1.2 ioutil — 方便的 IO 操作函数集
- 1.3 fmt — 格式化 IO
- 1.4 bufio — 缓存 IO
- 第二章 文本
- 2.1 strings — 字符串操作
- 2.2 bytes — byte slice 便利操作
- 2.3 strconv — 字符串和基本数据类型之间转换
- 2.4 regexp — 正则表达式
- 2.5 unicode — Unicode 码点、UTF-8/16 编码
- 第三章 数据结构与算法
- 3.1 sort — 排序算法
- 3.2 index/suffixarray — 后缀数组实现子字符串查询
- 3.3 container — 容器数据类型：heap、list 和 ring
- 第四章 日期与时间
- 4.1 主要类型概述
- 4.2 时区
- 4.3 Time类型详解
- 4.4 定时器
- 第六章 文件系统
- 6.1 os — 平台无关的操作系统功能实现
- 6.2 path/filepath — 操作路径
- 第七章 数据持久存储与交换
- 7.1 database/sql — SQL/SQL-Like 数据库操作接口
- 第八章 数据压缩与归档
- 8.1 flate * DEFLATE 压缩算法
- 第九章 测试
- 9.1 testing * 单元测试
- 9.2 testing * 基准测试
- 9.3 testing * 子测试
- 9.4 testing * 运行并验证示例
- 9.5 testing * 其他功能
- 9.6 httptest * HTTP 测试辅助工具
- 9.7 总结
- 第十章 进程、线程与 goroutine
- 10.1 创建进程
- 10.2 进程属性和控制
- 10.3 线程
- 10.4 进程间通信
- 第十三章 应用构建 与 debug
- 13.1 flag * 命令行参数解析
- 13.2 log * 日志记录
- 13.3 expvar * 公共变量的标准化接口
- 13.4 runtime/debug * 运行时的调试工具