...

Package sort

import "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)
}

// 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]
}

示例 (SortKeys)

ExampleSortKeys demonstrates a technique for sorting a struct type using programmable sort criteria.

代码:

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}]
}

示例 (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"
)

// 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}]

}

示例 (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)
    }
}

func Float64s

func Float64s(a []float64)

Float64s 以升序排列 float64 切片

func Float64sAreSorted

func Float64sAreSorted(a []float64) bool

Float64sAreSorted 判断 float64 切片是否已经按升序排列。

func Ints

func Ints(a []int)

Ints 以升序排列 int 切片。

示例

代码:

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 判断 int 切片是否已经按升序排列。

func IsSorted

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

func SearchFloat64s(a []float64, x float64) int

SearchFloat64s 在float64s切片中搜索x并返回索引 如Search函数所述. 返回可以插入x值的索引位置,如果x 不存在,返回数组a的长度 切片必须以升序排列

func SearchInts

func SearchInts(a []int, x int) int

SearchInts 在ints切片中搜索x并返回索引 如Search函数所述. 返回可以插入x值的索引位置,如果x 不存在,返回数组a的长度 切片必须以升序排列

func SearchStrings

func SearchStrings(a []string, x string) int

SearchFloat64s 在strings切片中搜索x并返回索引 如Search函数所述. 返回可以插入x值的索引位置,如果x 不存在,返回数组a的长度 切片必须以升序排列

func Sort

func Sort(data Interface)

Sort 对 data 进行排序。 它调用一次 data.Len 来决定排序的长度 n,调用 data.Less 和 data.Swap 的开销为 O(n*log(n))。此排序为不稳定排序。

func Stable

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

func Strings(a []string)

Strings 以升序排列 string 切片。

func StringsAreSorted

func StringsAreSorted(a []string) bool

StringsAreSorted 判断 string 切片是否已经按升序排列。

type Float64Slice

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

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

type Interface interface {
    // Len is the number of elements in the collection.
    // Len 为集合内元素的总数
    Len() int
    // Less reports whether the element with
    // index i should sort before the element with index j.
    //
    // Less 返回索引为 i 的元素是否应排在索引为 j 的元素之前。
    Less(i, j int) bool
    // Swap swaps the elements with indexes i and j.
    // Swap 交换索引为 i 和 j 的元素
    Swap(i, j int)
}

任何实现了 sort.Interface 的类型(一般为集合),均可使用该包中的方法进行排序。 这些方法要求集合内列出元素的索引为整数。

func Reverse

func Reverse(data Interface) Interface

Reverse returns the reverse order for data.

示例

代码:

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]

type StringSlice

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)