原创分享 一文搞懂 Go 语言中的切片排序

bigwhite-github · 2020年12月01日 · 82 次阅读

img{512x368}

本文首发于 “Gopher 部落” 知识星球

切片是 Go 语言中引入的用于在大多数场合替代数组的语法元素。切片是长度可变的同类型元素序列,它不支持存储不同类型的元素,当然如果你非用sl := [] interface{}{"hello", 11, 3.14}来抬杠^_^,那就另当别论。

有序列的地方就有排序的需求。在各种排序算法都已经成熟的今天,我们完全可以针对特定元素类型的切片手写排序函数/方法,但多数情况下不推荐这么做,因为 Go 标准库内置了sort包可以很好地帮助我们实现原生类型元素切片以及自定义类型元素切片的排序任务。

1. sort 包的排序原理

截至目前 (Go 1.15 版本),Go 还不支持泛型。因此,为了支持任意元素类型的切片的排序,标准库 sort 包定义了一个 Interface 接口和一个接受该接口类型参数的 Sort 函数:

// $GOROOT/src/sort/sort.go
type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}

func Sort(data Interface) {
        n := data.Len()
        quickSort(data, 0, n, maxDepth(n))
}

为了应用这个排序函数 Sort,我们需要让被排序的切片类型实现sort.Interface接口,以整型切片为例:

// slice-sort-in-go/sort_int_slice.go
type IntSlice []int

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

func main() {
    sl := IntSlice([]int{89, 14, 8, 9, 17, 56, 95, 3})
    fmt.Println(sl) // [89 14 8 9 17 56 95 3]
    sort.Sort(sl)
    fmt.Println(sl) // [3 8 9 14 17 56 89 95]
}

从 sort.Sort 函数的实现来看,它使用的是快速排序 (quickSort)。我们知道快速排序是在所有数量级为 (o(nlogn)) 的排序算法中其平均性能最好的算法,但在某些情况下其性能却并非最佳,Go sort 包中的 quickSort 函数也没有严格拘泥于仅使用快排算法,而是以快速排序为主,并根据目标状况在特殊条件下选择了其他不同的排序算法,包括堆排序 (heapSort)、插入排序 (insertionSort) 等。

sort.Sort 函数不保证排序是稳定的,要想使用稳定排序,需要使用sort.Stable函数。

注:稳定排序:假定在待排序的序列中存在多个具有相同值的元素,若经过排序,这些元素的相对次序保持不变,即在原序列中,若 r[i]=r[j] 且 r[i] 在 r[j] 之前,在排序后的序列中,若 r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的 (stable);否则称为不稳定的。

2. sort 包的 “语法糖” 排序函数

我们看到,直接使用 sort.Sort 函数对切片进行排序是比较繁琐的。如果仅仅排序一个原生的整型切片都这么繁琐 (要实现三个方法),那么 sort 包是会被 “诟病” 惨了的。还好,对于以常见原生类型为元素的切片,sort 包提供了类 “语法糖” 的简化函数,比如:sort.Ints、sort.Float64s 和 sort.Strings 等。上述整型切片的排序代码可以直接改造成下面这个样子:

// slice-sort-in-go/sort_int_slice_with_sugar.go

func main() {
    sl := []int{89, 14, 8, 9, 17, 56, 95, 3}
    fmt.Println(sl) // [89 14 8 9 17 56 95 3]
    sort.Ints(sl)
    fmt.Println(sl) // [3 8 9 14 17 56 89 95]
}

原生类型有 “语法糖” 可用了,那么对于自定义类型作为元素的切片,是不是每次都得实现 Interface 接口的三个方法呢?Go 团队也想到了这个问题! 所以在Go 1.8 版本中加入了sort.Slice函数,我们只需传入一个比较函数实现即可:

// slice-sort-in-go/custom-type-slice-sort-in-go.go

type Lang struct {
    Name string
    Rank int
}

func main() {
    langs := []Lang{
        {"rust", 2},
        {"go", 1},
        {"swift", 3},
    }
    sort.Slice(langs, func(i, j int) bool { return langs[i].Rank < langs[j].Rank })
    fmt.Printf("%v\n", langs) // [{go 1} {rust 2} {swift 3}]
}

同理,如果要进行稳定排序,则用 sort.SliceStable 替换上面的 sort.Slice。

3. 引入泛型后的切片排序

Russ Cox 已经确认了 Go 泛型 (type parameter) 将在 Go 1.18 版本落地,我们来展望一下在 2022 年 2 月 Go 泛型落地后,切片排序该怎么做。好在现在有https://go2goplay.golang.org/go 泛型技术草案中的语法。可以用于试验

