一个很好的例子是来自标准库的 sort
包,要对一组数字或字符串排序,只需要实现三个方法:反映元素个数的 Len()
方法、比较第 i
和 j
个元素的 Less(i, j)
方法以及交换第 i
和 j
个元素的 Swap(i, j)
方法。
排序函数的算法只会使用到这三个方法(可以使用任何排序算法来实现,此处我们使用冒泡排序):
1 2 3 4 5 6 7 8 9
| 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
,它声明了这些方法:
1 2 3 4 5
| type Sorter interface { Len() int Less(i, j int) bool Swap(i, j int) }
|
参数中的 int
是待排序序列长度的类型,而不是说要排序的对象一定要是一组 int
。i
和 j
表示元素的整型索引,长度也是整型的。
现在如果我们想对一个 int
数组进行排序,所有必须做的事情就是:为数组定一个类型并在它上面实现 Sorter
接口的方法:
1 2 3 4
| 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] }
|
下面是调用排序函数的一个具体例子:
1 2 3
| data := []int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586} a := sort.IntArray(data) sort.Sort(a)
|
完整的、可运行的代码可以在 sort.go 和 sortmain.go 里找到。
同样的原理,排序函数可以用于一个浮点型数组,一个字符串数组,或者一个表示每周各天的结构体 dayArray
。
示例 11.6 sort.go:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
| 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 }
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] }
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| 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) 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
备注:
panic("fail")
用于停止处于在非正常情况下的程序(详细请参考第 13 章),当然也可以先打印一条信息,然后调用 os.Exit(1)
来停止程序。
上面的例子帮助我们进一步了解了接口的意义和使用方式。对于基本类型的排序,标准库已经提供了相关的排序函数,所以不需要我们再重复造轮子了。对于一般性的排序,sort
包定义了一个接口:
1 2 3 4 5
| type Interface interface { Len() int Less(i, j int) bool Swap(i, j int) }
|
这个接口总结了需要用于排序的抽象方法,函数 Sort(data Interface)
用来对此类对象进行排序,可以用它们来实现对其他类型的数据(非基本类型)进行排序。在上面的例子中,我们也是这么做的,不仅可以对 int
和 string
序列进行排序,也可以对用户自定义类型 dayArray
进行排序。
练习 11.5 interfaces_ext.go:
a). 继续扩展程序,定义类型 Triangle
,让它实现 AreaInterface
接口。通过计算一个特定三角形的面积来进行测试(三角形面积=0.5 * (底 * 高))
b). 定义一个新接口 PeriInterface
,它有一个 Perimeter
方法。让 Square
实现这个接口,并通过一个 Square
示例来测试它。
练习 11.6 point_interfaces.go:
继续 10.3 中的练习 point_methods.go,定义接口 Magnitude
,它有一个方法 Abs()
。让 Point
、Point3
及 Polar
实现此接口。通过接口类型变量使用方法做 point.go 中同样的事情。
练习 11.7 float_sort.go / float_sortmain.go:
类似 11.7 和示例 11.3/4,定义一个包 float64
,并在包里定义类型 Float64Array
,然后让它实现 Sorter
接口用来对 float64
数组进行排序。
另外提供如下方法:
NewFloat64Array()
:创建一个包含 25 个元素的数组变量(参考 10.2 )List()
:返回数组格式化后的字符串,并在 String()
方法中调用它,这样就不用显式地调用 List()
来打印数组(参考 10.7)Fill()
:创建一个包含 10 个随机浮点数的数组(参考 4.5.2.6)
在主程序中新建一个此类型的变量,然后对它排序并进行测试。
练习 11.8 sort.go / sort_persons.go:
定义一个结构体 Person
,它有两个字段:firstName
和 lastName
,为 []Person
定义类型 Persons
。让 Persons
实现 Sorter
接口并进行测试。
链接