Go基础入门：sort包

前言

切片是Go语言中引入的用于在大多数场合替代数组的语法元素。切片是长度可变的同类型元素序列，它不支持存储不同类型的元素。 有序列的地方就有排序的需求。在各种排序算法都已经成熟的今天，我们完全可以针对特定元素类型的切片手写排序函数/方法，但多数情况下不推荐这么做，因为Go标准库内置了sort包可以很好地帮助我们实现原生类型元素切片以及自定义类型元素切片的排序任务。

一、sort包简介

Go的sort包用来排序，二分查找等操作。

二、sort包内排序原理实现

type Interface interface {
  // Len是集合中元素的个数。
  Len() int
  // Less是排序条件（索引i与j的元素对比排序）
  Less(i, j int) bool
  // Swap交换索引i和j的元素。
  Swap(i, j int)
}

// Sort按Less方法确定的升序对数据进行排序。
func Sort(data Interface) {
  n := data.Len()
  if n <= 1 {
    return
  }
  limit := bits.Len(uint(n))
  pdqsort(data, 0, n, limit)
}

入口的 Sort 函数调用的 pdqsort 并不完全是快排。

pdqsort实质为一种混合排序算法，在不同情况下切换到不同的排序机制，该实现灵感来自C++和RUST的实现，是对C++标准库算法introsort的一种改进，其理想情况下的时间复杂度为 O(n)，最坏情况下的时间复杂度为 O(n* logn)，不需要额外的空间。

pdqsort算法的改进在于对常见的情况做了特殊优化，其主要的思想是不断判定目前的序列情况，然后使用不同的方式和路径达到最优解；其实现就是对下面三种情况的不断循环：

短序列情况：对于长度在 [0, MAX_INSERTION] 的输入，使用 insertion sort (插入排序)来进行排序后直接返回，这里的 MAX_INSERTION 我们选定为 12。
最坏情况，如果发现改进的 quicksort 效果不佳(limit == 0)，则后续排序都使用 heap sort 来保证最坏情况时间复杂度为 O(n*logn)。
正常情况，对于其他输入，使用改进的 quicksort 来排序

func pdqsort(data Interface, a, b, limit int) {
  const maxInsertion = 12

  var (
    wasBalanced    = true // whether the last partitioning was reasonably balanced
    wasPartitioned = true // whether the slice was already partitioned
  )

  for {
    length := b - a

    if length <= maxInsertion {
      insertionSort(data, a, b)
      return
    }

    // Fall back to heapsort if too many bad choices were made.
    if limit == 0 {
      heapSort(data, a, b)
      return
    }

    // If the last partitioning was imbalanced, we need to breaking patterns.
    if !wasBalanced {
      breakPatterns(data, a, b)
      limit--
    }

    pivot, hint := choosePivot(data, a, b)
    if hint == decreasingHint {
      reverseRange(data, a, b)
      // The chosen pivot was pivot-a elements after the start of the array.
      // After reversing it is pivot-a elements before the end of the array.
      // The idea came from Rust's implementation.
      pivot = (b - 1) - (pivot - a)
      hint = increasingHint
    }

    // The slice is likely already sorted.
    if wasBalanced && wasPartitioned && hint == increasingHint {
      if partialInsertionSort(data, a, b) {
        return
      }
    }

    // Probably the slice contains many duplicate elements, partition the slice into
    // elements equal to and elements greater than the pivot.
    if a > 0 && !data.Less(a-1, pivot) {
      mid := partitionEqual(data, a, b, pivot)
      a = mid
      continue
    }

    mid, alreadyPartitioned := partition(data, a, b, pivot)
    wasPartitioned = alreadyPartitioned

    leftLen, rightLen := mid-a, b-mid
    balanceThreshold := length / 8
    if leftLen < rightLen {
      wasBalanced = leftLen >= balanceThreshold
      pdqsort(data, a, mid, limit)
      a = mid + 1
    } else {
      wasBalanced = rightLen >= balanceThreshold
      pdqsort(data, mid+1, b, limit)
      b = mid
    }
  }
}

