Go语言中的排序包

简介

排序包提供了默认实现来对slice等进行排序，还提供了接口来定义自己的比较逻辑。根据Go语言中接口和继承的思想，这也很有趣，请看解释笔记。

排序函数

在sort包中定义了一个Sort函数。

这个签名如下。

func Sort(data Interface)

换句话说，当你传入满足 sort.Interface 接口的变量时，它会根据需要选择快速排序、堆排序或插入排序，并将它们进行适当的排序。

排序界面

在Go语言中，只要具备了方法，就可以满足sort.Interface的接口要求。

type Interface interface {
  // Len is the number of elements in the collection.
  Len() int
  // Less returns whether the element with index i should sort
  // before the element with index j.
  Less(i, j int) bool
  // Swap swaps the elements with indexes i and j.
  Swap(i, j int)
}

简单的排序

只要实现上述方法，就可以对自己创建的结构体进行排序。

package main

import (
    "log"
    "sort"
)

// 独自の構造体
type Person struct {
    Name string
    Age  uint8
}

// 構造体のスライス
type People []Person

// 以下インタフェースを満たす

func (p People) Len() int {
    return len(p)
}

func (p People) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}

func (p People) Less(i, j int) bool {
    return p[i].Name < p[j].Name
}

func main() {
    var people People = []Person{
        {"John", 22},
        {"Tom", 20},
        {"Emily", 18},
    }

    // sort.Sort に渡すだけ
    sort.Sort(people) // return はされない点には注意
    log.Println(people) // [{Emily 18} {Tom 22} {John 20}]
}

想要多个排序条件

创建一个可以按照姓名和年龄分别排序的功能。
为排序条件准备一个类型，并继承原始结构体。
交换和长度函数可继承，而较小函数则应在子结构体中实现即可。

package main

import (
    "log"
    "sort"
)

type Person struct {
    Name string
    Age  uint8
}

type People []Person

func (p People) Len() int {
    return len(p)
}

func (p People) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}

// Name でソートするための型
type ByName struct {
    People // 継承にあたるもの
    // ちなみに
    // people People
    // などとすると継承にはならない
}

func (b ByName) Less(i, j int) bool {
    return b.People[i].Name < b.People[j].Name
}

// Age でソートするための型
type ByAge struct {
    People
}

func (b ByAge) Less(i, j int) bool {
    return b.People[i].Age < b.People[j].Age
}

func main() {
    var people People = []Person{
        {"John", 22},
        {"Tom", 20},
        {"Emily", 18},
    }

    // 条件に継承させてからソート
    sort.Sort(ByName{people})
    log.Println(people) // [{Emily 18} {John 22} {Tom 20}]

    sort.Sort(ByAge{people})
    log.Println(people) // [{Emily 18} {Tom 20} {John 22}]
}

基本排序

为int，string和float64的切片提供了默认实现。
提供了满足sort.Interface的类型，并提供了包装函数以继承并进行排序。

package main

import (
    "log"
    "sort"
)

func main() {
    i := []int{5, 2, 6, 3, 1, 4}
    // sort.IntSlice に型変換している
    // sort.Interface が満たされる
    sort.Sort(sort.IntSlice(i))
    log.Println(i) // [1 2 3 4 5 6]

    s := []string{"cd", "bc", "ab", "aa"}
    // 継承と Sort を両方やってくれる
    sort.Strings(s)
    log.Println(s) // [aa ab bc cd]

    // 同様に sort.Float64s もある。
}

反转

只要实现了 sort.Interface 接口，就可以使用 Reverse()。

sort.Sort(people)
log.Println(people) // [{Emily 18} {John 20} {Tom 22}]

sort.Sort(sort.Reverse(people)) // reverse
log.Println(people) // [{Tom 22} {John 20} {Emily 18}]

为什么呢？因为 Reverse 的实现只是偷了 Less 而已。

package sort

type reverse struct {
    // This embedded Interface permits Reverse to use the methods of
    // another Interface implementation.
    Interface
}

// Less returns the opposite of the embedded implementation's Less method.
func (r reverse) Less(i, j int) bool {
    return r.Interface.Less(j, i)
}

// Reverse returns the reverse order for data.
func Reverse(data Interface) Interface {
    return &reverse{data}
}