在泛型加入后,我们可以按如下方式对原生类型切片进行排序:

// https://go2goplay.golang.org/p/lKG3saE-1ek

package main

import (
    "fmt"
    "sort"
)

type Ordered interface {
    type int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, float32, float64, string
}

type orderedSlice[T Ordered] []T

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

func OrderedSlice[T Ordered](s []T) {
    sort.Sort(orderedSlice[T](s))
}

func main() {
    s1 := []int32{3, 5, 2}
    fmt.Println(s1) // [3 5 2] 
    OrderedSlice(s1)
    fmt.Println(s1) // [2 3 5]

    s2 := []string{"jim", "amy", "tom"}
    fmt.Println(s2) // [jim amy tom]  
    OrderedSlice(s2)
    fmt.Println(s2) // [amy jim tom] 
}

上面的 Ordered 接口类型、orderedSlice[T] 切片类型以及 OrderdSlice 函数都可能会内置到 sort 包中,我们直接使用 sort.OrderSlice 函数即可对原生类型元素切片进行排序。

而对于自定义类型,如果我们将其加入到 Ordered 接口的类型列表 (type list) 中,像下面这样:

type Lang struct {
    Name string
    Rank int
}


type Ordered interface {
    type int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, float32, float64, string
}

那么,当我们像下面代码这样对元素类型为 Lang 的切片 langs 进行排序时,我们会遇到编译错误:

func main() {
    langs := []Lang{
        {"rust", 2},
        {"go", 1},
        {"swift", 3},
    }

    OrderedSlice(langs)
    fmt.Println(langs)
}

$prog.go2:20:55: cannot compare s[i] < s[j] (operator < not defined for T)

由于 Lang 类型不支持<和>比较,因此我们无法将 Lang 类型放入 Ordered 的类型列表中。而根本原因在于 Go 语言不支持运算符重载,这样我们永远无法让自定义类型支持<和>比较,我们只能另辟蹊径,采用 sort.Slice 的思路:额外提供一个比较函数!

// https://go2goplay.golang.org/p/7K94ZJuaoDc

package main

import (
    "fmt"
    "sort"
)

type Lang struct {
    Name string
    Rank int
}

type sliceFn[T any] struct {
    s   []T
    cmp func(T, T) bool
}

func (s sliceFn[T]) Len() int           { return len(s.s) }
func (s sliceFn[T]) Less(i, j int) bool { return s.cmp(s.s[i], s.s[j]) }
func (s sliceFn[T]) Swap(i, j int)      { s.s[i], s.s[j] = s.s[j], s.s[i] }

func SliceFn[T any](s []T, cmp func(T, T) bool) {
    sort.Sort(sliceFn[T]{s, cmp})
}

func main() {
    langs := []Lang{
        {"rust", 2},
        {"go", 1},
        {"swift", 3},
    }

    SliceFn(langs, func(p1, p2 Lang) bool { return p1.Rank < p2.Rank })
    fmt.Println(langs) // [{go 1} {rust 2} {swift 3}]
}

有人说,SliceFn 和非泛型版本的 sort.Slice 在使用时复杂度似乎也没啥差别啊。形式上的确如此,但内涵上还是有差别的

使用泛型方案, 由于少了到 interface{}的装箱和拆箱操作,理论上 SliceFn 的性能要好于 sort.Slice 函数。根据Go 语言之父 Robert Griesemer 对 Go 泛型的讲解

SliceFn(langs,...)

等价于下面过程:

sliceFnForLang := SliceFn(Lang) // 编译阶段,sliceFnForLang的函数原型为func(s []Lang, func(Lang, Lang) bool);
sliceFnForLang(langs) // 运行阶段,和普通函数调用无异,但没有了到interface{}类型装箱和拆箱的损耗。

注:本文涉及的源码可以在这里https://github.com/bigwhite/experiments/tree/master/slice-sort-in-go 下载到。

延伸阅读


我的 Go 技术专栏:“改善 Go 语⾔编程质量的 50 个有效实践” 上线了,欢迎大家订阅学习!

我的网课 “Kubernetes 实战:高可用集群搭建、配置、运维与应用” 在慕课网热卖中,感谢小伙伴们学习支持!

Gopher Daily(Gopher 每日新闻) 归档仓库 - https://github.com/bigwhite/gopherdaily

我的联系方式:

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio
暂无回复。
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册