sort.Interface 接口

這個(gè)接口是 sort 包的核心，它有3個(gè)方法。這是 Golang 很酷的一個(gè)特性，只要數(shù)據(jù)類型滿足 sort.Interface 接口，就可以用sort包的函數(shù)進(jìn)行排序。

// 一個(gè)滿足sort.Interface接口的（集合）類型可以被本包的函數(shù)進(jìn)行排序。
// 方法要求集合中的元素可以被整數(shù)索引。
type Interface interface {
    // Len方法返回集合中的元素個(gè)數(shù)
    Len() int
    // Less方法報(bào)告索引i的元素是否比索引j的元素小
    Less(i, j int) bool
    // Swap方法交換索引i和j的兩個(gè)元素
    Swap(i, j int)
}

Example1

package main

import (
    "fmt"
    "sort"
)

//自定義一個(gè)類型
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)) //進(jìn)行排序
    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 包內(nèi)置的排序方法

So easy ! 看了2個(gè)例子你應(yīng)該明白了吧！

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接口，以便排序?yàn)檫f增序列。

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

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

搜索

搜索和排序是2兄弟，搜索是從已經(jīng)排序的數(shù)據(jù)中返回?cái)?shù)據(jù)的位置。

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() // 等價(jià)于調(diào)用 sort.Sort，搜索前需要先排序。
    fmt.Println(data)

    x := 5
    i := data.Search(x) // 等價(jià)于調(diào)用 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，則找不到索引時(shí)返回的是n，而不是列表應(yīng)該插入的位置，會(huì)破壞列表順序。
        //在升序列表中使用 p[i].Age >= x，則找不到索引時(shí)返回接近x的位置，以保證列表的遞增順序
        //在降序列表中使用 p[i].Age <= x，則找不到索引時(shí)返回接近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