为了更方便理解应用排序函数Sort，我们需要让被排序的切片类型实现 sort.Interface接口，以整型切片排序为例：

// IntSlice将Interface的方法附加到[]int，按递减顺序排序。
type IntSlice []int

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] }

func main() {
  sl := IntSlice([]int{24, 46, 81, 9, 67, 6, 5, 13})
  fmt.Println(sl) // [24, 46, 81, 9, 67, 6, 5, 13]

  // Sort按照less条件排序
  sort.Sort(sl)
  fmt.Println(sl) // [81 67 46 24 13 9 6 5]
}

使用 sort.Sort 函数的实现排序后，因为我们并没有重写接口的Sort方法，所以默认使用sort包里Sort函数，它使用的是快速排序(quickSort)。我们知道快速排序是在所有数量级为(O(nlogn))的排序算法中其平均性能最好的算法，但在某些情况下其性能却并非最佳。 Go sort包中的quickSort函数也没有严格拘泥于仅使用快排算法，而是以快速排序为主，并根据目标状况在特殊条件下选择了其他不同的排序算法，包括堆排序(heapSort)、插入排序(insertionSort)等。

sort.Sort函数不保证排序是稳定的，要想使用稳定排序，需要使用sort.Stable函数。（保证排序的稳定性，相等元素的相对次序不变）

注：稳定排序：假定在待排序的序列中存在多个具有相同值的元素，若经过排序，这些元素的相对次序保持不变，即在原序列中，若r[i]=r[j]且r[i]在r[j]之前，在排序后的序列中，若r[i]仍在r[j]之前，则称这种排序算法是稳定的(stable)；否则称为不稳定的。

三、sort包内置函数

如果我们直接使用sort.Sort函数对切片进行排序还是比较繁琐的，所以sort包提供了许多内置函数，比如：Ints、Float64s、Strings、Slice,、Sort、 SearchInts、SearchFloat64s、SearchStrings和Search等。

1、sort.Ints(x []int)

  ints := []int{1, 4, 3, 2}
  fmt.Printf("%v\n", ints)
  sort.Ints(ints) //默认升序
  fmt.Printf("%v\n", ints) //[1 2 3 4]
  sort.Sort(sort.Reverse(sort.IntSlice(ints))) //降序排序
  fmt.Printf("%v\n", ints) //[4 3 2 1]

sort.Strings(x []string) sort.Float64s(x []float64)使用方法相同。

2、sort.Slice(x any, less func(i, j int) bool)

Slice函数有个好处，如果传入对象是切片，实现回调函数即可，如果传入对象是结构体，也可以自定义排序规则。

传入对象是切片，实现回调函数

  slices := []int{1, 1, 4, 5, 1, 4}
  sort.Slice(slices, func(i, j int) bool {
    return slices[i] < slices[j]
  })
  fmt.Printf("%v\n", slices)//[1 1 1 4 4 5]

传入对象是结构体，可以自定义排序规则

  type stu struct {
    name string
    age  int
  }

  stus := []stu{{"h", 20}, {"a", 23}, {"h", 21}}
  sort.Slice(stus, func(i, j int) bool {
    if stus[i].name == stus[j].name {
      return stus[i].age > stus[j].age // 年龄逆序
    }
    return stus[i].name < stus[j].name // 名字正序
  })
  fmt.Printf("%v\n", stus) //[{a 23} {h 21} {h 20}]

3、sort.SearchInts(a []int, x int) int

作用：用来二分查找对应值的索引值，索引值从0开始。

  arr := []int{1, 2, 3, 4, 5, 6, 7}
  idx := sort.SearchInts(arr, 4)
  fmt.Printf("%v\n", idx) // 3

sort.SearchFloat64s(a []float64, x float64) int sort.SearchStrings(a []string, x string) int 功能同上。

4、sort.Search(n int, f func(int) bool) int

作用：自定义的二分查找，需要自己实现查找条件

arr := []int{1, 2, 3, 4, 5, 6, 7}
  idx := sort.Search(len(arr), func(i int) bool {
    return arr[i] > 4
  })
  fmt.Printf("%v\n", idx) //4