go语言中的排序

Posted on Edited on In

背景

单看一些较旧的文档,go只能做一些简单的排序.
如今的go已经

  1. 区分稳定排序与不稳定排序
  2. 针对slice类型,优化代码行数
  3. 支持多键排序

介绍

go的sort包负责对数据的排序,主要功能

  1. 实现对内置类型的快捷排序
    1. sort.Ints()
    2. sort.Float64s()
  2. 实现对自定义类型的排序
  3. 实现多键排序
  4. 倒序排序

TODO 排序的算法
sort包支持3种算法

  1. 快速排序
  2. 插入排序
  3. 堆排序

简单举例

3个内置类型的slice有快捷方式

  1. int
  2. float64
  3. string
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
a := [3]int{3, 1, 2}
fmt.Println(sort.IntsAreSorted(a[:])) // false
fmt.Println(sort.SearchInts(a[:], 3)) // 3,不为升序找不到,找不到返回长度,而不是-1
sort.Ints(a[:])
fmt.Println(a)                        // [1 2 3]
fmt.Println(sort.IntsAreSorted(a[:])) // true
fmt.Println(sort.SearchInts(a[:], 3)) // 2,找到则返回下标

b := []float64{1.0, 3.5, -12.3}
sort.Float64s(b)          // [-12.3 1 3.5], 函数并无返回值,仅仅记录排序后的b
sort.Float64sAreSorted(b) // true
sort.SearchFloat64s(b, 1) // 1

c := []string{"b", "ca", "7", "11", "你好"}
sort.StringsAreSorted(c)   // false
sort.Strings(c)            // [11 7 b ca 你好]
sort.SearchStrings(c, "你") // 4

实现方式

核心在于 Sort 方法的参数要求实现3个函数

  1. Len
  2. Less
  3. Swap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
type IntSlice []int           // 内部将[]int称为IntSlice
func (x IntSlice) Sort() { Sort(x) } // 在IntSlice上定义有Sort方法,调用Sort函数

func Sort(data Interface) {   // Sort函数要求参数是Interface类型,满足Interface接口
  n := data.Len()
  quickSort(data, 0, n, maxDepth(n))
}

type Interface interface {    // Interface接口要求3个函数
  Len() int
  Less(i, j int) bool
  Swap(i, j int)
}

// 于是IntSlice上定义了3个函数
func (x IntSlice) Len() int           { return len(x) }
func (x IntSlice) Less(i, j int) bool { return x[i] < x[j] }
func (x IntSlice) Swap(i, j int)      { x[i], x[j] = x[j], x[i] }

故意找麻烦,使用起来如下

1
2
3
4
5
aa := sort.IntSlice([]int{5, 2, 2, 1})
aa.Len()      // 4
aa.Less(0, 1) // false 5 < 2 => false
aa.Swap(0, 1) // [2 5 2 1]
aa.Sort()     // [1 2 2 5]

自定义类型排序

实现Interface接口即可

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
type student struct {
  name  string
  score int
}
type myClass struct {
  className string
  students  []student
}

func (c myClass) Len() int           { return len(c.students) }
func (c myClass) Less(i, j int) bool { return c.students[i].score < c.students[j].score }
func (c myClass) Swap(i, j int)      { c.students[i], c.students[j] = c.students[j], c.students[i] }

func main() {
  cls := myClass{className: "一班", students: []student{
    student{"zhang", 3},
    student{"li", 4},
    student{"wang", 5},
    student{"zhao", 6},
    student{"qian", 3},
  }} // {一班 [{zhang 3} {li 4} {wang 5} {zhao 6} {qian 3}]}
  sort.IsSorted(cls) // false
  sort.Sort(cls)     // {一班 [{zhang 3} {qian 3} {li 4} {wang 5} {zhao 6}]}
  sort.Stable(cls)   // 稳定排序,{一班 [{zhang 3} {qian 3} {li 4} {wang 5} {zhao 6}]}

  // 在前1个内容中搜索满足score>3的条目,找不到,返回数字0
  sort.Search(1, func(i int) bool { return cls.students[i].score > 3 })
  // 在前5个内容中搜索满足score>3的条目,找到了,返回数字2,即{li 4}
  sort.Search(cls.Len(), func(i int) bool { return cls.students[i].score > 3 })
}