在用户领域决定较少

以下是在 http://golang.org/pkg/sort/#example__sortKeys 中介绍的技巧。
从类型定义中将 Less() 分离出来可以很方便，就像这样。

由于无法动态定义 Less()，因此可以在内部创建另一个 Struct，并在其初始化时传递的 func 中使用该 Less() 技巧。

package main

import (
    "log"
    "sort"
)

type Person struct {
    Name string
    Age  uint8
}

type People []Person

// Less() の型
type By func(p1, p2 Person) bool

func (by By) Sort(people People) {
  // ここで struct にメンバとして渡す
    ps := PeopleSorter{
        people: people,
        by:     by,
    }
    sort.Sort(ps)
}

type PeopleSorter struct {
    people People
    by     By
}

func (p PeopleSorter) Len() int {
    return len(p.people)
}

func (p PeopleSorter) Swap(i, j int) {
    p.people[i], p.people[j] = p.people[j], p.people[i]
}

func (p PeopleSorter) Less(i, j int) bool {
  // ここで渡された Less が使う
    return p.by(p.people[i], p.people[j])
}

func main() {
    var people People = []Person{
        {"John", 22},
        {"Tom", 20},
        {"Emily", 18},
    }

  // Less() を別途定義
    name := func(p1, p2 Person) bool {
        return p1.Name < p2.Name
    }

    age := func(p1, p2 Person) bool {
        return p1.Age < p2.Age
    }

  // ここで渡す
    By(name).Sort(people)
    log.Println(people)

    By(age).Sort(people)
    log.Println(people)
}

按照姓名对人进行排序，开个玩笑哈哈。

我尝试了一下，不确定能否做得到。
因为在Sort()中只有People的信息，所以我认为在By()中还需要一个结构体。实现方法有些凌乱（可能可以更优雅）。

package main

import (
    "log"
    "sort"
)

type Person struct {
    Name string
    Age  uint8
}

type People []Person

func Sort(people People) PeopleSorter {
    return PeopleSorter{
        people,
    }
}

type PeopleSorter struct {
    people People
}

func (p PeopleSorter) By(by By) {
    s := Sorter{
        p,
        by,
    }
    s.sort()
}

type Sorter struct {
    PeopleSorter
    By
}

func (s Sorter) Len() int {
    return len(s.people)
}

func (s Sorter) Swap(i, j int) {
    s.people[i], s.people[j] = s.people[j], s.people[i]
}

func (s Sorter) Less(i, j int) bool {
    return s.By(s.people[i], s.people[j])
}

func (s Sorter) sort() {
    sort.Sort(s)
}

type By func(p1, p2 Person) bool

func main() {
    var people People = []Person{
        {"John", 22},
        {"Tom", 20},
        {"Emily", 18},
    }

    name := func(p1, p2 Person) bool {
        return p1.Name < p2.Name
    }

    age := func(p1, p2 Person) bool {
        return p1.Age < p2.Age
    }

    Sort(people).By(name)
    log.Println(people)

    Sort(people).By(age)
    log.Println(people)
}

临时搁置

无论好坏如何，我用 Sort(people, name) 试着写了一下。

package main

import (
    "log"
    "sort"
)

type Person struct {
    Name string
    Age  uint8
}

type People []Person

type By func(p1, p2 Person) bool

func Sort(people People, by By) {
    p := PeopleSorter{
        people,
        by,
    }
    sort.Sort(p)
}

type PeopleSorter struct {
    People
    By
}

func (s PeopleSorter) Len() int {
    return len(s.People)
}

func (s PeopleSorter) Swap(i, j int) {
    s.People[i], s.People[j] = s.People[j], s.People[i]
}

func (s PeopleSorter) Less(i, j int) bool {
    return s.By(s.People[i], s.People[j])
}

func main() {
    var people People = []Person{
        {"John", 22},
        {"Tom", 20},
        {"Emily", 18},
    }

    name := func(p1, p2 Person) bool {
        return p1.Name < p2.Name
    }

    age := func(p1, p2 Person) bool {
        return p1.Age < p2.Age
    }

    Sort(people, name)
    log.Println(people)

    Sort(people, age)
    log.Println(people)
}

因为我累了，所以搜索稍后再说。