《Go语言四十二章经》第二十九章 排序(sort)

作者：李骁

29.1 sort包介绍

Go语言标准库sort包中实现了３种基本的排序算法：插入排序、快排和堆排序。和其他语言中一样，这三种方式都是不公开的，他们只在sort包内部使用。所以用户在使用sort包进行排序时无需考虑使用那种排序方式，sort.Interface定义的三个方法：获取数据集合长度的Len()方法、比较两个元素大小的Less()方法和交换两个元素位置的Swap()方法，就可以顺利对数据集合进行排序。sort包会根据实际数据自动选择高效的排序算法。

  1. type Interface
  2. type Interface interface {
  4.     Len() int    // Len 为集合内元素的总数  
  5.     Less(i, j int) bool　//如果index为i的元素小于index为j的元素，则返回true，否则false
  6.     Swap(i, j int)  // Swap 交换索引为 i 和 j 的元素
  7. }

sort包里面已经实现了[]int, []float64, []string的排序。

任何实现了 sort.Interface 的类型（一般为集合），均可使用该包中的方法进行排序。这些方法要求集合内列出元素的索引为整数。

  1. package main
  3. import (
  4.     "fmt"
  5.     "sort"
  6. )
  8. func main() {
  9.     a := []int{3, 5, 4, -1, 9, 11, -14}
  10.     sort.Ints(a)
  11.     fmt.Println(a)
  12.     ss := []string{"surface", "ipad", "mac pro", "mac air", "think pad", "idea pad"}
  13.     sort.Strings(ss)
  14.     fmt.Println(ss)
  15.     sort.Sort(sort.Reverse(sort.StringSlice(ss)))
  16.     fmt.Printf("After reverse: %v\n", ss)
  17. }
  1. 程序输出：
  2. [-14 -1 3 4 5 9 11]
  3. [idea pad ipad mac air mac pro surface think pad]
  4. After reverse: [think pad surface mac pro mac air ipad idea pad]

默认结果都是升序排列，如果我们想对一个 sortable object 进行逆序排序，可以自定义一个type。但 sort.Reverse 帮你省掉了这些代码。

  1. package main
  3. import (
  4.     "fmt"
  5.     "sort"
  6. )
  8. func main() {
  9.     a := []int{4, 3, 2, 1, 5, 9, 8, 7, 6}
  10.     sort.Sort(sort.Reverse(sort.IntSlice(a)))
  11.     fmt.Println("After reversed: ", a)
  12. }
  1. 程序输出：
  2. After reversed:  [9 8 7 6 5 4 3 2 1]

相关方法：

  1. // 将类型为float64的slice以升序方式排序
  2. func Float64s(a []float64)   
  4. // 判定是否已经进行排序func Ints(a []int)
  5. func Float64sAreSorted(a []float64) bool　
  7. // Ints 以升序排列 int 切片。
  8. func Ints(a []int)                  
  10. // 判断 int 切片是否已经按升序排列。
  11. func IntsAreSorted(a []int) bool　
  13. //IsSorted 判断数据是否已经排序。包括各种可sort的数据类型的判断．
  14. func IsSorted(data Interface) bool    
  17. //Strings 以升序排列 string 切片。
  18. func Strings(a []string)
  20. //判断 string 切片是否按升序排列
  21. func StringsAreSorted(a []string) bool
  23. // search使用二分法进行查找，Search()方法回使用“二分查找”算法来搜索某指定切片[0:n]，
  24. // 并返回能够使f(i)=true的最小的i（0<=i<n）值，并且会假定，如果f(i)=true，则f(i+1)=true，
  25. // 即对于切片[0:n]，i之前的切片元素会使f()函数返回false，i及i之后的元素会使f()
  26. // 函数返回true。但是，当在切片中无法找到时f(i)=true的i时（此时切片元素都不能使f()
  27. // 函数返回true），Search()方法会返回n（而不是返回-1）。
  28. //
  29. // Search 常用于在一个已排序的，可索引的数据结构中寻找索引为 i 的值 x，例如数组或切片。
  30. // 这种情况下实参 f一般是一个闭包，会捕获所要搜索的值，以及索引并排序该数据结构的方式。
  31. func Search(n int, f func(int) bool) int   
  33. // SearchFloat64s 在float64s切片中搜索x并返回索引如Search函数所述. 
  34. // 返回可以插入x值的索引位置，如果x不存在，返回数组a的长度切片必须以升序排列
  35. func SearchFloat64s(a []float64, x float64) int　　
  37. // SearchInts 在ints切片中搜索x并返回索引如Search函数所述. 返回可以插入x值的
  38. // 索引位置，如果x不存在，返回数组a的长度切片必须以升序排列
  39. func SearchInts(a []int, x int) int 
  41. // SearchFloat64s 在strings切片中搜索x并返回索引如Search函数所述. 返回可以
  42. // 插入x值的索引位置，如果x不存在，返回数组a的长度切片必须以升序排列
  43. func SearchStrings(a []string, x string) int
  45. // 其中需要注意的是，以上三种search查找方法，其对应的slice必须按照升序进行排序，
  46. // 否则会出现奇怪的结果．
  48. // Sort 对 data 进行排序。它调用一次 data.Len 来决定排序的长度 n，调用 data.Less 
  49. // 和 data.Swap 的开销为O(n*log(n))。此排序为不稳定排序。他根据不同形式决定使用
  50. // 不同的排序方式（插入排序，堆排序，快排）。
  51. func Sort(data Interface)
  53. // Stable对data进行排序，不过排序过程中，如果data中存在相等的元素，则他们原来的
  54. // 顺序不会改变，即如果有两个相等元素num, 他们的初始index分别为i和j，并且i<j，
  55. // 则利用Stable对data进行排序后，i依然小于ｊ．直接利用sort进行排序则不能够保证这一点。
  56. func Stable(data Interface)

