🔥码云GVP开源项目 12k star Uniapp+ElementUI 功能强大 支持多语言、二开方便! 广告
# package sort `import "sort"` sort包提供了排序切片和用户自定义数据集的函数。 Example ``` 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) } // ByAge implements sort.Interface for []Person based on // the Age field. 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) // Output: // [Bob: 31 John: 42 Michael: 17 Jenny: 26] // [Michael: 17 Jenny: 26 Bob: 31 John: 42] } ``` Example (SortKeys) ``` package sort_test import ( "fmt" "sort" ) // A couple of type definitions to make the units clear. type earthMass float64 type au float64 // A Planet defines the properties of a solar system object. type Planet struct { name string mass earthMass distance au } // By is the type of a "less" function that defines the ordering of its Planet arguments. type By func(p1, p2 *Planet) bool // Sort is a method on the function type, By, that sorts the argument slice according to the function. func (by By) Sort(planets []Planet) { ps := &planetSorter{ planets: planets, by: by, // The Sort method's receiver is the function (closure) that defines the sort order. } sort.Sort(ps) } // planetSorter joins a By function and a slice of Planets to be sorted. type planetSorter struct { planets []Planet by func(p1, p2 *Planet) bool // Closure used in the Less method. } // Len is part of sort.Interface. func (s *planetSorter) Len() int { return len(s.planets) } // Swap is part of sort.Interface. func (s *planetSorter) Swap(i, j int) { s.planets[i], s.planets[j] = s.planets[j], s.planets[i] } // Less is part of sort.Interface. It is implemented by calling the "by" closure in the sorter. 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}, } // ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria. func Example_sortKeys() { // Closures that order the Planet structure. 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) } // Sort the planets by the various criteria. 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}] } ``` Example (SortMultiKeys) ``` package sort_test import ( "fmt" "sort" ) // A Change is a record of source code changes, recording user, language, and delta size. type Change struct { user string language string lines int } type lessFunc func(p1, p2 *Change) bool // multiSorter implements the Sort interface, sorting the changes within. type multiSorter struct { changes []Change less []lessFunc } // Sort sorts the argument slice according to the less functions passed to OrderedBy. func (ms *multiSorter) Sort(changes []Change) { ms.changes = changes sort.Sort(ms) } // OrderedBy returns a Sorter that sorts using the less functions, in order. // Call its Sort method to sort the data. func OrderedBy(less ...lessFunc) *multiSorter { return &multiSorter{ less: less, } } // Len is part of sort.Interface. func (ms *multiSorter) Len() int { return len(ms.changes) } // Swap is part of sort.Interface. func (ms *multiSorter) Swap(i, j int) { ms.changes[i], ms.changes[j] = ms.changes[j], ms.changes[i] } // Less is part of sort.Interface. It is implemented by looping along the // less functions until it finds a comparison that is either Less or // !Less. Note that it can call the less functions twice per call. We // could change the functions to return -1, 0, 1 and reduce the // number of calls for greater efficiency: an exercise for the reader. 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): // p < q, so we have a decision. return true case less(q, p): // p > q, so we have a decision. return false } // p == q; try the next comparison. } // All comparisons to here said "equal", so just return whatever // the final comparison reports. 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}, } // 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. func Example_sortMultiKeys() { // Closures that order the Change structure. 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. } // Simple use: Sort by user. OrderedBy(user).Sort(changes) fmt.Println("By user:", changes) // More examples. 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) // Output: // By user: [{dmr C 100} {glenda Go 200} {gri Smalltalk 80} {gri Go 100} {ken Go 200} {ken C 150} {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} {gri Go 100} {r 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}] } ``` Example (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] } // ByName implements sort.Interface by providing Less and using the Len and // Swap methods of the embedded Organs value. type ByName struct{ Organs } func (s ByName) Less(i, j int) bool { return s.Organs[i].Name < s.Organs[j].Name } // ByWeight implements sort.Interface by providing Less and using the Len and // Swap methods of the embedded Organs value. 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) // 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) } func printOrgans(s []*Organ) { for _, o := range s { fmt.Printf("%-8s (%v)\n", o.Name, o.Weight) } } ``` ## Index * [type Interface](#Interface) * [type IntSlice](#IntSlice) * [func (p IntSlice) Len() int](#IntSlice.Len) * [func (p IntSlice) Less(i, j int) bool](#IntSlice.Less) * [func (p IntSlice) Search(x int) int](#IntSlice.Search) * [func (p IntSlice) Sort()](#IntSlice.Sort) * [func (p IntSlice) Swap(i, j int)](#IntSlice.Swap) * [type Float64Slice](#Float64Slice) * [func (p Float64Slice) Len() int](#Float64Slice.Len) * [func (p Float64Slice) Less(i, j int) bool](#Float64Slice.Less) * [func (p Float64Slice) Search(x float64) int](#Float64Slice.Search) * [func (p Float64Slice) Sort()](#Float64Slice.Sort) * [func (p Float64Slice) Swap(i, j int)](#Float64Slice.Swap) * [type StringSlice](#StringSlice) * [func (p StringSlice) Len() int](#StringSlice.Len) * [func (p StringSlice) Less(i, j int) bool](#StringSlice.Less) * [func (p StringSlice) Search(x string) int](#StringSlice.Search) * [func (p StringSlice) Sort()](#StringSlice.Sort) * [func (p StringSlice) Swap(i, j int)](#StringSlice.Swap) * [func Ints(a []int)](#Ints) * [func IntsAreSorted(a []int) bool](#IntsAreSorted) * [func SearchInts(a []int, x int) int](#SearchInts) * [func Float64s(a []float64)](#Float64s) * [func Float64sAreSorted(a []float64) bool](#Float64sAreSorted) * [func SearchFloat64s(a []float64, x float64) int](#SearchFloat64s) * [func Strings(a []string)](#Strings) * [func StringsAreSorted(a []string) bool](#StringsAreSorted) * [func SearchStrings(a []string, x string) int](#SearchStrings) * [func Sort(data Interface)](#Sort) * [func Stable(data Interface)](#Stable) * [func Reverse(data Interface) Interface](#Reverse) * [func IsSorted(data Interface) bool](#IsSorted) * [func Search(n int, f func(int) bool) int](#Search) ### Examples * [Ints](#example-Ints) * [Reverse](#example-Reverse) * [package](#example-package) * [package (SortKeys)](#example-package--SortKeys) * [package (SortMultiKeys)](#example-package--SortMultiKeys) * [package (SortWrapper)](#example-package--SortWrapper) ## type [Interface](https://github.com/golang/go/blob/master/src/sort/sort.go#L12 "View Source") ``` 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](https://github.com/golang/go/blob/master/src/sort/sort.go#L233 "View Source") ``` type IntSlice []int ``` IntSlice给[]int添加方法以满足Interface接口,以便排序为递增序列。 ### func (IntSlice) [Len](https://github.com/golang/go/blob/master/src/sort/sort.go#L235 "View Source") ``` func (p IntSlice) Len() int ``` ### func (IntSlice) [Less](https://github.com/golang/go/blob/master/src/sort/sort.go#L236 "View Source") ``` func (p IntSlice) Less(i, j int) bool ``` ### func (IntSlice) [Swap](https://github.com/golang/go/blob/master/src/sort/sort.go#L237 "View Source") ``` func (p IntSlice) Swap(i, j int) ``` ### func (IntSlice) [Sort](https://github.com/golang/go/blob/master/src/sort/sort.go#L240 "View Source") ``` func (p IntSlice) Sort() ``` Sort等价于调用Sort(p) ### func (IntSlice) [Search](https://github.com/golang/go/blob/master/src/sort/search.go#L106 "View Source") ``` func (p IntSlice) Search(x int) int ``` Search等价于调用SearchInts(p, x) ## type [Float64Slice](https://github.com/golang/go/blob/master/src/sort/sort.go#L243 "View Source") ``` type Float64Slice []float64 ``` Float64Slice给[]float64添加方法以满足Interface接口,以便排序为递增序列。 ### func (Float64Slice) [Len](https://github.com/golang/go/blob/master/src/sort/sort.go#L245 "View Source") ``` func (p Float64Slice) Len() int ``` ### func (Float64Slice) [Less](https://github.com/golang/go/blob/master/src/sort/sort.go#L246 "View Source") ``` func (p Float64Slice) Less(i, j int) bool ``` ### func (Float64Slice) [Swap](https://github.com/golang/go/blob/master/src/sort/sort.go#L247 "View Source") ``` func (p Float64Slice) Swap(i, j int) ``` ### func (Float64Slice) [Sort](https://github.com/golang/go/blob/master/src/sort/sort.go#L255 "View Source") ``` func (p Float64Slice) Sort() ``` Sort等价于调用Sort(p) ### func (Float64Slice) [Search](https://github.com/golang/go/blob/master/src/sort/search.go#L109 "View Source") ``` func (p Float64Slice) Search(x float64) int ``` Search等价于调用SearchFloat64s(p, x) ## type [StringSlice](https://github.com/golang/go/blob/master/src/sort/sort.go#L258 "View Source") ``` type StringSlice []string ``` StringSlice给[]string添加方法以满足Interface接口,以便排序为递增序列。 ### func (StringSlice) [Len](https://github.com/golang/go/blob/master/src/sort/sort.go#L260 "View Source") ``` func (p StringSlice) Len() int ``` ### func (StringSlice) [Less](https://github.com/golang/go/blob/master/src/sort/sort.go#L261 "View Source") ``` func (p StringSlice) Less(i, j int) bool ``` ### func (StringSlice) [Swap](https://github.com/golang/go/blob/master/src/sort/sort.go#L262 "View Source") ``` func (p StringSlice) Swap(i, j int) ``` ### func (StringSlice) [Sort](https://github.com/golang/go/blob/master/src/sort/sort.go#L265 "View Source") ``` func (p StringSlice) Sort() ``` Sort等价于调用Sort(p) ### func (StringSlice) [Search](https://github.com/golang/go/blob/master/src/sort/search.go#L112 "View Source") ``` func (p StringSlice) Search(x string) int ``` Search等价于调用SearchStrings(p, x) ## func [Sort](https://github.com/golang/go/blob/master/src/sort/sort.go#L192 "View Source") ``` func Sort(data Interface) ``` Sort排序data。它调用1次data.Len确定长度,调用O(n\*log(n))次data.Less和data.Swap。本函数不能保证排序的稳定性(即不保证相等元素的相对次序不变)。 ## func [Stable](https://github.com/golang/go/blob/master/src/sort/sort.go#L317 "View Source") ``` 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](https://github.com/golang/go/blob/master/src/sort/sort.go#L220 "View Source") ``` func IsSorted(data Interface) bool ``` IsSorted报告data是否已经被排序。 ## func [Reverse](https://github.com/golang/go/blob/master/src/sort/sort.go#L215 "View Source") ``` func Reverse(data Interface) Interface ``` Reverse包装一个Interface接口并返回一个新的Interface接口,对该接口排序可生成递减序列。 Example ``` s := []int{5, 2, 6, 3, 1, 4} // unsorted sort.Sort(sort.Reverse(sort.IntSlice(s))) fmt.Println(s) ``` Output: ``` [6 5 4 3 2 1] ``` ## func [Search](https://github.com/golang/go/blob/master/src/sort/search.go#L59 "View Source") ``` 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] &gt;= 23 })会返回data中最小的索引i满足data[i] &gt;= 23。如果调用者想要知道23是否在切片里,它必须另外检查data[i] == 23。 搜索递减顺序的数据时,应使用&lt;=运算符代替&gt;=运算符。 下列代码尝试在一个递增顺序的整数切片中找到值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](https://github.com/golang/go/blob/master/src/sort/sort.go#L270 "View Source") ``` func Ints(a []int) ``` Ints函数将a排序为递增顺序。 Example ``` s := []int{5, 2, 6, 3, 1, 4} // unsorted sort.Ints(s) fmt.Println(s) ``` Output: ``` [1 2 3 4 5 6] ``` ## func [IntsAreSorted](https://github.com/golang/go/blob/master/src/sort/sort.go#L279 "View Source") ``` func IntsAreSorted(a []int) bool ``` IntsAreSorted检查a是否已排序为递增顺序。 ## func [SearchInts](https://github.com/golang/go/blob/master/src/sort/search.go#L83 "View Source") ``` func SearchInts(a []int, x int) int ``` SearchInts在递增顺序的a中搜索x,返回x的索引。如果查找不到,返回值是x应该插入a的位置(以保证a的递增顺序),返回值可以是len(a)。 ## func [Float64s](https://github.com/golang/go/blob/master/src/sort/sort.go#L273 "View Source") ``` func Float64s(a []float64) ``` Float64s函数将a排序为递增顺序。 ## func [Float64sAreSorted](https://github.com/golang/go/blob/master/src/sort/sort.go#L282 "View Source") ``` func Float64sAreSorted(a []float64) bool ``` Float64sAreSorted检查a是否已排序为递增顺序。 ## func [SearchFloat64s](https://github.com/golang/go/blob/master/src/sort/search.go#L92 "View Source") ``` func SearchFloat64s(a []float64, x float64) int ``` SearchFloat64s在递增顺序的a中搜索x,返回x的索引。如果查找不到,返回值是x应该插入a的位置(以保证a的递增顺序),返回值可以是len(a)。 ## func [Strings](https://github.com/golang/go/blob/master/src/sort/sort.go#L276 "View Source") ``` func Strings(a []string) ``` Strings函数将a排序为递增顺序。 ## func [StringsAreSorted](https://github.com/golang/go/blob/master/src/sort/sort.go#L285 "View Source") ``` func StringsAreSorted(a []string) bool ``` StringsAreSorted检查a是否已排序为递增顺序。 ## func [SearchStrings](https://github.com/golang/go/blob/master/src/sort/search.go#L101 "View Source") ``` func SearchStrings(a []string, x string) int ``` SearchStrings在递增顺序的a中搜索x,返回x的索引。如果查找不到,返回值是x应该插入a的位置(以保证a的递增顺序),返回值可以是len(a)。