15
Golang标准库——sort
source link: https://studygolang.com/articles/31226
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
sort
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 main() {
people := []Person{
{"Bob", 31},
{"John", 42},
{"Michael", 17},
{"Jenny", 26},
}
fmt.Println(people)
sort.Sort(ByAge(people))
fmt.Println(people)
}
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 // Closure used in the Less method.
}
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 main() {
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)
}
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]
// Try all but the last comparison.
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 main() {
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 // Note: > orders downwards.
}
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)
}
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 main() {
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)
}
}
type Interface
type Interface interface {
// Len方法返回集合中的元素个数
Len() int
// Less方法报告索引i的元素是否比索引j的元素小
Less(i, j int) bool
// Swap方法交换索引i和j的两个元素
Swap(i, j int)
}
一个满足sort.Interface接口的（集合）类型可以被本包的函数进行排序。方法要求集合中的元素可以被整数索引。
type IntSlice
type IntSlice []int
IntSlice给[]int添加方法以满足Interface接口，以便排序为递增序列。
func (IntSlice) Len
func (p IntSlice) Len() int
func (IntSlice) Less
func (p IntSlice) Less(i, j int) bool
func (IntSlice) Swap
func (p IntSlice) Swap(i, j int)
func (IntSlice) Sort
func (p IntSlice) Sort()
Sort等价于调用Sort(p)
func (IntSlice) Search
func (p IntSlice) Search(x int) int
Search等价于调用SearchInts(p, x)
type Float64Slice
type Float64Slice []float64
Float64Slice给[]float64添加方法以满足Interface接口，以便排序为递增序列。
func (Float64Slice) Len
func (p Float64Slice) Len() int
func (Float64Slice) Less
func (p Float64Slice) Less(i, j int) bool
func (Float64Slice) Swap
func (p Float64Slice) Swap(i, j int)
func (Float64Slice) Sort
func (p Float64Slice) Sort()
Sort等价于调用Sort(p)
func (Float64Slice) Search
func (p Float64Slice) Search(x float64) int
Search等价于调用SearchFloat64s(p, x)
type StringSlice
type StringSlice []string
StringSlice给[]string添加方法以满足Interface接口，以便排序为递增序列。
func (StringSlice) Len
func (p StringSlice) Len() int
func (StringSlice) Less
func (p StringSlice) Less(i, j int) bool
func (StringSlice) Swap
func (p StringSlice) Swap(i, j int)
func (StringSlice) Sort
func (p StringSlice) Sort()
Sort等价于调用Sort(p)
func (StringSlice) Search
func (p StringSlice) Search(x string) int
Search等价于调用SearchStrings(p, x)
func Sort
func Sort(data Interface)
Sort排序data。它调用1次data.Len确定长度，调用O(n*log(n))次data.Less和data.Swap。本函数不能保证排序的稳定性（即不保证相等元素的相对次序不变）。
func Stable
func Stable(data Interface)
Stable排序data，并保证排序的稳定性，相等元素的相对次序不变。
它调用1次data.Len，O(n log(n))次data.Less和O(n log(n)*log(n))次data.Swap。
func IsSorted
func IsSorted(data Interface) bool
IsSorted报告data是否已经被排序。
func Reverse
func Reverse(data Interface) Interface
Reverse包装一个Interface接口并返回一个新的Interface接口，对该接口排序可生成递减序列。
func main() {
s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Sort(sort.Reverse(sort.IntSlice(s)))
fmt.Println(s)
// [6 5 4 3 2 1]
}
func Search
func Search(n int, f func(int) bool) int
Search函数采用二分法搜索找到[0, n)区间内最小的满足f(i)==true的值i。也就是说，Search函数希望f在输入位于区间[0, n)的前面某部分（可以为空）时返回假，而在输入位于剩余至结尾的部分（可以为空）时返回真；Search函数会返回满足f(i)==true的最小值i。如果没有该值，函数会返回n。注意，未找到时的返回值不是-1，这一点和strings.Index等函数不同。Search函数只会用区间[0, n)内的值调用f。
一般使用Search找到值x在插入一个有序的、可索引的数据结构时，应插入的位置。这种情况下，参数f（通常是闭包）会捕捉应搜索的值和被查询的数据集。
例如，给定一个递增顺序的切片，调用Search(len(data), func(i int) bool { return data[i] >= 23 })会返回data中最小的索引i满足data[i] >= 23。如果调用者想要知道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 is present at data[i]
} else {
// x is not present in data,
// but i is the index where it would be inserted.
}
一个更古怪的例子，下面的程序会猜测你持有的数字：
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 Ints
func Ints(a []int)
Ints函数将a排序为递增顺序。
func main() {
s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(s)
fmt.Println(s)
// [1 2 3 4 5 6]
}
func IntsAreSorted
func IntsAreSorted(a []int) bool
IntsAreSorted检查a是否已排序为递增顺序。
func SearchInts
func SearchInts(a []int, x int) int
SearchInts在递增顺序的a中搜索x，返回x的索引。如果查找不到，返回值是x应该插入a的位置（以保证a的递增顺序），返回值可以是len(a)。
func Float64s
func Float64s(a []float64)
Float64s函数将a排序为递增顺序。
func Float64sAreSorted
func Float64sAreSorted(a []float64) bool
Float64sAreSorted检查a是否已排序为递增顺序。
func SearchFloat64s
func SearchFloat64s(a []float64, x float64) int
SearchFloat64s在递增顺序的a中搜索x，返回x的索引。如果查找不到，返回值是x应该插入a的位置（以保证a的递增顺序），返回值可以是len(a)。
func Strings
func Strings(a []string)
Strings函数将a排序为递增顺序。
func StringsAreSorted
func StringsAreSorted(a []string) bool
StringsAreSorted检查a是否已排序为递增顺序。
func SearchStrings
func SearchStrings(a []string, x string) int
SearchStrings在递增顺序的a中搜索x，返回x的索引。如果查找不到，返回值是x应该插入a的位置（以保证a的递增顺序），返回值可以是len(a)。
有疑问加站长微信联系
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK