sort.Interface 接口

这个接口是 sort 包的核心，它有3个方法。这是 Golang 很酷的一个特性，只要数据类型满足 sort.Interface 接口，就可以用sort包的函数进行排序。

// 一个满足sort.Interface接口的（集合）类型可以被本包的函数进行排序。
// 方法要求集合中的元素可以被整数索引。
type Interface interface {
    // Len方法返回集合中的元素个数
    Len() int
    // Less方法报告索引i的元素是否比索引j的元素小
    Less(i, j int) bool
    // Swap方法交换索引i和j的两个元素
    Swap(i, j int)
}

Example1

package main

import (
    "fmt"
    "sort"
)

//自定义一个类型
type ints []int

func (s ints) Len() int           { return len(s) }
func (s ints) Less(i, j int) bool { return s[i] < s[j] }
func (s ints) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func main() {
    nums := []int{9, 8, 5, 4, 7, 6, 3, 0, 1, 2}

    sort.Sort(ints(nums)) //进行排序
    fmt.Println(nums)
}

Output: [0 1 2 3 4 5 6 7 8 9]

Example2

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

type Persons []Person

func (s Persons) Len() int           { return len(s) }
func (s Persons) Less(i, j int) bool { return s[i].Age < s[j].Age }
func (s Persons) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func main() {
    p := []Person{Person{"Lily", 20}, Person{"Bing", 18}, Person{"Tom", 23}, Person{"Vivy", 16}, Person{"John", 18}}

    sort.Sort(sort.Reverse(Persons(p))) //sort.Reverse 生成递减序列
    fmt.Println(p)
}

Output: [{Tom 23} {Lily 20} {Bing 18} {John 18} {Vivy 16}]

sort 包内置的排序方法

So easy ! 看了2个例子你应该明白了吧！

Example:

s := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(s)
fmt.Println(s)

Output: [1 2 3 4 5 6]

使用自定义排序算法

package main

import (
    "fmt"
    "sort"
)

//bubbleSort 冒泡排序
func bubbleSort(data sort.Interface) {
    r := data.Len() - 1
    for i := 0; i < r; i++ {
        for j := r; j > i; j-- {
            if data.Less(j, j-1) {
                data.Swap(j, j-1)
            }
        }
    }
}

//insertSort 插入排序
func insertSort(data sort.Interface) {
    r := data.Len() - 1
    for i := 1; i <= r; i++ {
        for j := i; j > 0 && data.Less(j, j-1); j-- {
            data.Swap(j, j-1)
        }
    }
}

//selectSort 选择排序
func selectSort(data sort.Interface) {
    r := data.Len() - 1
    for i := 0; i < r; i++ {
        min := i
        for j := i + 1; j <= r; j++ {
            if data.Less(j, min) {
                min = j
            }
        }
        data.Swap(i, min)
    }
}

func main() {
    nums := []int{9, 8, 5, 4, 7, 6, 3, 0, 1, 2}
    ints := sort.IntSlice(nums) //IntSlice给[]int添加方法以满足Interface接口，以便排序为递增序列。

    bubbleSort(ints) //使用冒泡排序
    fmt.Println(ints)
}

output: [0 1 2 3 4 5 6 7 8 9]

搜索

搜索和排序是2兄弟，搜索是从已经排序的数据中返回数据的位置。

Example1：[]int 搜索

package main

import (
    "fmt"
    "sort"
)

func main() {
    data := sort.IntSlice{9, 5, 3, 25, 1, 5, 64, 45, 21, 48, 55}
    data.Sort() // 等价于调用 sort.Sort，搜索前需要先排序。
    fmt.Println(data)

    x := 5
    i := data.Search(x) // 等价于调用 sort.SearchInts
    fmt.Printf("%v is present at data[%d]\n", x, i)
}

output:
[1 3 5 5 9 21 25 45 48 55 64]
5 is present at data[2]

Example2: []struct 搜索

package main

import (
    "fmt"
    "sort"
)

type Person struct {
    Name string
    Age  int
}

type Persons []Person

func (s Persons) Len() int           { return len(s) }
func (s Persons) Less(i, j int) bool { return s[i].Age < s[j].Age }
func (s Persons) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }

func main() {
    p := []Person{Person{"Lily", 20}, Person{"Bing", 18}, Person{"Tom", 23}, Person{"Vivy", 16}, Person{"John", 18}}
    sort.Sort(sort.Reverse(Persons(p))) //sort.Reverse 生成递减序列
    fmt.Println(p)

    x := 18
    i := sort.Search(len(p), func(i int) bool {
        //如果使用 p[i].Age == x，则找不到索引时返回的是n，而不是列表应该插入的位置，会破坏列表顺序。
        //在升序列表中使用 p[i].Age >= x，则找不到索引时返回接近x的位置，以保证列表的递增顺序
        //在降序列表中使用 p[i].Age <= x，则找不到索引时返回接近x的位置，以保证列表的递减顺序
        return p[i].Age <= x
    })
    fmt.Println(i)
}

output:
[{Tom 23} {Lily 20} {Bing 18} {John 18} {Vivy 16}]
2

参考：https://my.oschina.net/evilunix/blog/370676