Sort
Overview
包sort提供排序切片和用户自定义集合的原语函数(Functions)
func Float64s(a []float64)
Float64s以升序排序切片,NaN(not a number)被视为小于其它值func Float64sAreSorted(a []float64) bool
检查float64s的切片是否已升序排序,NaN(not a number)被视为小于其它值func Ints(a []int)
以升序排序整型切片func IntsAreSorted(a []int) bool
检查整型切片是否是由升序排序func IsSorted(data Interface) bool
IsSorted检查data是否已排序func Search(n int, f func(int) bool) int
Search使用二分查找并返回最小的索引[0, n)符合f(i)是true,确保f(i) == true暗示着f(i + 1) == true,就是说,Search要求返回false对于一些输入[0,n)前缀(可能是空),剩下的为true，可能为空,Search返回第一个满足f(i) == true的索引,如果没有这样的索引,返回n.一个共同的使用Search是在已排序的集合,可索引的数据结构切片或数组func SearchFloat64s(a []float64, x float64) int
SearchFloat64s在已升序排序的切片a中搜索符合插入x的位置 (可能为len(a)),该切片必须以升序排序.func SearchInts(a []int, x int) int
SearchInts在已升序排序的切片a中搜索符合插入x的位置 (可能为len(a)),该切片必须以升序排序.func SerachStrings(a []string, x string) int
SearchStrings在已升序排序的切片a中搜索符合插入x的位置 (可能为len(a)),该切片必须以升序排序.func Slice(slice interface{}, less func(i, j int) bool)
Slice提供了给slice排序按指定的less function. 该函数不保证排序是稳定的,对于需要排序稳定的,使用SliceStable. 该函数panic,如果提供的slice不是切片func SliceSorted(slice interface{}, less func(i, j int) bool) bool
SliceSorted检查slice是否已排序 如果slice不是切片,将会导致panic.func SliceStable(slice interface{}, less func(i, j int) bool)
SliceStable以稳定排序算法排序slice 如果slice不是切片,将会导致panicfunc Sort(data Interface)
Sort根据data实现的sort.Interface提供的接口方法进行排序,由data.Len提供终止的n,data.Less实现O(n*logn)复杂度的排序,data.Swap进行交换func Stable(data Interface)
Stable提供了Sort的稳定排序形式func Strings(a []string)
Strings以升序排序字符串切片.func StringsAreSorted(a []string) bool
StringsAreSorted检查字符串切片是否以升序排序.type Float64Slice
type Float64Slice []float64
func (p Float64Slice) Len() int
func (p Float64Slice) Less(i, j int) bool
func (p Float64Slice) Swap(i, j int) bool
func (p Float64Slice) Search(x float64)
返回接收者为p的SerachFloat64s的结果func (p Float64Slice) Sort()
type IntSlice
type IntSlice []int
func (p IntSlice) Len() int
func (p IntSlice) Less(i, j int) bool
func (p IntSlice) Swap(i, j int)
func (p IntSlice) Search(x int) int
Search返回应用SearchInts到接收者p和xfunc (p IntSlice) Sort()
Sort是sort.Sort(p)的简单表示type Interface
type Interface interface {
Less(i, j int) bool
Len() int
Swap(i, j int)
}
func Reverse(data Interface) Interface
Reverse返回data的逆序type StringSlice
type StringSlice []string
func (p StringSlice) Len() int
func (p StringSlice) Less(i, j int) bool
func (p StringSlice) Swap(i, j int) bool
func (p StringSlice) Search(x string) int
func (p StringSlice) Sort()
Examples
两种方法排序
package sort_test
import (
"sort"
"fmt"
)
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 (ba ByAge) Len() int {
return len(ba)
}
func (ba ByAge) Less(i, j int) bool {
return ba[i].Age < ba[j].Age
}
func (ba ByAge) Swap(i, j int) {
ba[i], ba[j] = ba[j], ba[i]
}
func Example() {
people := []Person {
{"Bob", 31},
{"John", 42},
{"Michael", 17},
{"Jenny", 26},
}
fmt.Println(people)
// 第一种方法: 通过实现sort.Interface接口进行排序
sort.Sort(ByAge(people))
fmt.Println(people)
// 第二种方法: 如果原生类型是切片,可以直接提供Less函数排序
sort.Slice(people, func(i, j int) bool {
return people[i].Age > people[j].Age
})
fmt.Println(people)
// Output:
// [Bob: 31 John: 42 Michael: 17 Jenny: 26]
// [Michael: 17 Jenny: 26 Bob: 31 John: 42]
// [John: 42 Bob: 31 Jenny: 26 Michael: 17]
}
按照指定key排序
package sort_test
import (
"sort"
"fmt"
)
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 (ps *PlanetSorter) Len() int {
return len(ps.planets)
}
func (ps *PlanetSorter) Less(i, j int) bool {
return ps.by(&ps.planets[i], &ps.planets[j])
}
func (ps *PlanetSorter) Swap(i, j int) {
ps.planets[i], ps.planets[j] = ps.planets[j], ps.planets[i]
}
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(p2, p1)
}
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)
// Output: By name: [{Earth 1 1} {Mars 0.107 1.5} {Mercury 0.055 0.4} {Venus 0.815 0.7}]
// By mass: [{Mercury 0.055 0.4} {Mars 0.107 1.5} {Venus 0.815 0.7} {Earth 1 1}]
// By distance: [{Mercury 0.055 0.4} {Venus 0.815 0.7} {Earth 1 1} {Mars 0.107 1.5}]
// By decreasing distance: [{Mars 0.107 1.5} {Earth 1 1} {Venus 0.815 0.7} {Mercury 0.055 0.4}]
}
组合多个key进行排序
package sort_test
import (
"sort"
"fmt"
)
type Change struct {
user string
language string
line int
}
type lessFunc func(p1, p2 *Change) bool
type MultiSorter struct {
changes []Change
less []lessFunc
}
func OrderBy(less ...lessFunc) *MultiSorter {
return &MultiSorter {
less: less,
}
}
func (ms *MultiSorter) Sort(changes []Change) {
ms.changes = changes
sort.Sort(ms)
}
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 {
for _, less := range ms.less {
switch {
case less(&ms.changes[i], &ms.changes[j]) :
return true
case less(&ms.changes[j], &ms.changes[i]):
return false
}
}
return ms.less[len(ms.less) - 1](&ms.changes[i], &ms.changes[j])
}
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.line < c2.line
}
decreasingLines := func(c1, c2 *Change) bool {
return increasingLines(c2, c1)
}
OrderBy(user).Sort(changes)
fmt.Println("By user:", changes)
OrderBy(user, increasingLines).Sort(changes)
fmt.Println("By user,<lines:", changes)
OrderBy(user, decreasingLines).Sort(changes)
fmt.Println("By user,>lines:", changes)
OrderBy(language, increasingLines).Sort(changes)
fmt.Println("By language,<lines:", changes)
OrderBy(language, increasingLines, user).Sort(changes)
fmt.Println("By language,<lines,user:", changes)
// Output:
// By user: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
// By user,<lines: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken C 150} {ken Go 200} {r Go 100} {r C 150} {rsc Go 200}]
// By user,>lines: [{dmr C 100} {glenda Go 200} {gri Go 100} {gri Smalltalk 80} {ken Go 200} {ken C 150} {r C 150} {r Go 100} {rsc Go 200}]
// By language,<lines: [{dmr C 100} {ken C 150} {r C 150} {r Go 100} {gri Go 100} {ken Go 200} {glenda Go 200} {rsc Go 200} {gri Smalltalk 80}]
// By language,<lines,user: [{dmr C 100} {ken C 150} {r C 150} {gri Go 100} {r Go 100} {glenda Go 200} {ken Go 200} {rsc Go 200} {gri Smalltalk 80}]
}
组合封装成sort.Interface接口
package sort_test
import (
"sort"
"fmt"
)
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 printOrgans(s []*Organ) {
for _, v := range s {
fmt.Printf("%-8s (%v)\n", v.Name, v.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)
// Output:
// Organs by weight:
// prostate (62g)
// pancreas (131g)
// spleen (162g)
// heart (290g)
// brain (1340g)
// liver (1494g)
// Organs by name:
// brain (1340g)
// heart (290g)
// liver (1494g)
// pancreas (131g)
// prostate (62g)
// spleen (162g)
}
Next Post