参考 排序算法

sort

对常用切片类型的排序

sort 包提供了对 []int 切片、[]float64 切片和 []string 切片完整支持，主要包括：

  • 对基本数据类型切片的排序支持 ```go // Ints sorts a slice of ints in increasing order. func Ints(x []int) { Sort(IntSlice(x)) }

// Float64s sorts a slice of float64s in increasing order. // Not-a-number (NaN) values are ordered before other values. func Float64s(x []float64) { Sort(Float64Slice(x)) }

// Strings sorts a slice of strings in increasing order. func Strings(x []string) { Sort(StringSlice(x)) }

  2. - 判断基本数据类型切片是否已经排好序
  3. ```go
  4. // IntsAreSorted reports whether the slice x is sorted in increasing order.
  5. func IntsAreSorted(x []int) bool { return IsSorted(IntSlice(x)) }
  7. // Float64sAreSorted reports whether the slice x is sorted in increasing order,
  8. // with not-a-number (NaN) values before any other values.
  9. func Float64sAreSorted(x []float64) bool { return IsSorted(Float64Slice(x)) }
  11. // StringsAreSorted reports whether the slice x is sorted in increasing order.
  12. func StringsAreSorted(x []string) bool { return IsSorted(StringSlice(x)) }

  • 对排好序的数据集合逆序，不必修改 Less() 方法的代码

    1. sort.Sort(sort.Reverse(data))

    对自定义数据类型的排序

    需要实现 sort.Interface 接口的三个方法，比较复杂的是 Less(i, j int) 方法，简言之就是位于索引 i 的元素是否应该排序在位于索引 j 的元素之前。

    1. // An implementation of Interface can be sorted by the routines in this package.
    2. // The methods refer to elements of the underlying collection by integer index.
    3. type Interface interface {
    4.   // Len is the number of elements in the collection.
    5.   Len() int
    7.   // Less reports whether the element with index i
    8.   // must sort before the element with index j.
    9.   //
    10.   // If both Less(i, j) and Less(j, i) are false,
    11.   // then the elements at index i and j are considered equal.
    12.   // Sort may place equal elements in any order in the final result,
    13.   // while Stable preserves the original input order of equal elements.
    14.   //
    15.   // Less must describe a transitive ordering:
    16.   //  - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well.
    17.   //  - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well.
    18.   //
    19.   // Note that floating-point comparison (the < operator on float32 or float64 values)
    20.   // is not a transitive ordering when not-a-number (NaN) values are involved.
    21.   // See Float64Slice.Less for a correct implementation for floating-point values.
    22.   Less(i, j int) bool
    24.   // Swap swaps the elements with indexes i and j.
    25.   Swap(i, j int)
    26. }

    实现上述接口后，可以直接调用函数进行排序

    1. sort.Sort(data)

试想，对于自定义结构体数组，我们如果想进行排序，还需要额外封装一层结构体，十分繁琐。sort 包提供了相关方法，我们提供比较函数即可

  1. func Slice(slice interface{}, less func(i, j int) bool) 
  2. func SliceStable(slice interface{}, less func(i, j int) bool) 
  3. func SliceIsSorted(slice interface{}, less func(i, j int) bool) bool

举个例子，完成一个自定义结构体 slice 的排序

  1. people := []struct {
  2.     Name string
  3.     Age  int
  4. }{
  5.     {"Gopher", 7},
  6.     {"Alice", 55},
  7.     {"Vera", 24},
  8.     {"Bob", 75},
  9. }
  11. sort.Slice(people, func(i, j int) bool { return people[i].Age < people[j].Age }) // 按年龄升序排序
  12. fmt.Println("Sort by age:", people)

search

sort 包还提供了对基本数据元素查找 的功能，注意输入必须是已经排序过的；输出是被查找元素 x 的位置（如果 x 存在），或者 x 应该被插入的位置（如果 x 不存在）

  1. // SearchInts searches for x in a sorted slice of ints and returns the index
  2. // as specified by Search. The return value is the index to insert x if x is
  3. // not present (it could be len(a)).
  4. // The slice must be sorted in ascending order.
  5. //
  6. func SearchInts(a []int, x int) int {
  7.     return Search(len(a), func(i int) bool { return a[i] >= x })
  8. }
  10. func SearchFloat64s(a []float64, x float64) int
  12. func SearchStrings(a []string, x string) int

同样，对于自定义结构体的列表查询，也需要实现一个 func(int) bool 函数，此函数的实现应该使得对于被查找的元素 x 之前所有值的返回值为 false

举个例子

  1. a := []int{2, 3, 4, 200, 100, 21, 234, 56}
  2. x := 21
  4. sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })   // 升序排序
  5. index := sort.Search(len(a), func(i int) bool { return a[i] >= x }) // 查找元素
  7. if index < len(a) && a[index] == x {
  8.     fmt.Printf("found %d at index %d in %v\n", x, index, a)
  9. } else {
  10.     fmt.Printf("%d not found in %v,index:%d\n", x, a, index)
  11. }