sort接口 · go

一个很好的例子是来自标准库的 sort 包，要对一组数字或字符串排序，只需要实现三个方法：反映元素个数的 Len() 方法、比较第 i 和 j 个元素的 Less(i, j) 方法以及交换第 i 和 j 个元素的 Swap(i, j) 方法。排序函数的算法只会使用到这三个方法（可以使用任何排序算法来实现，此处我们使用冒泡排序）： ~~~ func Sort(data Sorter) { for pass := 1; pass < data.Len(); pass++ { for i := 0;i < data.Len() - pass; i++ { if data.Less(i+1, i) { data.Swap(i, i + 1) } } } } ~~~ Sort 函数接收一个接口类型参数：Sorter ，它声明了这些方法： ~~~ type Sorter interface { Len() int Less(i, j int) bool Swap(i, j int) } ~~~ 参数中的 int 是待排序序列长度的类型，而不是说要排序的对象一定要是一组 int。i 和 j 表示元素的整型索引，长度也是整型的。现在如果我们想对一个 int 数组进行排序，所有必须做的事情就是：为数组定一个类型并在它上面实现 Sorter 接口的方法： ~~~ type IntArray []int func (p IntArray) Len() int { return len(p) } func (p IntArray) Less(i, j int) bool { return p[i] < p[j] } func (p IntArray) Swap(i, j int) { p[i], p[j] = p[j], p[i] } ~~~ 下面是调用排序函数的一个具体例子： ~~~ data := []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586} a := sort.IntArray(data) //conversion to type IntArray from package sort sort.Sort(a) ~~~ 同样的原理，排序函数可以用于一个浮点型数组，一个字符串数组，或者一个表示每周各天的结构体 dayArray. 示例 11.6 sort.go： ~~~ package sort type Sorter interface { Len() int Less(i, j int) bool Swap(i, j int) } func Sort(data Sorter) { for pass := 1; pass < data.Len(); pass++ { for i := 0; i < data.Len()-pass; i++ { if data.Less(i+1, i) { data.Swap(i, i+1) } } } } func IsSorted(data Sorter) bool { n := data.Len() for i := n - 1; i > 0; i-- { if data.Less(i, i-1) { return false } } return true } // Convenience types for common cases type IntArray []int func (p IntArray) Len() int { return len(p) } func (p IntArray) Less(i, j int) bool { return p[i] < p[j] } func (p IntArray) Swap(i, j int) { p[i], p[j] = p[j], p[i] } type StringArray []string func (p StringArray) Len() int { return len(p) } func (p StringArray) Less(i, j int) bool { return p[i] < p[j] } func (p StringArray) Swap(i, j int) { p[i], p[j] = p[j], p[i] } // Convenience wrappers for common cases func SortInts(a []int) { Sort(IntArray(a)) } func SortStrings(a []string) { Sort(StringArray(a)) } func IntsAreSorted(a []int) bool { return IsSorted(IntArray(a)) } func StringsAreSorted(a []string) bool { return IsSorted(StringArray(a)) } ~~~ 示例 11.7 sortmain.go： ~~~ package main import ( "./sort" "fmt" ) func ints() { data := []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586} a := sort.IntArray(data) //conversion to type IntArray sort.Sort(a) if !sort.IsSorted(a) { panic("fails") } fmt.Printf("The sorted array is: %v\n", a) } func strings() { data := []string{"monday", "friday", "tuesday", "wednesday", "sunday", "thursday", "", "saturday"} a := sort.StringArray(data) sort.Sort(a) if !sort.IsSorted(a) { panic("fail") } fmt.Printf("The sorted array is: %v\n", a) } type day struct { num int shortName string longName string } type dayArray struct { data []*day } func (p *dayArray) Len() int { return len(p.data) } func (p *dayArray) Less(i, j int) bool { return p.data[i].num < p.data[j].num } func (p *dayArray) Swap(i, j int) { p.data[i], p.data[j] = p.data[j], p.data[i] } func days() { Sunday := day{0, "SUN", "Sunday"} Monday := day{1, "MON", "Monday"} Tuesday := day{2, "TUE", "Tuesday"} Wednesday := day{3, "WED", "Wednesday"} Thursday := day{4, "THU", "Thursday"} Friday := day{5, "FRI", "Friday"} Saturday := day{6, "SAT", "Saturday"} data := []*day{&Tuesday, &Thursday, &Wednesday, &Sunday, &Monday, &Friday, &Saturday} a := dayArray{data} sort.Sort(&a) if !sort.IsSorted(&a) { panic("fail") } for _, d := range data { fmt.Printf("%s ", d.longName) } fmt.Printf("\n") } func main() { ints() strings() days() } ~~~ 输出： ~~~ The sorted array is: [-5467984 -784 0 0 42 59 74 238 905 959 7586 7586 9845] The sorted array is: [ friday monday saturday sunday thursday tuesday wednesday] Sunday Monday Tuesday Wednesday Thursday Friday Saturday ~~~ 备注：上面的例子帮助我们进一步了解了接口的意义和使用方式。对于基本类型的排序，标准库已经提供了相关的排序函数，所以不需要我们再重复造轮子了。对于一般性的排序，sort 包定义了一个接口： type Interface interface { Len() int Less(i, j int) bool Swap(i, j int) } 这个接口总结了需要用于排序的抽象方法，函数 Sort(data Interface) 用来对此类对象进行排序，可以用它们来实现对其他数据（非基本类型）进行排序。在上面的例子中，我们也是这么做的，不仅可以对 int 和 string 序列进行排序，也可以对用户自定义类型 dayArray 进行排序。