[2012-05-21 翻译自这里, 对原文有所扩展, 也有所删减.]
在进入泛型的话题之前, 首先实现对int slice(可以看做int数组)的冒泡排序:
1 func BubbleSort(array []int) {
2 for i := 0; i < len(array); i++ {
3 for j := 0; j < len(array)-i-1; j++ {
4 if array[j] > array[j+1] {
5 // 交换
6 array[j], array[j+1] = array[j+1], array[j]
7 }
8 }
9 }
10 }
如你所见, 上面的代码仅适用于对int数组进行排序, 如果想要对string数组排序, 不得不另写一个.
是否可以只写一个通用的泛型程序, 以便对所有类型的数组(甚至是任意数据)进行冒泡排序?
很遗憾, go不支持java中的标记式泛型. 但是我们可以使用go的interface实现类似的功能.
interface用于定义方法的集合. 在冒泡排序中, 我们可以将排序操作分解成3个方法: Len()方法负责计算长度, Less(i, j)方法负责比较大小, Swap(i, j)方法负责进行交换.
1 // 定义可排序接口
2 type Sortable interface {
3 Len() int
4 Less(int, int) bool
5 Swap(int, int)
6 }
可以说, 任何实现了Sortable接口的数据类型都可进行冒泡排序, 下面是对Bubblesort方法的改造:
1 func BubbleSortable(arr Sortable) {
2 length := arr.Len()
3 for i := 0; i < length; i++ {
4 for j := i; j < length-i-1; j++ {
5 if arr.Less(j, j+1) {
6 arr.Swap(j, j+1)
7 }
8 }
9 }
10 }
BubbleSortable函数可以对所有Sortable类型的数据进行排序. 那么, 哪些数据是Sortable类型的呢? 很简单, 那些实现了Len(), Less(i, j), Swap(i, j)方法的数据类型都是Sortable的.
如果想要对int数组进行冒泡排序, 只需让int数组实现以上3个方法即可:
1 // 定义IntArr类型
2 type IntArr []int
3 // 给IntArr提供Len方法
4 func (arr IntArr) Len() int {
5 return len(arr)
6 }
7 // 给IntArr提供Less方法
8 func (arr IntArr) Less(i int, j int) bool {
9 return arr[i] < arr[j]
10 }
11 // 给IntArr提供Swap方法
12 func (arr IntArr) Swap(i int, j int) {
13 arr[i], arr[j] = arr[j], arr[i]
14 }
至此, 我们定义了新的类型: IntArr(实际上就是int数组), 并为IntArr增加了Len, Less, Swap方法.
注意, 在go中, 实现接口不需要像java那样显式的说明对某个接口的implements, 只需要为类型提供所有interface中定义的方法即可. 此例中, 我们给IntArr提供了所有Sortable中定义的方法, 所以IntArr已经实现了Sortable接口. 接下来要做的是将IntArr类型的数据传递给BubbleSortable函数就可以了:
1 intarr := IntArr{2, 3, 1, -9, 0}
2 // 调用排序方法
3 BubbleSortable(intarr)
4 // 输出排序之后的数据
5 fmt.Printf("sorted int arr is: %v\n", intarr)
同样的, 如果想对string数组进行冒泡排序, 也只需要让string数组实现Sortable接口中定义的所有方法:
1 type StrArr []string
2 func (arr StrArr) Len() int {
3 return len(arr)
4 }
5 func (arr StrArr) Less(i int, j int) bool {
6 return arr[i] < arr[j]
7 }
8 func (arr StrArr) Swap(i int, j int) {
9 arr[i], arr[j] = arr[j], arr[i]
10 }
测试代码如下:
1 strarr := StrArr{"nut", "ape", "elephant", "zoo", "go"}
2 Bubblesort(strarr)
3 fmt.Printf("sorted string arr is: %v\n", strarr)
现在, 你可以对任意数据进行冒泡排序了, 只需要该类型实现了Len, Less, Swap方法.
本文由本人原创或者翻译. 欢迎转载原创文章, 但转载必须保存本签名. 对于翻译文章, 所有版权属于原作者, 转载必须保存本签名. from: http://www.cnblogs.com/cool-xing
请发表评论