针对slice的排序

由于Len和Swap对于slice都很简单,
只需要提供一个闭包,表示Less函数即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func main() {
  sts := []student{
    student{"zhang", 3},
    student{"li", 4},
    student{"wang", 5},
    student{"zhao", 6},
    student{"qian", 3},
  } // [{zhang 3} {li 4} {wang 5} {zhao 6} {qian 3}]

  // slice的len与swap可以由go自身很方便地提供
  less := func(i, j int) bool { return sts[i].score < sts[j].score }
  sort.Slice(sts, less)         // [{zhang 3} {qian 3} {li 4} {wang 5} {zhao 6}]
  sort.SliceStable(sts, less)   // [{zhang 3} {qian 3} {li 4} {wang 5} {zhao 6}]
  sort.SliceIsSorted(sts, less) // true
  // 虽然没有sort.SliceSearch,但sort.Search对于所有非Interface类型也可以使用
  sort.Search(len(sts), func(i int) bool { return sts[i].score > 3 }) // 2, 即{li 4}
}

降序

1
2
3
4
5
// 用 sort.Reverse包裹符合Interface接口的数据即可
sort.Sort(sort.Reverse(cls)) // {一班 [{zhao 6} {wang 5} {li 4} {zhang 3} {qian 3}]}
// 或者直接让Less函数返回相反的结果
sort.Slice(sts, func(i, j int) bool { return sts[i].score > sts[j].score })
fmt.Println(sts) // [{zhao 6} {wang 5} {li 4} {zhang 3} {qian 3}]

查找

由于内部使用二分查找,因此要求

  1. 不能使用等于作为判断条件,必须使用不等式
  2. 查找升序序列,应当使用 >=
  3. 查找降序序列,应当使用 <=

包默认提供的 sort.SearchInts() 等方法默认序列是升序的.

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
func main() {
  a := []int{3, 4, 1, 2}
  /* 乱序下 */
  fmt.Println("乱序", a) // [3 4 1 2]
  // 快捷查找,错误
  fmt.Println(sort.SearchInts(a, 3)) // 4
  // 查找也会出错
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] == 4 })) // 4
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] >= 2 })) // 3
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] <= 3 })) // 2

  /* 升序下 */
  sort.Ints(a)
  fmt.Println("升序", a) // [1 2 3 4]
  // 查找时只有 >= 不会出错
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] == 2 })) // 4
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] <= 2 })) // 4
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] >= 0 })) // 0
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] >= 1 })) // 0
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] >= 2 })) // 1
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] >= 3 })) // 2
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] >= 4 })) // 3
  // 快捷查找,ok
  // 查看源码,也使用了 >=
  fmt.Println(sort.SearchInts(a, 3)) // 2

  /* 降序下 */
  sort.Sort(sort.Reverse(sort.IntSlice(a)))
  fmt.Println("降序", a) // [4 3 2 1]
  // 查找时只有 <= 不会出错
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] == 3 })) // 4
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] >= 3 })) // 4
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] <= 5 })) // 0
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] <= 4 })) // 0
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] <= 3 })) // 1
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] <= 2 })) // 2
  fmt.Println(sort.Search(len(a), func(i int) bool { return a[i] <= 1 })) // 3
  // 快捷查找出错
  fmt.Println(sort.SearchInts(a, 3)) // 4
}

按键排序

时常遇到,时刻1需要按a键排序,时刻2需要按b键排序.

朴素法

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
type person struct {
  name   string
  height int
  weight float64
}

