go中的三种排序方法-ag真人游戏

排序操作是很多程序经常使用的操作。尽管一个简短的快排程序只要二三十行代码就可以搞定，但是一个健壮的实现需要更多的代码，并且我们不希望每次我们需要的时候都重写或者拷贝这些代码。幸运的是，go内置的sort包中提供了根据一些排序函数来对任何序列进行排序的功能。

排序整数、浮点数和字符串切片

对于[]int, []float, []string这种元素类型是基础类型的切片使用sort包提供的下面几个函数进行排序。

• sort.ints
• sort.floats
• sort.strings

s := []int{4, 2, 3, 1}
sort.ints(s)
fmt.println(s) // 输出[1 2 3 4]

使用自定义比较器排序

• 使用sort.slice函数排序，它使用一个用户提供的函数来对序列进行排序，函数类型为func(i, j int) bool，其中参数i, j是序列中的索引。
• sort.slicestable在排序切片时会保留相等元素的原始顺序。
• 上面两个函数让我们可以排序结构体切片(order by struct field value)。

family := []struct {
    name string
    age  int
}{
    {"alice", 23},
    {"david", 2},
    {"eve", 2},
    {"bob", 25},
}
// 用 age 排序，年龄相等的元素保持原始顺序
sort.slicestable(family, func(i, j int) bool {
    return family[i].age < family[j].age
})
fmt.println(family) // [{david 2} {eve 2} {alice 23} {bob 25}]

排序任意数据结构

• 使用sort.sort或者sort.stable函数。
• 他们可以排序实现了sort.interface接口的任意类型

一个内置的排序算法需要知道三个东西：序列的长度，表示两个元素比较的结果，一种交换两个元素的方式；这就是sort.interface的三个方法：

type interface interface {
    len() int
    less(i, j int) bool // i, j 是元素的索引
    swap(i, j int)
}

还是以上面的结构体切片为例子，我们为切片类型自定义一个类型名，然后在自定义的类型上实现 srot.interface 接口

type person struct {
    name string
    age  int
}
// byage 通过对age排序实现了sort.interface接口
type byage []person
func (a byage) len() int           { return len(a) }
func (a byage) less(i, j int) bool { return a[i].age < a[j].age }
func (a byage) swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func main() {
    family := []person{
        {"david", 2},
        {"alice", 23},
        {"eve", 2},
        {"bob", 25},
    }
    sort.sort(byage(family))
    fmt.println(family) // [{david, 2} {eve 2} {alice 23} {bob 25}]
}

实现了sort.interface的具体类型不一定是切片类型；下面的customsort是一个结构体类型。

type customsort struct {
    p    []*person
    less func(x, y *person) bool
}
func (x customsort) len() int {len(x.p)}
func (x customsort) less(i, j int) bool { return x.less(x.p[i], x.p[j]) }
func (x customsort) swap(i, j int)      { x.p[i], x.p[j] = x.p[j], x.p[i] }

让我们定义一个根据多字段排序的函数，它主要的排序键是age，age 相同了再按 name 进行倒序排序。下面是该排序的调用，其中这个排序使用了匿名排序函数：

sort.sort(customsort{persons, func(x, y *person) bool {
    if x.age != y.age {
        return x.age < y.age
    }
    if x.name != y.name {
        return x.name > y.name
    }
    return false
}})

排序具体的算法和复杂度

go 的sort包中所有的排序算法在最坏的情况下会做 n log n次 比较，n 是被排序序列的长度，所以排序的时间复杂度是 o(n log n*)。其大多数的函数都是用改良后的快速排序算法实现的。