29.2 自定义sort.Interface排序

如果是具体的某个结构体的排序，就需要自己实现Interface了。

  1. package main
  3. import (
  4.     "fmt"
  5.     "sort"
  6. )
  8. type person struct {
  9.     Name string
  10.     Age  int
  11. }
  13. type personSlice []person
  15. func (s personSlice) Len() int           { return len(s) }
  16. func (s personSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
  17. func (s personSlice) Less(i, j int) bool { return s[i].Age < s[j].Age }
  19. func main() {
  20.     a := personSlice{
  21.         {
  22.             Name: "AAA", 
  23.             Age:  55, 
  24.         }, 
  25.         {
  26.             Name: "BBB", 
  27.             Age:  22, 
  28.         }, 
  29.         {
  30.             Name: "CCC", 
  31.             Age:  0, 
  32.         }, 
  33.         {
  34.             Name: "DDD", 
  35.             Age:  22, 
  36.         }, 
  37.         {
  38.             Name: "EEE", 
  39.             Age:  11, 
  40.         }, 
  41.     }
  42.     sort.Sort(a)
  43.     fmt.Println("Sort:", a)
  45.     sort.Stable(a)
  46.     fmt.Println("Stable:", a)
  48. }
  1. 程序输出：
  3. Sort: [{CCC 0} {EEE 11} {BBB 22} {DDD 22} {AAA 55}]
  4. Stable: [{CCC 0} {EEE 11} {BBB 22} {DDD 22} {AAA 55}]

29.3 sort.Slice

利用sort.Slice 函数，而不用提供一个特定的 sort.Interface 的实现，而是 Less(i，j int) 作为一个比较回调函数，可以简单地传递给 sort.Slice 进行排序。

  1. package main
  3. import (
  4.     "fmt"
  5.     "sort"
  6. )
  8. type Peak struct {
  9.     Name      string
  10.     Elevation int // in feet
  11. }
  13. func main() {
  14.     peaks := []Peak{
  15.         {"Aconcagua", 22838}, 
  16.         {"Denali", 20322}, 
  17.         {"Kilimanjaro", 19341}, 
  18.         {"Mount Elbrus", 18510}, 
  19.         {"Mount Everest", 29029}, 
  20.         {"Mount Kosciuszko", 7310}, 
  21.         {"Mount Vinson", 16050}, 
  22.         {"Puncak Jaya", 16024}, 
  23.     }
  25.     // does an in-place sort on the peaks slice, with tallest peak first
  26.     sort.Slice(peaks, func(i, j int) bool {
  27.         return peaks[i].Elevation >= peaks[j].Elevation
  28.     })
  29.     fmt.Println(peaks)
  31. }
  1. 程序输出：
  2. [{Mount Everest 29029} {Aconcagua 22838} {Denali 20322} {Kilimanjaro 19341} {Mount Elbrus 18510} {Mount Vinson 16050} {Puncak Jaya 16024} {Mount Kosciuszko 7310}]