Golang源码学习之sort

本文主要介绍go语言sort包内部分排序函数的实现，学习如何在实际的工业代码中如何应用那些基础的排序算法。

Sort方法

sort包内的Sort方法位于源文件sort/sort.go，是一个通用的非稳定排序的方法。

API设计

函数签名

func Sort(data Interface)

go由于没有泛型，要实现通用排序只能另辟蹊径。
sort使用接口类型sort.Interface作为方法参数，sort.Interface接口定义了交换和比较的方法，按照比较方法的结果进行排序。

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

Sort方法实现

一般不稳定排序我们会先考虑快排，不过需要解决以下两个问题：

• 如何避免递归调用过深
• 如何避免最差情况时间复杂度

下面我们看一下go源码中使用了什么方法来解决这些问题，以及它使用了哪些优化手段。

quickSort函数

Sort方法内部调用了quickSort函数，主要逻辑在该函数中

func quickSort(data Interface, a, b, maxDepth int)

a,b传进来的是(0,data.Len())，对应的排序范围为[a, b)
maxDepth传进来的是根据Len计算出来的对数值

// quickSort方法体
for b - a > 12 {
	if maxDepth == 0 {
		heapSort(data, a, b)
		return
	}
	maxDepth--
	// 以下为快排逻辑，下文会讲到
}
if b - a > 1 {
	// 步长为6的shell排序
	for i := a + 6; i < b; i++ {
		if data.Less(i, i-6) {
			data.Swap(i, i-6)
		}
	}
	// 插入排序
	insertionSort(data, a, b)
}

quickSort是一个递归的方法，以上代码主要关注出口的逻辑

• 当maxDepth为0时，为了避免继续递归产生很深的调用栈，源码使用了堆排序对子序列进行排序
• 当子序列长度小于等于12，此时会先用步长为6的shell排序预处理，然后使用插入排序对子序列排序

以上两步优化，限制了调用栈深度，加速了短的子序列的排序

快排流程

for b - a > 12 {
	// 省略了上面讲到的代码
	maxDepth--
	mlo, mhi := doPivot(data, a, b)
	if mlo-a < b-mhi {
		quickSort(data, a, mlo, maxDepth)
		a = mhi
	} else {
		quickSort(data, mhi, b, maxDepth)
		b = mlo
	}
}

每次循环会处理一部分子任务，所以深度需要减一
doPivot函数对子序列进行交换，使得左边元素的值小于右边，相同元素放在中间，返回等于pivot和大于pivot的第一个元素位置
每次处理长度较小的子序列，做这一步目的应该是为了避免递归深度太深，下一次循环处理剩余的子序列

doPivot方法

这个方法略为复杂，主要干了以下三件事

• 优化取pivot，使用了三值取中间值的优化方法
• 交换元素，使得左边元素小于pivot右边元素大于pivot
• 优化相等的元素，尽可能使相等元素放中间，同时找到左右边界

取pivot

m := int(uint(lo+hi) >> 1)
// 对于很长的子序列，会先从三个位置的周围寻找中值
if hi-lo > 40{
	s := (hi - lo) / 8
	medianOfThree(data, lo, lo+s, lo+2*s)
	medianOfThree(data, m, m-s, m+s)
	medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
}
// medianOfThree会对这三个进行比较，最终的结果是data[m]<data[lo]<data[hi-1]
// pivot在lo位置上
medianOfThree(data, lo, m, hi-1)

交换元素

pivot := lo
a, c := lo+1, hi-1 // lo和hi-1都交换过，后面不需要再交换，再处理相等的时候再考虑
// 跳过小于pivot的元素
for ; a < c && data.Less(a, pivot); a++{}
b := a // b指向第一个大于等于pivot的元素
for {
	// data[b] <= pivot，找到第一个大于pivot的位置b
	for ; b < c && !data.Less(pivot, b); b++ { 
	}
	// c起始位置在hi-1，而hi-1已经调整过
	// data[c-1] > pivot，找到第一个小于等于pivot的右边位置
	for ; b < c && data.Less(pivot, c-1); c-- {
	}
	if b >= c {
		break
	}
	// data[b] > pivot; data[c-1] <= pivot
	data.Swap(b, c-1)
	b++ // data[b-1] <= pivot
	c-- // data[c] > pivot
}

这段交换逻辑主要是理解b和c指向的位置
b经过第一个for循环，总是指向第一个大于pivot的元素或者结束位置，遇到相等元素会跳过
c经过第二个for循环，总是指向小于等于pivot元素的右边，所以后面交换的位置是c-1
循环结束之后，b和c相等。c如果有移动，那么指向大于pivot的第一个元素，否则指向hi-1

移动相等元素

protect := hi-c < 5 // 如果大于pivot的元素小于5个认为划分有倾斜，小于等于的一侧可能有相等元素
// 如果没有倾斜，尝试检查三个位置是否有相等元素
if !protect && hi-c < (hi-lo)/4 {
	dups := 0
	if !data.Less(pivot, hi-1) { // 之前没有检查过，不过相等的概率比较低
		data.Swap(c, hi-1)
		c++
		dups++
	}
	if !data.Less(b-1, pivot) { // 检查边界左边元素
		b--
		dups++
	}
	// 小于等于的元素范围占3/4以上，那么中间元素也在小于等于范围内
	if !data.Less(m, pivot) {
		data.Swap(m, b-1)
		b--
		dups++
	}
	protect = dups > 1 // 如果有2个相等元素
}
// 主要的移动逻辑
if protect {
	for {
		// for: data[b] == pivot
		for ; a < b && !data.Less(b-1, pivot); b--{
		}
		// after for: data[b-1]<pivot
		// for: data[a] < pivot
		for ; a < b && data.Less(a, pivot); a++ {
		}
		// after for: data[a] == pivot
		if a >= b {
			break
		}
		data.Swap(a, b-1)
		a++
		b--
	}
}

是否需要找相同元素根据划分的倾斜情况来，对于长的子序列会根据比例判断是否需要寻找相同元素
最后的for循环检查小于等于的元素，把相等元素移动到中间，结束之后a向右移，b向左移

最后交换pivot，返回pivot位置和大于pivot的第一个位置

data.Swap(pivot, b-1) 
return b-1, c

总结

Sort方法做了以下优化来控制调用深度、避免最坏时间复杂度以及加速短序列排序

• 使用maxDepth控制递归深度，每处理一个子序列maxDepth减一，当maxDepth为0时采用堆排序
• 在快排中使用了三位置取中值的优化，避免最坏时间复杂度；元素交换之后尝试把相等元素移动到中间，减少子序列范围
• 当子序列长度小于12，使用shell排序预处理，然后用插入排序优化短序列排序

虽然快排本身看起来简单，要在工业软件中使用，还是需要做许多优化的。

打赏