# 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)
        }
    }

## 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接口，对该接口排序可生成递减序列。

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

    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排序为递增顺序。

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

    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)。