Go的标准包sort排序

因此对数据集合排序时不必考虑应当选择哪一种排序方法，只要实现了sort.Interface定义的三个方法：获取数据集合长度的(Len)方法、比较两个元素大小的(Less)方法和交换两个元素位置的(Swap)方法，就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。

标准库提供一个通用接口，只要实现了这个接口，就可以通过调用 sort.Sort 来排序。

  1. type Interface interface {
  2.     // Len is the number of elements in the collection. 获取数据集合元素个数
  3.     Len() int
  4.     // Less returns whether the element with index i should sort 
  5.     // before the element with index j. 如果index为i的元素小于index为j的元素，则返回true，否则返回false
  6.     Less(i, j int) bool
  7.     // Swap swaps the elements with indexes i and j. 交换i和j索引的两个元素的位置
  8.     Swap(i, j int)
  9. }

接下来我们看一个测试:

  1. import (
  2.     "fmt"
  3.     "sort"
  4. )
  6. func main() {
  8.     // int 类型的排序
  9.     a := []int{60, 5, 50, 32, 100}
  10.     fmt.Println(a)     // [60 5 50 32 100]
  11.     sort.Ints(a)       // sort.Sort(IntSlice(a)) 的封装
  12.     fmt.Println(a)     // [5 32 50 60 100]，默认的 Less() 实现的是升序
  13.     sort.Sort(sort.Reverse(sort.IntSlice(a)))
  14.     fmt.Println(a)     // [100 60 50 32 5] 实现降序排列
  16.     //float类型的排序
  17.     b := []float64{60.23,5.23,50.99,76.32,100.39,20.21}
  18.     fmt.Println(b)    // [60.23 5.23 50.99 76.32 100.39 20.21]
  19.     sort.Float64s(b)  // sort.Float64Slice(b)
  20.     fmt.Println(b)    // [5.23 20.21 50.99 60.23 76.32 100.39]
  21.     sort.Sort(sort.Reverse(sort.Float64Slice(b)))
  22.     fmt.Println(a)    // [100.39 76.32 60.23 50.99 20.21 5.23] 实现降序排列
  23. }

这里需要注意的是，默认的sort.Less实现的是升序排列，如果想要让结果降序，可以先用sort.Reverse包装一次。这个调用会得到一个reverse的类型，包含一个 Interface 的匿名字段，其中Less函数与Interface里的相反，从而实现逆序。

如果我们要对自定义的数据类型进行排序，需要实现 sort.Interface 接口，也就是实现 Len、Less 和 Swap 三个函数。很多场景下 Len 和 Swap 基本上和数据类型无关，所以实际上只有 Less 会有差别。

例如在app市场中app下载排行榜，知道appId和对应的下载量，需要把数据根据下载量进行排序。

  1. import (
  2.     "fmt"
  3.     "math/rand"
  4.     "sort"
  5. )
  7. type DownloadItem struct {
  8.     AppId            int // appID
  9.     DownloadTimes     int // 下载次数
  10. }
  12. func (d DownloadItem) String() string{
  13.     return fmt.Sprintf("AppId:%d,DownloadTimes:%d",d.AppId,d.DownloadTimes)
  14. }
  16. type DownloadCollection []*DownloadItem
  18. func (d DownloadCollection)Len() int{
  19.     return len(d)
  20. }
  22. func (d DownloadCollection)Swap(i int,j int){
  23.     d[i],d[j] = d[j],d[i]
  24. }
  26. // 根据app下载量降序排列
  27. func (d DownloadCollection)Less(i int,j int) bool{
  28.     return d[i].DownloadTimes >d[j].DownloadTimes
  29. }
  31. func main() {
  32.     a := make(DownloadCollection,5)
  33.     for i := 0; i < len(a); i++ {
  34.         a[i] = &DownloadItem{i + 1, rand.Intn(1000)}
  35.     }
  37.     fmt.Println(a)
  38.     sort.Sort(a)
  39.     fmt.Println(a)
  40. }

可以看到为排序的数据是:

  1. [AppId:1,DownloadTimes:81 AppId:2,DownloadTimes:887 AppId:3,DownloadTimes:847 AppId:4,DownloadTimes:59 AppId:5,DownloadTimes:81]

排序后的顺序是：

  1. [AppId:2,DownloadTimes:887 AppId:3,DownloadTimes:847 AppId:1,DownloadTimes:81 AppId:5,DownloadTimes:81 AppId:4,DownloadTimes:59]

在了解了Go的sort包排序之后我们继续探索下当今最流行的十大排序算法，然后做个梳理和总结方便我们以后可以学习和回顾．