golang：排序

水深无声 2022-02-25 04:08 255阅读 0赞

排序操作和字符串格式化一样是很多程序经常使用的操作。尽管一个最短的快排程序只要 15 行就可以搞定，但是一个健壮的实现需要更多的代码，并且我们不希望每次我们需要的时候都重写或者拷贝这些代码。

幸运的是，sort 包内置的提供了根据一些排序函数来对任何序列排序的功能。它的设计非常独到。在很多语言中，排序算法都是和序列数据类型关联，同时排序函数和具体类型元素关联。

相比之下，Go语言的 sort.Sort 函数不会对具体的序列和它的元素做任何假设。相反，它使用了一个接口类型 sort.Interface 来指定通用的排序算法和可能被排序到的序列类型之间的约定。这个接口的实现由序列的具体表示和它希望排序的元素决定，序列的表示经常是一个切片。

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

package sort
    type Interface interface {
        
        Len() int            // 获取元素数量
        Less(i, j int) bool // i，j是序列元素的指数。
        Swap(i, j int)        // 交换元素
    }

为了对序列进行排序，我们需要定义一个实现了这三个方法的类型，然后对这个类型的一个实例应用 sort.Sort 函数。思考对一个字符串切片进行排序，这可能是最简单的例子了。下面是这个新的类型 MyStringList 和它的 Len，Less 和 Swap 方法

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

# 使用sort.Interface接口进行排序 #

package main
    import (
        "fmt"
        "sort"
    )
    // 将[]string定义为MyStringList类型
    type MyStringList []string
    // 实现sort.Interface接口的获取元素数量方法
    func (m MyStringList) Len() int {
        
        return len(m)
    }
    // 实现sort.Interface接口的比较元素方法
    func (m MyStringList) Less(i, j int) bool {
        
        return m[i] < m[j]
    }
    // 实现sort.Interface接口的交换元素方法
    func (m MyStringList) Swap(i, j int) {
        
        m[i], m[j] = m[j], m[i]
    }
    func main() {
        
        // 准备一个内容被打乱顺序的字符串切片
        names := MyStringList{
        
            "3. Triple Kill",
            "5. Penta Kill",
            "2. Double Kill",
            "4. Quadra Kill",
            "1. First Blood",
        }
        // 使用sort包进行排序
        sort.Sort(names)
        // 遍历打印结果
        for _, v := range names {
        
                fmt.Printf("%s\n", v)
        }
    }

sort.Sort(names)将 names（MyStringList类型）进行排序。排序时，sort 包会通过 MyStringList 实现的 Len()、Less()、Swap() 这 3 个方法进行数据获取和修改。  
![在这里插入图片描述][b0033ecbd453495b9bea62139b997810.png]

# 常见类型的便捷排序 #

通过实现 sort.Interface 接口的排序过程具有很强的可定制性，可以根据被排序对象比较复杂的特性进行定制。例如，需要多种排序逻辑的需求就适合使用 sort.Interface 接口进行排序。但大部分情况中，只需要对字符串、整型等进行快速排序。Go语言中提供了一些固定模式的封装以方便开发者迅速对内容进行排序。

## 字符串切片的便捷排序 ##

sort 包中有一个 StringSlice 类型，定义如下：

type StringSlice []string
    func (p StringSlice) Len() int           {
         return len(p) }
    func (p StringSlice) Less(i, j int) bool {
         return p[i] < p[j] }
    func (p StringSlice) Swap(i, j int)      {
         p[i], p[j] = p[j], p[i] }
    // Sort is a convenience method.
    func (p StringSlice) Sort() {
         Sort(p)

sort 包中的 StringSlice 的代码与 MyStringList 的实现代码几乎一样。因此，只需要使用 sort 包的 StringSlice 就可以更简单快速地进行字符串排序。将代码1中的排序代码简化后如下所示：

package main
    import (
    	"fmt"
    	"sort"
    )
    
    func main() {
        
    	names := sort.StringSlice{
        
    		"3. Triple Kill",
    		"5. Penta Kill",
    		"2. Double Kill",
    		"4. Quadra Kill",
    		"1. First Blood",
    	}
    	// 使用sort包进行排序
    	sort.Sort(names)
    	// 遍历打印结果
    	for _, v := range names {
        
    		fmt.Printf("%s\n", v)
    	}
    }

## 对整型切片进行排序 ##

除了字符串可以使用 sort 包进行便捷排序外，还可以使用 sort.IntSlice 进行整型切片的排序。sort.IntSlice 的定义如下：

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] }
    // Sort is a convenience method.
    func (p IntSlice) Sort() {
         Sort(p) }

