go sort.Interface 排序接口

在很多语言中,排序算法都是和序列数据类型关联,同时排序函数和具体类型元素关联。而 Go 语言的 sort.Sort() 函数不会对具体的序列和它的元素做任何假设。相反,它使用了一个接口类型 sort.Interface 来指定通用的排序算法和可能被排序到的序列类型之间的约定。
这个接口的实现由序列的具体表示和它希望排序的元素决定,序列的表示经常是一个切片。
一个内置的排序算法需要知道三个东西:序列的长度,表示两个元素比较的结果,一种交换两个元素的
方式
;这就是 sort.Interface 的三个方法:

package sort

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
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)
}

为了对序列进行排序,我们需要定义一个实现了这三个方法的类型,然后对这个类型的一个实例应用
sort.Sort() 函数。
例子:对一个表格中的音乐播放列表进行排序

package main

import (
    "fmt"
    "os"
    "sort"
    "text/tabwriter"
    "time"
)

//定义音乐播放列表的结构体
type Track struct {
    Title  string
    Artist string
    Album  string
    Year   int
    Length time.Duration
}

//实例化几条测试数据
var tracks = []*Track{
    {"GO", "Delilah", "From the Roots Up", 2012, length("3m38s")},
    {"GO", "Moby", "Moby", 2012, length("13m38s")},
    {"GOaaaa", "Alicic keys", "As I am", 2012, length("31m38s")},
    {"GO", "Martin solveig", "Smash", 2012, length("34m38s")},
}

/**
获取时间长度
*/
func length(s string) time.Duration {
    d, err := time.ParseDuration(s)
    if err != nil {
        panic(err)
    }
    return d
}

/**
将播放列表打印成一个表格,
使用text/tabwriter包来生成一个列是整齐对齐和隔开的表格
*/
func printTracks(track []*Track) {
    const format = "%v\t%v\t%v\t%v\t%v\t\n"
    tw := new(tabwriter.Writer).Init(os.Stdout, 0, 8, 2, ' ', 0)
    fmt.Fprintf(tw, format, "Title", "Artist", "Album", "Year", "Length")
    for _, t := range track {
        fmt.Fprintf(tw, format, t.Title, t.Artist, t.Album, t.Year, t.Length)
    }

    tw.Flush()
}

/**
为了能按照Artist字段对播放列表进行排序,
我们要按照sort.Interface定义实现三个方法:
Len() int
Less(i,j int) bool
Swap(i,j)

*/
type byArtist []*Track

func (x byArtist) Len() int {
    return len(x)
}

//按照Artilst排序
func (x byArtist) Less(i, j int) bool {
    return x[i].Artist < x[j].Artist
}

func (x byArtist) Swap(i, j int) {
    x[i], x[j] = x[j], x[i]
}

//程序入口
func main() {
    sort.Sort(byArtist(tracks)) //将tracks转换为新的byArtist类型
    printTracks(tracks)
}

输出结果:
file

假设用户第二次请求 「按照 artist 排序」,我们会对 tracks 进行逆向排序。然而我们不需要定义一个有
颠倒 Less 方法的新类型 byReverseArtist ,因为sort包中提供了 Reverse 函数将排序顺序转换成逆序。

func main() {
    sort.Sort(sort.Reverse(byArtist(tracks)))//逆向排序
    printTracks(tracks)
}

逆向排序的结果:
file

sort 包定义了一个不公开的 struct 类型 reverse,它嵌入了一个 sort.Interface。reverse的Less方法调
用了内嵌的sort.Interface值的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}
}

reverse 的另外两个方法 Len 和 Swap 隐式地由原有内嵌的 sort.Interface 提供。因为reverse是一个不公开的类型,所以导出函数 Reverse 函数返回一个包含原有sort.Interface 值的 reverse 类型实例。

本作品采用《CC 协议》,转载必须注明作者和本文链接

不卑不亢,不慌不忙,这才是生活的模样。

讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!