Package sort
sort 包为切片及用户定义的集合的排序操作提供了原语.
▾ 示例
代码:
package sort_test
import (
"fmt"
"sort"
)
type Person struct {
Name string
Age int
}
func (p Person) String() string {
return fmt.Sprintf("%s: %d", p.Name, p.Age)
}
type ByAge []Person
func (a ByAge) Len() int { return len(a) }
func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age }
func Example() {
people := []Person{
{"Bob", 31},
{"John", 42},
{"Michael", 17},
{"Jenny", 26},
}
fmt.Println(people)
sort.Sort(ByAge(people))
fmt.Println(people)
}
▾ 示例 (SortKeys)
ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria.
代码:
package sort_test
import (
"fmt"
"sort"
)
type earthMass float64
type au float64
type Planet struct {
name string
mass earthMass
distance au
}
type By func(p1, p2 *Planet) bool
func (by By) Sort(planets []Planet) {
ps := &planetSorter{
planets: planets,
by: by,
}
sort.Sort(ps)
}
type planetSorter struct {
planets []Planet
by func(p1, p2 *Planet) bool
}
func (s *planetSorter) Len() int {
return len(s.planets)
}
func (s *planetSorter) Swap(i, j int) {
s.planets[i], s.planets[j] = s.planets[j], s.planets[i]
}
func (s *planetSorter) Less(i, j int) bool {
return s.by(&s.planets[i], &s.planets[j])
}
var planets = []Planet{
{"Mercury", 0.055, 0.4},
{"Venus", 0.815, 0.7},
{"Earth", 1.0, 1.0},
{"Mars", 0.107, 1.5},
}
func Example_sortKeys() {
name := func(p1, p2 *Planet) bool {
return p1.name < p2.name
}
mass := func(p1, p2 *Planet) bool {
return p1.mass < p2.mass
}
distance := func(p1, p2 *Planet) bool {
return p1.distance < p2.distance
}
decreasingDistance := func(p1, p2 *Planet) bool {
return !distance(p1, p2)
}
By(name).Sort(planets)
fmt.Println("By name:", planets)
By(mass).Sort(planets)
fmt.Println("By mass:", planets)
By(distance).Sort(planets)
fmt.Println("By distance:", planets)
By(decreasingDistance).Sort(planets)
fmt.Println("By decreasing distance:", planets)
}
▾ 示例 (SortMultiKeys)
ExampleMultiKeys demonstrates a technique for sorting a struct type using different
sets of multiple fields in the comparison. We chain together "Less" functions, each of
which compares a single field.
代码:
package sort_test
import (
"fmt"
"sort"
)
type Change struct {
user string
language string
lines int
}
type lessFunc func(p1, p2 *Change) bool
type multiSorter struct {
changes []Change
less []lessFunc
}
func (ms *multiSorter) Sort(changes []Change) {
ms.changes = changes
sort.Sort(ms)
}
func OrderedBy(less ...lessFunc) *multiSorter {
return &multiSorter{
less: less,
}
}
func (ms *multiSorter) Len() int {
return len(ms.changes)
}
func (ms *multiSorter) Swap(i, j int) {
ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i]
}
func (ms *multiSorter) Less(i, j int) bool {
p, q := &ms.changes[i], &ms.changes[j]
var k int
for k = 0; k < len(ms.less)-1; k++ {
less := ms.less[k]
switch {
case less(p, q):
return true
case less(q, p):
return false
}
}
return ms.less[k](p, q)
}
var changes = []Change{
{"gri", "Go", 100},
{"ken", "C", 150},
{"glenda", "Go", 200},
{"rsc", "Go", 200},
{"r", "Go", 100},
{"ken", "Go", 200},
{"dmr", "C", 100},
{"r", "C", 150},
{"gri", "Smalltalk", 80},
}
func Example_sortMultiKeys() {
user := func(c1, c2 *Change) bool {
return c1.user < c2.user
}
language := func(c1, c2 *Change) bool {
return c1.language < c2.language
}
increasingLines := func(c1, c2 *Change) bool {
return c1.lines < c2.lines
}
decreasingLines := func(c1, c2 *Change) bool {
return c1.lines > c2.lines
}
OrderedBy(user).Sort(changes)
fmt.Println("By user:", changes)
OrderedBy(user, increasingLines).Sort(changes)
fmt.Println("By user,<lines:", changes)
OrderedBy(user, decreasingLines).Sort(changes)
fmt.Println("By user,>lines:", changes)
OrderedBy(language, increasingLines).Sort(changes)
fmt.Println("By language,<lines:", changes)
OrderedBy(language, increasingLines, user).Sort(changes)
fmt.Println("By language,<lines,user:", changes)
}
▾ 示例 (SortWrapper)
代码:
package sort_test
import (
"fmt"
"sort"
)
type Grams int
func (g Grams) String() string { return fmt.Sprintf("%dg", int(g)) }
type Organ struct {
Name string
Weight Grams
}
type Organs []*Organ
func (s Organs) Len() int { return len(s) }
func (s Organs) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
type ByName struct{ Organs }
func (s ByName) Less(i, j int) bool { return s.Organs[i].Name < s.Organs[j].Name }
type ByWeight struct{ Organs }
func (s ByWeight) Less(i, j int) bool { return s.Organs[i].Weight < s.Organs[j].Weight }
func Example_sortWrapper() {
s := []*Organ{
{"brain", 1340},
{"heart", 290},
{"liver", 1494},
{"pancreas", 131},
{"prostate", 62},
{"spleen", 162},
}
sort.Sort(ByWeight{s})
fmt.Println("Organs by weight:")
printOrgans(s)
sort.Sort(ByName{s})
fmt.Println("Organs by name:")
printOrgans(s)
}
func printOrgans(s []*Organ) {
for _, o := range s {
fmt.Printf("%-8s (%v)\n", o.Name, o.Weight)
}
}
- func Float64s(a []float64)
- func Float64sAreSorted(a []float64) bool
- func Ints(a []int)
- func IntsAreSorted(a []int) bool
- func IsSorted(data Interface) bool
- func Search(n int, f func(int) bool) int
- func SearchFloat64s(a []float64, x float64) int
- func SearchInts(a []int, x int) int
- func SearchStrings(a []string, x string) int
- func Sort(data Interface)
- func Stable(data Interface)
- func Strings(a []string)
- func StringsAreSorted(a []string) bool
- type Float64Slice
- func (p Float64Slice) Len() int
- func (p Float64Slice) Less(i, j int) bool
- func (p Float64Slice) Search(x float64) int
- func (p Float64Slice) Sort()
- func (p Float64Slice) Swap(i, j int)
- type IntSlice
- func (p IntSlice) Len() int
- func (p IntSlice) Less(i, j int) bool
- func (p IntSlice) Search(x int) int
- func (p IntSlice) Sort()
- func (p IntSlice) Swap(i, j int)
- type Interface
- func Reverse(data Interface) Interface
- type StringSlice
- func (p StringSlice) Len() int
- func (p StringSlice) Less(i, j int) bool
- func (p StringSlice) Search(x string) int
- func (p StringSlice) Sort()
- func (p StringSlice) Swap(i, j int)
包文件
search.go
sort.go
在下面的调用图查看器中,每个节点都是一个属于本包的函数,其子节点即为它所调用的函数——或许是动态的。
根节点为包的入口点:函数可从包的外部调用。若这些函数被其它包动态地调用,
那么它们可能是未导出的或匿名的。
点击一个节点来查看该函数的源码。在源码中,可以点击它的 func
声明标记来查看其调用者。
在分析特定程序或测试时,被认定为无法访问的函数会被忽略。
func Float64s(a []float64)
Float64s 以升序排列 float64 切片
func Float64sAreSorted(a []float64) bool
Float64sAreSorted 判断 float64 切片是否已经按升序排列。
func Ints(a []int)
Ints 以升序排列 int 切片。
▾ 示例
代码:
s := []int{5, 2, 6, 3, 1, 4}
sort.Ints(s)
fmt.Println(s)
输出:
[1 2 3 4 5 6]
func IntsAreSorted(a []int) bool
IntsAreSorted 判断 int 切片是否已经按升序排列。
func IsSorted(data Interface) bool
IsSorted 返回数据是否已经排序。
func Search(n int, f func(int) bool) int
Search 使用二分查找法在 [0, n) 中寻找并返回满足 f(i) == true 的最小索引 i,
假定该索引在区间 [0, n) 内,则 f(i) == true 就蕴含了 f(i+1) == true。
也就是说,Search 要求 f 对于输入区间 [0, n) (可能为空)的前一部分为 false,
而对于剩余(可能为空)的部分为 true;Search 返回第一个 f 为 true 时的索引 i。
若该索引不存在,Search 就返回 n。(注意,“未找到”的返回值并不像 strings.Index
这类函数一样返回 -1)。Search 仅当 i 在区间 [0, n) 内时才调用 f(i)。
Search 常用于在一个已排序的,可索引的数据结构中寻找索引为 i 的值 x,例如数组或切片。
这种情况下,实参 f,一般是一个闭包,会捕获所要搜索的值,以及索引并排序该数据结构的方式。
例如,给定一个以升序排列的切片数据,调用
Search(len(data), func(i int) bool { return data[i] >= 23 })
会返回满足 data[i] >= 23 的最小索引 i。若调用者想要判断 23 是否在此切片中,
就必须单独测试 data[i] == 23 的值。
搜索降以序排列的数据,需使用 <= 操作符,而非 >= 操作符。
补全上面的例子, 以下代码试图从以升序排列的整数切片中寻找值 x 的索引:
x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
// x 为 data[i]
} else {
// x 不在 data 中,但 i 可作为它的索引插入。
}
还有个更有趣的例子,此程序会猜你所想的数字:
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)
}
func SearchFloat64s(a []float64, x float64) int
SearchFloat64s 在float64s切片中搜索x并返回索引
如Search函数所述. 返回可以插入x值的索引位置,如果x
不存在,返回数组a的长度
切片必须以升序排列
func SearchInts(a []int, x int) int
SearchInts 在ints切片中搜索x并返回索引
如Search函数所述. 返回可以插入x值的索引位置,如果x
不存在,返回数组a的长度
切片必须以升序排列
func SearchStrings(a []string, x string) int
SearchFloat64s 在strings切片中搜索x并返回索引
如Search函数所述. 返回可以插入x值的索引位置,如果x
不存在,返回数组a的长度
切片必须以升序排列
func Sort(data Interface)
Sort 对 data 进行排序。
它调用一次 data.Len 来决定排序的长度 n,调用 data.Less 和 data.Swap 的开销为
O(n*log(n))。此排序为不稳定排序。
func Stable(data Interface)
Stable sorts data while keeping the original order of equal elements.
It makes one call to data.Len to determine n, O(n*log(n)) calls to
data.Less and O(n*log(n)*log(n)) calls to data.Swap.
func Strings(a []string)
Strings 以升序排列 string 切片。
func StringsAreSorted(a []string) bool
StringsAreSorted 判断 string 切片是否已经按升序排列。
type Float64Slice []float64
Float64Slice 针对 []float6 实现接口的方法,以升序排列。
func (Float64Slice) Len
func (p Float64Slice) Len() int
func (Float64Slice) Less
func (p Float64Slice) Less(i, j int) bool
func (Float64Slice) Search
func (p Float64Slice) Search(x float64) int
Search 返回以调用者和x为参数调用SearchFloat64s后的结果
func (Float64Slice) Sort
func (p Float64Slice) Sort()
Sort 为便捷性方法
func (Float64Slice) Swap
func (p Float64Slice) Swap(i, j int)
type IntSlice []int
IntSlice 针对 []int 实现接口的方法,以升序排列。
func (IntSlice) Len
func (p IntSlice) Len() int
func (IntSlice) Less
func (p IntSlice) Less(i, j int) bool
func (IntSlice) Search
func (p IntSlice) Search(x int) int
Search 返回以调用者和x为参数调用SearchInts后的结果
func (IntSlice) Sort
func (p IntSlice) Sort()
Sort 为便捷性方法
func (IntSlice) Swap
func (p IntSlice) Swap(i, j int)
type Interface interface {
Len() int
Less(i, j int) bool
Swap(i, j int)
}
任何实现了 sort.Interface 的类型(一般为集合),均可使用该包中的方法进行排序。
这些方法要求集合内列出元素的索引为整数。
func Reverse(data Interface) Interface
Reverse returns the reverse order for data.
▾ 示例
代码:
s := []int{5, 2, 6, 3, 1, 4}
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s)
输出:
[6 5 4 3 2 1]
type StringSlice []string
StringSlice 针对 []string 实现接口的方法,以升序排列。
func (StringSlice) Len
func (p StringSlice) Len() int
func (StringSlice) Less
func (p StringSlice) Less(i, j int) bool
func (StringSlice) Search
func (p StringSlice) Search(x string) int
Search 返回以调用者和x为参数调用SearchStrings后的结果
func (StringSlice) Sort
func (p StringSlice) Sort()
Sort 为便捷性方法
func (StringSlice) Swap
func (p StringSlice) Swap(i, j int)