Golang sort源码阅读

复习算法

  • 插入排序(insertion sort) 插入排序 可以想象为打牌的时候,我们抓到一张牌之后,从右往左 (或者从左往右)找到合适的位置,然后插入。它的时间复杂度是O(n^2)。

    insertion sort插入排序

  • 希尔排序(shell sort) 希尔排序 是插入排序的一种改进版本,它每次以一定步长进行排序,一直重复 到步长为1为止。

  • 堆排(heapsort) 堆排序 借助了堆这个数据结构的特性,将数据放到堆以后再取出,便有了顺序。

  • 快排(quicksort) 快排 每次选取一个哨兵,然后将比它更小的放左边,比它更大的放右边, 然后递归对左右两侧的子数组进行快排的操作,最终数组便会是一个有序的数组。

看看Go的sort实现

我们来看看Go的sort是咋实现的,首先得让要排序的对象实现这个接口:

// A type, typically a collection, that satisfies sort.Interface can be
// sorted by the routines in this package. The methods require that the
// elements of the collection be enumerated by an integer index.
type Interface interface {
	// Len is the number of elements in the collection.
	Len() int
	// Less reports whether the element with
	// index i should sort before the element with index j.
	Less(i, j int) bool
	// Swap swaps the elements with indexes i and j.
	Swap(i, j int)
}

在这个接口之上,我们才能继续阅读源码,以 sort.Ints 为例:

func Ints(a []int) { Sort(IntSlice(a)) }

func Sort(data Interface) {
	n := data.Len()
	quickSort(data, 0, n, maxDepth(n))
}

看函数名,它是用的快排,但是点进去,你会发现其实它是一个混合排序算法:

func quickSort(data Interface, a, b, maxDepth int) {
	for b-a > 12 { // Use ShellSort for slices <= 12 elements
		if maxDepth == 0 {
			heapSort(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := doPivot(data, a, b)
		// Avoiding recursion on the larger subproblem guarantees
		// a stack depth of at most lg(b-a).
		if mlo-a < b-mhi {
			quickSort(data, a, mlo, maxDepth)
			a = mhi // i.e., quickSort(data, mhi, b)
		} else {
			quickSort(data, mhi, b, maxDepth)
			b = mlo // i.e., quickSort(data, a, mlo)
		}
	}
	if b-a > 1 {
		// Do ShellSort pass with gap 6
		// It could be written in this simplified form cause b-a <= 12
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		insertionSort(data, a, b)
	}
}

可以看得出来,在不同的条件下,它会使用不同的算法:

  • 当元素数量小于12时,使用shell sort(插入排序的一种更高效的改进版本)
  • 元素数量大于12且maxDepth不为0时,使用原地快排
  • maxDepth = 0时,转而使用 heap sort

所以可以看出来,Go的sort方法是比较复杂的,它结合了多种排序方法进行排序。

其实其它语言也是一样的,比如Python和Java的排序,就使用了 TimSort,也是一种 混合排序算法。



更多文章
  • Cython! Python和C两个世界的交叉点
  • socketserver 源码阅读与分析
  • functools 源码阅读与分析
  • contextlib代码阅读
  • Redis通信协议阅读
  • Collections 源码阅读与分析
  • 2016年就要结束了,2017年就要开始啦!
  • unittest 源代码阅读
  • APUEv3 - 重读笔记
  • Mock源码阅读与分析
  • Thinking in Python
  • 我的代码进CPython标准库啦
  • Python零碎小知识
  • 工作一年的总结
  • Python和单元测试