func main() {
  ps := []person{
    person{"zhang", 3, 6.1},
    person{"li", 4, 5.1},
    person{"wang", 5, 4.1},
    person{"zhao", 6, 3.1},
  } // [{zhang 3 6} {li 4 5} {wang 5 4} {zhao 6 3}]

  ByName := func(i, j int) bool {
    return ps[i].name < ps[j].name
  }
  ByHeight := func(i, j int) bool {
    return ps[i].height < ps[j].height
  }
  ByWeight := func(i, j int) bool {
    return ps[i].weight < ps[j].weight
  }
  sort.Slice(ps, ByName)   // [{_li_ 4 5.1} {_wang_ 5 4.1} {_zhang_ 3 6.1} {_zhao_ 6 3.1}]
  sort.Slice(ps, ByHeight) // [{zhang _3_ 6.1} {li _4_ 5.1} {wang _5_ 4.1} {zhao _6_ 3.1}]
  sort.Slice(ps, ByWeight) // [{zhao 6 _3.1_} {wang 5 _4.1_} {li 4 _5.1_} {zhang 3 _6.1_}]
}

画蛇添足法

1
2
3
4
5
6
7
8
9
10
type By func(i, j int) bool

func main() {
  // ...

  name := func(i, j int) bool {
    return ps[i].name < ps[j].name
  }
  sort.Slice(ps, By(name)) // [{_li_ 4 5.1} {_wang_ 5 4.1} {_zhang_ 3 6.1} {_zhao_ 6 3.1}]
}

绕远路法

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
type By func(p1, p2 *person) bool

// 缺少 []person 信息,无法为By类型实现Interface接口
// func (by By) Len() int {}

// 从receiver中获取排序方式,从arg中获取被排序的群体
func (by By) Sort(persons []person) {
  // 虽然信息有了,但sort方法是作用在对象上的,因此不得不将两个信息合并到一个对象中去
  ps := &personSorter{
    persons: persons,
    by:      by,
  }
  // 当为该合成的类型实现了Len,Less,Swap方法后可以用sort了
  // 该合成的对象,事实上是不想暴露的,只想在By()之后链式使用Sort()方法
  // 因此暴露的是By对象上的Sort方法,而不是personSorter对象上的Sort()方法
  sort.Sort(ps)
}

type personSorter struct {
  persons []person
  by      By
}

func (s *personSorter) Len() int {
  return len(s.persons)
}
func (s *personSorter) Less(i, j int) bool {
  return s.by(&s.persons[i], &s.persons[j])
}
func (s *personSorter) Swap(i, j int) {
  s.persons[i], s.persons[j] = s.persons[j], s.persons[i]
}

func main() {
  // ...
  name := func(p1, p2 *person) bool { // 核心计算依然需要自己写,感觉费力不讨好,只适合练习
    return p1.name < p2.name
  }

  By(name).Sort(ps)
  fmt.Println(ps) // [{_li_ 4 5.1} {_wang_ 5 4.1} {_zhang_ 3 6.1} {_zhao_ 6 3.1}]
}

换汤不换药法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type persons []person

// 着眼于Len和Swap方法的公共性,在基类上实现该方法
func (s persons) Len() int      { return len(s) }
func (s persons) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

// 而不同的Less方法,通过包装不同的外层类,并在外层类上实现,来达到区分的目的
type ByName struct{ persons }
func (s ByName) Less(i, j int) bool { return s.persons[i].name < s.persons[j].name }// 但关键计算方法还是要写的

type ByWeight struct{ persons }
func (s ByWeight) Less(i, j int) bool { return s.persons[i].weight < s.persons[j].weight }

func main() {
  // ...
  sort.Sort(ByName{ps}) // [{li 4 5.1} {wang 5 4.1} {zhang 3 6.1} {zhao 6 3.1}]
  fmt.Println(ps)

  expand()
}

多键排序

时常有按照多个键来排序的需求

两次stable排序

缺点:

  1. 优先级更高的应该放在后面排序,有点不习惯
  2. 可能有性能浪费?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type person struct {
  name string
  age  int
}

