golang的排序功能

golang的排序功能

1. 首先明确两个基础概念

1. 排序基本上针对slice类型
2. 可排序的元数据类型有整数，浮点数，和字符串

2. 接着讨论元数据类型的排序

sort模块提供了函数给元数据类型排序。

func Ints(a []int)
func Float64s(a []float64)
func Strings(a []string)

然后到排序怎么处理呢

func Reverse(data Interface) Interface

这个函数的用法很奇怪，下面用例子说明：
数据类型sort.Interface的介绍后面再说，这里我们把它等同于slice即可：func Reverse(data []int) []int

package main

import (
    "fmt"
    "sort"
)

func main() {
    s1 := []int {5, 3, 4, 8, 2}
    s2 := sort.IntSlice(s1)
    s3 := sort.Reverse(s2)
    sort.Sort(s3)

    fmt.Printf("s1=%v\n", s1)
    fmt.Printf("s2=%v\n", s2)
    fmt.Printf("s3=%v\n", s3)
}

运行结果：

s1=[8 5 4 3 2]
s2=[8 5 4 3 2]
s3=&{[8 5 4 3 2]}

这个地方需要注意的是：

1. sort.IntSlice和Sort.Reverse，以及sort.Sort都没有分配新的slice空间，都只是使用的原始的s1的slice空间。
2. sort.Reverse并没有排序，只是定义了一个新的Interface wraper，只有用了sort.Sort之后才是真正的排序。
   我们看一段Reverse的代码就比较清晰：

// 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只是改写了原来的Less函数，把判断条件反转，这样在执行sort.Sort的时候才能实现反转。

3. 自定义数据类型的排序

前面都是系统自带的元数据类型的排序，语义也是很清楚的，数字按大小，字符串按字母顺序排序；那么如何给自定义的数据类型排序呢，例如自定义的struct类型。

3.1 先介绍排序的基本概念
一个collection容器的元素是可排序的，这个容器必须满足一定的条件：实现sort.Interface定义的接口函数：

type Interface interface {
    // Len is the number of elements in the collection.
    Len() int
    // Less reports 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)
}

• Len表示容器包含元素的个数。
• Less就是比较函数
• Swap交换两个元素

前面我们用到的元数据类型，Float64Slice/IntSlice/StringSlice，他们都是在[]float64, []int, []string的一层封装：

type Float64Slice []float64
type IntSlice []int
type StringSlice []string

因为[]int本身不具有Len(), Less(), Swap()的定义；而IntSlice定义了。

有了这个原来，我们就可以给任何数据类型进行排序了，例如：

package main

import (
    "fmt"
    "sort"
)

type MyData struct {
  Name string
  Age  int
}
type MyDataSlice []MyData

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

func main() {
    data := MyDataSlice {
        {"dd", 10},
        {"bb", 11},
        {"aa", 12},
        {"cc", 13},
    }

    sort.Sort(data)
    fmt.Printf("%v\n", data)
}

运行结果：

[{aa 12} {bb 11} {cc 13} {dd 10}]

还有一种简化的方式对应slice类型，只需要指定Less函数 func Slice(slice interface{}, less func(i, j int) bool)：

package main

import (
    "fmt"
    "sort"
)

type MyData struct {
  Name string
  Age  int
}

func main() {

    data := []MyData {
        {"dd", 10},
        {"bb", 11},
        {"aa", 12},
        {"cc", 13},
    }

    sort.Slice(data, func(i, j int) bool{
        return data[i].Name < data[j].Name
    })
    fmt.Printf("%v\n", data)
}

相比较前面一种方法：

1. 不需要定义数据类型MyDataSlice
2. 也不需要定义Len()和Swap()函数
3. 因为对应显示的[]slice类型数据，可以隐式的实现Len()和Swap函数功能。

我们可以看到sort.Slice的源代码，使用的隐式的[]slice的内置函数：

func Slice(slice interface{}, less func(i, j int) bool) {
    rv := reflect.ValueOf(slice)
    swap := reflect.Swapper(slice)
    length := rv.Len()
    ...
}