1. 3.1 sort 排序算法
sort包
实现了四种基本排序算法 插入排序 归并排序 堆排序 和 快速排序
但是这四种排序方法是不公开的 它们只被用于sort包内部使用 所以在对 数据集合 排序时不必考虑应当选择哪一种排序方法
只要实现了 sort.Interface 定义的三个方法
获取数据集合 长度的 Len()方法
比较两个元素大小的 Less()方法
和交换两个元素位置的Swap()方法
就可以顺利对数据集合进行排序
sort包会根据实际数据自动选择高效的排序算法
除此之外 为了方便对常用数据类型的操作 sort包提供了对 []int 切片 []float64切片 和 []string切片完整支持
主要包括
对基本数据类型切片的排序支持
基本数据元素查找
判断基本数据类型切片是否已经排好序
对排好序的数据集合逆序
1.1. 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包 对学生成绩排序的示例
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},
}
//打印未排序的stus数据
fmt.Println("Default:\n\t",stus)
//StuScores 已经实现了sort.Interface 接口 所以可以调用Sort函数进行排序
sort.Sort(stus)
//判断是否已经排好顺序 将会打印true
fmt.Println("IS Sorted?\n\t", sort.IsSorted(stus))
//打印排序后的stus数据
fmt.Println("Sorted:\n\t",stus)
}
该示例程序的自定义类型 StuScores 实现了sort.Interface 接口 所以可以将其对象作为sort.Sort()和sort.IsSorted()的参数传入 运行结果
Default:
[{alan 95} {hikerell 91} {acmfly 96} {leao 90}]
IS Sorted?
true
Sorted:
[{leao 90} {hikerell 91} {alan 95} {acmfly 96}]
该示例实现的是 升序排序 如果要得到降序排序结果 其实只要修改 Less()函数
//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()的内部实现比较有趣
//定义了一个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("Reverse Sorted:\n\t",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)
}
官方文档还给出了一个猜数字的小程序
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)
}
1.2. 3.1.2 sort包已经支持的内部数据类型排序
前面已经提到 sort包 原生支持[]int []float64和[]string 三种 内建数据类型 切片的排序 操作 即不必自己实现相关的Len() Less()和Swap()方法
1. IntSlice 类型及 []int 排序
由于 []int 切片排序内部实现及使用方法与[]float64和[]string类似 所以只 详细描述 该部分
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而不是1
2. 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
sort包
实现了四种基本排序算法 插入排序 归并排序 堆排序 和 快速排序
但是这四种排序方法是不公开的 它们只被用于sort包内部使用 所以在对 数据集合 排序时不必考虑应当选择哪一种排序方法
只要实现了 sort.Interface 定义的三个方法
获取数据集合 长度的 Len()方法
比较两个元素大小的 Less()方法
和交换两个元素位置的Swap()方法
就可以顺利对数据集合进行排序
sort包会根据实际数据自动选择高效的排序算法
除此之外 为了方便对常用数据类型的操作 sort包提供了对 []int 切片 []float64切片 和 []string切片完整支持
主要包括
对基本数据类型切片的排序支持
基本数据元素查找
判断基本数据类型切片是否已经排好序
对排好序的数据集合逆序
1.1. 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包 对学生成绩排序的示例
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},
}
//打印未排序的stus数据
fmt.Println("Default:\n\t",stus)
//StuScores 已经实现了sort.Interface 接口 所以可以调用Sort函数进行排序
sort.Sort(stus)
//判断是否已经排好顺序 将会打印true
fmt.Println("IS Sorted?\n\t", sort.IsSorted(stus))
//打印排序后的stus数据
fmt.Println("Sorted:\n\t",stus)
}
该示例程序的自定义类型 StuScores 实现了sort.Interface 接口 所以可以将其对象作为sort.Sort()和sort.IsSorted()的参数传入 运行结果
Default:
[{alan 95} {hikerell 91} {acmfly 96} {leao 90}]
IS Sorted?
true
Sorted:
[{leao 90} {hikerell 91} {alan 95} {acmfly 96}]
该示例实现的是 升序排序 如果要得到降序排序结果 其实只要修改 Less()函数
//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()的内部实现比较有趣
//定义了一个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("Reverse Sorted:\n\t",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)
}
官方文档还给出了一个猜数字的小程序
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)
}
1.2. 3.1.2 sort包已经支持的内部数据类型排序
前面已经提到 sort包 原生支持[]int []float64和[]string 三种 内建数据类型 切片的排序 操作 即不必自己实现相关的Len() Less()和Swap()方法
1. IntSlice 类型及 []int 排序
由于 []int 切片排序内部实现及使用方法与[]float64和[]string类似 所以只 详细描述 该部分
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而不是1
2. 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
尊贵的董事大人
英文标题不为空时 视为本栏投稿
需要关键字 描述 英文标题