Golang之Sort包

落日映苍穹つ 2023-03-14 10:42 10阅读 0赞

Go语言是一门非常简单优雅的语言，其源码更是其风格标杆。看源码，不仅能学习Go的设计哲学，了解如何调用库函数，同时帮助我们写出更优雅的go代码。

Go源码位于GOROOT目录下的src中。

本文学习1.14.1版本源码库的sort包。该包对外提供的主要功能是排序和搜索。其核心的函数分别是：sort.Sort()与sort.Search()。

**1. sort.Sort()**

函数定义如下

func Sort(data Interface) {
      n := data.Len()
      quickSort(data, 0, n, maxDepth(n))
    }

Sort函数中调用了quickSort方法，该方法下是排序算法的具体实现，核心策略是根据待排序的数据量，相应调整不同的排序算法，这部分内容不在本文分析内容之中。

对包使用者来说，需要注意的是，Sort的入参是Interface接口，这Interface是什么呢？以下是其在sort.go中的定义。

type Interface interface {
      // Len is the number of elements in the collection.
      Len() int
      // Less reports whether the element with
      // index i should sort before the element with index j.
      Less(i, j int) bool
      // Swap swaps the elements with indexes i and j.
      Swap(i, j int)
    }

可见，Interface是一个接口类型（interface），其需要实现的函数方法分别是：Len、Less和Swap。这意味着什么呢？

我们知道，go中的接口实现是隐式实现，只要对象实现了接口定义的方法，即可实现该接口。因此，这种方式是一种非侵入式的实现。

那么，如果需要某对象能调用Sort方法，即实现其参数Interface接口即可。

在Sort包中，已经实现了部分对象类型对Sort函数的调用，包括：\[\]int,\[\]float64,\[\]string。以\[\]int类型为例，看其代码实现。

type IntSlice []int //使用IntSlice类型对[]int类型进行封装
    //IntSlice对象实现Interface接口
    func (p IntSlice) Len() int           { return len(p) }
    func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
    func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
    ...
    //由于Intslice对象实现了Interface接口，即可以作为参数调用Sort方法。
    func Ints(a []int) { Sort(IntSlice(a)) }

这就是sort包对外提供的Ints函数：当需要对\[\]int数组进行排序时，直接调用sort.Ints()。

package main
    
    import (
      "fmt"
      "sort"
    )
    
    func main() {
      a := []int{12,45,33,78,9,14}
      sort.Ints(a)
      fmt.Println(a) //[9 12 14 33 45 78]
    }

sort.Float64()和sort.Strings()同理。

**2. 自定义对象调用Sort()**

思考：假如需要排序的是自定义对象，应该如何实现。

给定对象person，其包括两个属性: name string,  age int。那么如何根据姓名或者age给person进行排序。完整示例如下。

package main
    
    import (
      "fmt"
      "sort"
    )
    
    type person struct {  //定义对象person
      name string
      age  int
    }
    
    type personSlice []person //给[]person绑定对象
    
    // 实现sort包定义的Interface接口
    func (s personSlice) Len() int { 
      return len(s)
    }
    
    func (s personSlice) Less(i, j int) bool {
      return s[i].age < s[j].age
    }
    
    func (s personSlice) Swap(i, j int) {
      s[i].age, s[j].age = s[j].age, s[i].age
    }
    
    func main() {
      p := personSlice{
        person{
          name: "mike",
          age:  13,
        }, person{
          name: "jane",
          age:  12,
        }, person{
          name: "peter",
          age:  14,
        }}
      sort.Sort(p)
      fmt.Println(p) // [{mike 12} {jane 13} {peter 14}]
    }

注意：并不是所有对象都能实现排序，前提是排序依赖的属性列是可比较的，如int，string等。

**3. sort.Search()**

函数原型

func Search(n int, f func(int) bool) int {}

Serarch里面的算法细节本文不讨论，只关注如何实现调用。Search函数中n参数是待搜索对象集的长度，注意此对象集必须是已排序过的；f参数是一个匿名函数，实现规则见下文\[\]int例子。

同样的，sort包已为几个特定对象实现了调用函数，包括\[\]int,\[\]float64,\[\]string。以\[\]int为例。

// 输入已排序[]int类型a，和某item值x，返回其在[]int中的索引值。
    // 注：小于[]int最小值返回0，大于最大值，返回len(a)
    func SearchInts(a []int, x int) int {
      return Search(len(a), func(i int) bool { return a[i] >= x })
    }
    ...
    // 返回IntSlice([]int)中的x所在索引值
    // 注：小于[]int最小值返回0，大于最大值，返回len(a)
    func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

使用示例：

package main
    
    import (
      "fmt"
      "sort"
    )
    
    func main() {
      a := []int{3,2,4,5,1}
      sort.Ints(a)
      fmt.Println(a)  // [1 2 3 4 5]
      fmt.Println(sort.SearchInts(a,5))  // 4
      fmt.Println(sort.SearchInts(a,6))  // 5
      fmt.Println(sort.IntSlice(a).Search(5)) // 4
    }

**4. 自定义对象调用Search**

同样是person对象，如果想根据age来查找排序后的person集合（personSlice）中下标，该如何实现。示例代码如下。

// 调用sort.Search函数，构造PersonSlice自己的Search方法
    func (s personSlice) Search(age int) int{
      return sort.Search(len(s), func(i int) bool {
        return s[i].age>=age
      })
    }

func main() {
      p := personSlice{
        person{
          name: "mike",
          age:  13,
        }, person{
          name: "jane",
          age:  12,
        }, person{
          name: "peter",
          age:  14,
        }}
      sort.Sort(p)
      fmt.Println(p)  // [{mike 12} {jane 13} {peter 14}]
      fmt.Println(p.Search(13)) // 1
    }

**5. 其他函数**

当然，在sort包中还有其他的一些函数暴露给用户使用，例如：sort.IsSorted()用于判断对象是否有序；sort.Stable()提供稳定排序，即当元素类型相等时，保留原有相对位置；sort.Reverse()提供对象集合元素反转等。有了sort.Sort()和sort.Search()的理解，这些函数都是相似的调用或实现。

本文内容同步在作者个人微信公众号：Golang技术分享。欢迎关注！

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NscGhhaGFoYQ_size_16_color_FFFFFF_t_70]: /images/20230312/c091579c4de24100a029f54bfa6060a5.png