Go - sort模块源码分析

[Caaalabash]

1. Go - sort模块源码分析

浏览sort模块源码，源码可以整理成如下结构

上面三张图已经能明确的体现出：sort模块到底有什么？内部是什么样的调用流程？自定义类型排序应该如何实现？

2. 整体结构

2.1 如何实现自定义类型的排序？

一个满足sort.Interface接口的类型可以被本包的函数进行排序，方法要求集合中的函数可以被整数索引

type Interface interface {
    // Len方法返回集合中的元素个数
    Len() int
    // Less方法报告索引i的元素是否比索引j的元素小
    Less(i, j int) bool
    // Swap方法交换索引i和j的两个元素
    Swap(i, j int)
}

IntSlice的作用在于给[]int类型添加方法以满足Interface接口, 以实现[]int类型的排序

type IntSlice []int

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] }
// Sort无需实现，Search根据需要实现
func (p IntSlice) Sort() { Sort(p) }
func (p IntSlice) Search(x int) int { return SearchInts(p, x) }

因此，如果需要实现自定义类型的排序，参考type IntSlice的实现即可

2.2 如果实现集合的反序？

究极带秀的做法，实现一个reverse类型用于包装Interface，其内部在调用Less函数时交换i,j的顺序

type Interface interface {
    Len() int
    Less(i, j int) bool
    Swap(i, j int)
}
type reverse struct {
	Interface
}
func (r reverse) Less(i, j int) bool {
	return r.Interface.Less(j, i)
}
func Reverse(data Interface) Interface {
	return &reverse{data}
}

2.3 默认采用那种排序方式？

日常使用中最常用的就属sort.Ints了，它首先将传入的[]int类型转换为内置的IntSlice类型，然后调用Sort函数进行不稳定排序

func Ints(a []int) { Sort(IntSlice(a)) }
func Float64s(a []float64) { Sort(Float64Slice(a)) }
func Strings(a []string) { Sort(StringSlice(a)) }

2.4 如何判断集合是有序的？

从后向前遍历，调用date.Less方法，只要出现Less(后一个值, 前一个值)为true的情况，则说明是无序的

func IsSorted(data Interface) bool {
	n := data.Len()
	for i := n - 1; i > 0; i-- {
		if data.Less(i, i-1) {
			return false
		}
	}
	return true
}
func IntsAreSorted(a []int) bool { return IsSorted(IntSlice(a)) }
func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Slice(a)) }
func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }

2.5 Search是如何实现的？

假设集合都是经过排序的，要找到目标元素，通过二分法查找，Search函数可以作为二分法模版参考了

func Search(n int, f func(int) bool) int {
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1)
		if !f(h) {
			i = h + 1
		} else {
			j = h
		}
	}
	return i
}

func SearchInts(a []int, x int) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}
func SearchFloat64s(a []float64, x float64) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}
func SearchStrings(a []string, x string) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

func (p IntSlice) Search(x int) int { return SearchInts(p, x) }
func (p Float64Slice) Search(x float64) int { return SearchFloat64s(p, x) }
func (p StringSlice) Search(x string) int { return SearchStrings(p, x) }

2.6 sort.Sort 和 sort.Stable

稳定排序：多个具有相同的关键字的记录，经过排序，这些记录的相对次序保持不变

Sort是不稳定排序，速度较Stable会更快

It makes one call to data.Len to determine n, and O(n*log(n)) calls to data.Less and data.Swap. The sort is not guaranteed to be stable.

sort.Sort背后的调用路径如下所示：

• maxDepth
• quickSort
  • doPivot
    • medianOfThree
  • heapSort
    • siftDown
  • insertionSort

Stable是稳定排序

It makes one call to data.Len to determine n, O(nlog(n)) calls to data.Less and O(nlog(n)*log(n)) calls to data.Swap.

sort.Stable背后的调用路径如下所示：

• stable
  • insertionSort
  • symMerge
    • rotate
      • swapRange

这部分代码先仰望吧，有太多细节需要仔细研读了