使用：

names := []string{
        
        "3. Triple Kill",
        "5. Penta Kill",
        "2. Double Kill",
        "4. Quadra Kill",
        "1. First Blood",
    }
    sort.Strings(names)
    // 遍历打印结果
    for _, v := range names {
        
        fmt.Printf("%s\n", v)
    }

## sort包内建的类型排序接口一览 ##

Go语言中的 sort 包中定义了一些常见类型的排序方法，如下表所示。  
![在这里插入图片描述][88a4f25653884e5cac3d6f851b454388.png]  
编程中经常用到的 int32、int64、float32、bool 类型并没有由 sort 包实现，使用时依然需要开发者自己编写。

# 对结构体数据进行排序 #

除了基本类型的排序，也可以对结构体进行排序。结构体比基本类型更为复杂，排序时不能像数值和字符串一样拥有一些固定的单一原则。结构体的多个字段在排序中可能会存在多种排序的规则，例如，结构体中的名字按字母升序排列，数值按从小到大的顺序排序。一般在多种规则同时存在时，需要确定规则的优先度，如先按名字排序，再按年龄排序等。

## 完整实现sort.Interface进行结构体排序 ##

package main
    import (
        "fmt"
        "sort"
    )
    // 声明英雄的分类
    type HeroKind int
    // 定义HeroKind常量, 类似于枚举
    const (
        None HeroKind = iota
        Tank
        Assassin
        Mage
    )
    // 定义英雄名单的结构
    type Hero struct {
        
        Name string  // 英雄的名字
        Kind HeroKind  // 英雄的种类
    }
    // 将英雄指针的切片定义为Heros类型
    type Heros []*Hero
    // 实现sort.Interface接口取元素数量方法
    func (s Heros) Len() int {
        
        return len(s)
    }
    // 实现sort.Interface接口比较元素方法
    func (s Heros) Less(i, j int) bool {
        
        // 如果英雄的分类不一致时, 优先对分类进行排序
        if s[i].Kind != s[j].Kind {
        
            return s[i].Kind < s[j].Kind
        }
        // 默认按英雄名字字符升序排列
        return s[i].Name < s[j].Name
    }
    // 实现sort.Interface接口交换元素方法
    func (s Heros) Swap(i, j int) {
        
        s[i], s[j] = s[j], s[i]
    }
    func main() {
        
        // 准备英雄列表
        heros := Heros{
        
            &Hero{
        "吕布", Tank},
            &Hero{
        "李白", Assassin},
            &Hero{
        "妲己", Mage},
            &Hero{
        "貂蝉", Assassin},
            &Hero{
        "关羽", Tank},
            &Hero{
        "诸葛亮", Mage},
        }
        // 使用sort包进行排序
        sort.Sort(heros)
        // 遍历英雄列表打印排序结果
        for _, v := range heros {
        
            fmt.Printf("%+v\n", v)
        }
    }

## 使用sort.Slice进行切片元素排序 ##

从 Go 1.8 开始，Go语言在 sort 包中提供了 sort.Slice() 函数进行更为简便的排序方法。sort.Slice() 函数只要求传入需要排序的数据，以及一个排序时对元素的回调函数，类型为 func(i,j int)bool，sort.Slice() 函数的定义如下：

func Slice(slice interface{
        }, less func(i, j int) bool)

使用：

package main
    import (
        "fmt"
        "sort"
    )
    type HeroKind int
    const (
        None = iota
        Tank
        Assassin
        Mage
    )
    type Hero struct {
        
        Name string
        Kind HeroKind
    }
    func main() {
        
        heros := []*Hero{
        
            {
        "吕布", Tank},
            {
        "李白", Assassin},
            {
        "妲己", Mage},
            {
        "貂蝉", Assassin},
            {
        "关羽", Tank},
            {
        "诸葛亮", Mage},
        }
        sort.Slice(heros, func(i, j int) bool {
        
            if heros[i].Kind != heros[j].Kind {
        
                return heros[i].Kind < heros[j].Kind
            }
            return heros[i].Name < heros[j].Name
        })
        for _, v := range heros {
        
            fmt.Printf("%+v\n", v)
        }
    }

[b0033ecbd453495b9bea62139b997810.png]: /images/20220225/4891f152c07e46f5b71ad90e04348c76.png
[88a4f25653884e5cac3d6f851b454388.png]: /images/20220225/13cd401a422843ed8b82985c9b871fb3.png