func main() {
  ps := []person{
    person{"zhang", 10},
    person{"li", 10},
    person{"wang", 11},
    person{"zhao", 11},
  } // [{zhang 3 6} {li 4 5} {wang 5 4} {zhao 6 3}]

  ByAge := func(i, j int) bool { return ps[i].age < ps[j].age }
  ByName := func(i, j int) bool { return ps[i].name < ps[j].name }

  sort.Slice(ps, ByName)
  sort.Slice(ps, ByAge) // 优先级更高的应该放在后面排序

  fmt.Println(ps) // [{li 10} {zhang 10} {wang 11} {zhao 11}]
}

条件表达式

缺点

  1. 三个条件以上就回调地狱
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
func main() {
  ps := []person{
    person{"ai", 10},
    person{"li", 10},
    person{"ai", 11},
    person{"zhao", 11},
  }

  ageThenName := func(i, j int) bool {
    if ps[i].age != ps[j].age {
      return ps[i].age < ps[j].age
    } else {
      return ps[i].name < ps[j].name
    }
  }
  sort.Slice(ps, ageThenName)
  fmt.Println(ps) // [{ai 10} {li 10} {ai 11} {zhao 11}]

  nameThenAge := func(i, j int) bool {
    if ps[i].name != ps[j].name {
      return ps[i].name < ps[j].name
    } else {                                           // 如果相同,还不能返回
      return ps[i].age < ps[j].age // 还要继续比较
    }
  }

  sort.Slice(ps, nameThenAge)
  fmt.Println(ps) // [{ai 10} {ai 11} {li 10} {zhao 11}]
}

将条件表达式中多个元素for循环化

核心在于如果能回答,则立即回答,
如果相同,需要下一条规则

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
less := func(i, j int) bool {
  for k := 0; k < len(lesses)-1; k++ {
    rule := lesses[k]
    if rule(i, j) || rule(j, i) { // 若交换后也能分出大小,则真的能分出大小
      return rule(i, j)                       // 立即回答
    } // 否则表示分不出大小,需要用下一条规则
  }
  lastRule := lesses[len(lesses)-1]
  return lastRule(i, j) // 用最后的规则
}

// 上面的比较了三次
// 下面的虽有些脱裤子放屁,但仅仅比较两次
less := func(i, j int) bool {
  for k := 0; k < len(lesses)-1; k++ {
    rule := lesses[k]
    switch {
    case rule(i, j):
      return true // 若小则立即回答
    case rule(j, i):
      return false // 若大也立即回答
    } // 若相等则使用下一条规则
  }
  // 最后用最后的规则
  lastRule := lesses[len(lesses)-1]
  return lastRule(i, j)
}

比如选性价比旗舰

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
type phone struct {
  brand string
  // 各种指数满分5
  economicIndex   int // 经济性指数
  functionalIndex int // 功能指数
  fluencyIndex    int // 流畅指数
}

type lessFunc func(i, j int) bool

func main() {
  phones := []phone{
    {brand: "mi", economicIndex: 4, functionalIndex: 4, fluencyIndex: 2},
    {brand: "apple", economicIndex: 1, functionalIndex: 2, fluencyIndex: 4},
    {brand: "oneplus", economicIndex: 3, functionalIndex: 4, fluencyIndex: 5},
    {brand: "oppo", economicIndex: 2, functionalIndex: 5, fluencyIndex: 4},
    {brand: "huawei", economicIndex: 2, functionalIndex: 4, fluencyIndex: 4},
    {brand: "samsung", economicIndex: 1, functionalIndex: 4, fluencyIndex: 4},
  }

  byEconomy := func(i, j int) bool {
    return phones[i].economicIndex < phones[j].economicIndex
  }

  byFunction := func(i, j int) bool {
    return phones[i].functionalIndex < phones[j].functionalIndex
  }

  byFluency := func(i, j int) bool {
    return phones[i].fluencyIndex < phones[j].fluencyIndex
  }

  lesses := []lessFunc{ // 挑选性价比旗舰
    byFluency,  // 先看流畅
    byFunction, // 后看功能
    byEconomy,  // 最后看价格
  }

  less := func(i, j int) bool {
    for k := 0; k < len(lesses)-1; k++ {
      rule := lesses[k]
      switch {
      case rule(i, j):
        return true // 若小则立即回答
      case rule(j, i):
        return false // 若大也立即回答
      } // 若相等则使用下一条规则
    }
    // 最后用最后的规则
    lastRule := lesses[len(lesses)-1]
    return lastRule(i, j)
  }

  sort.Slice(phones, less)
  fmt.Println(phones)

  /* Output: 性价比旗舰升序
     {mi 4 4 _2_}               // 小米因太过卡顿无缘旗舰
     {apple 1 _2_ 4}          // apple因功能太差无缘旗舰
     {samsung _1_ 4 4}        // 三星因价格太高暂别性价比
     {huawei _2_ 4 4}         // 相同流畅度和功能,华为比三星便宜
     {oppo 2 _5_ 4}             // 相同流畅度,oppo比华为功能多
     {oneplus 3 4 _5_}]       // 一加最为流畅
  */
}

上面有一些缺点:

  1. 需要手动实现总less的封装
  2. 准备数据阶段做了实质上的倒序(比如价格指数,低者指数高),不够灵活
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
67
68
69
70
71
72
73
74
75
76
type phone struct {
  brand string
  // 各种指数满分5
  priceIndex      int // 价格指数
  functionalIndex int // 功能指数
  fluencyIndex    int // 流畅指数
}

type lessFunc func(i, j int) bool

// 2. 针对倒序,提供一个反转的封装函数
func desc(r lessFunc) lessFunc {
  return func(i, j int) bool {
    return r(j, i)
  }
}

type phones []phone

// 1. 针对手动实现,可以提供封装好的方法
func (s phones) SortBy(lesses ...lessFunc) {
  less := func(i, j int) bool {
    for k := 0; k < len(lesses)-1; k++ {
      rule := lesses[k]
      switch {
      case rule(i, j):
        return true // 若小则立即回答
      case rule(j, i):
        return false // 若大也立即回答
      } // 若相等则使用下一条规则
    }
    // 最后用最后的规则
    lastRule := lesses[len(lesses)-1]
    return lastRule(i, j)
  }
  sort.Slice(s, less)
}

func main() {
  phones := phones{
    {brand: "mi", priceIndex: 1, functionalIndex: 4, fluencyIndex: 2},
    {brand: "apple", priceIndex: 4, functionalIndex: 2, fluencyIndex: 4},
    {brand: "oneplus", priceIndex: 2, functionalIndex: 4, fluencyIndex: 5},
    {brand: "oppo", priceIndex: 3, functionalIndex: 5, fluencyIndex: 4},
    {brand: "huawei", priceIndex: 3, functionalIndex: 4, fluencyIndex: 4},
    {brand: "samsung", priceIndex: 4, functionalIndex: 4, fluencyIndex: 4},
  }

  byPrice := func(i, j int) bool {
    return phones[i].priceIndex < phones[j].priceIndex
  }

  byFunction := func(i, j int) bool {
    return phones[i].functionalIndex < phones[j].functionalIndex
  }

  byFluency := func(i, j int) bool {
    return phones[i].fluencyIndex < phones[j].fluencyIndex
  }

  phones.SortBy(
    byFluency,     // 先看流畅
    byFunction,    // 再看功能
    desc(byPrice), // 最后看价格更低的
  )
  fmt.Println(phones)

  /* Output: 性价比旗舰升序
    {mi 1 4 2}                  // 小米因太过卡顿无缘旗舰
    {apple 4 2 4}           // apple因功能太差无缘旗舰
    {samsung 4 4 4}           // 三星因价格太高暂别性价比
    {huawei 3 4 4}            // 相同流畅度和功能,华为比三星便宜
    {oppo 3 5 4}            // 相同流畅度,oppo比华为功能多
    {oneplus 2 4 5}]      // 一加最为流畅
  */
}

参考

  1. 知识参考
  2. 中文参考,不过已经旧了
  3. 官方参考