常见排序算法总结和 Go 标准库排序源码分析

前言

排序算法是数组相关算法的基础知识之一，它们的经典思想可以用于很多算法之中。这里详细介绍了 7 个最常见排序算法，并用 Go 做了实现，同时对比这几种算法的时间复杂度、空间复杂度和稳定性。最后是对 Go 标准库排序实现的源码阅读和分析，来理解官方如何通过将以上排序算法进行组合提高性能，完成生产环境的排序实践。

排序算法分类

常见的 7 种排序算法分别是：

选择排序
冒泡排序
插入排序
希尔排序
归并排序
快速排序
堆排序

宏观上这些都是排序类算法思想，进一步地，可以根据算法特点像复杂度、是否比较元素、内外部排序等特点做更详细的分类，比如上面的算法都是内部排序的。一般我们可以基于算法是否比较了元素，将排序分为两类：

比较类排序：通过比较来决定元素间的相对次序，由于其平均时间复杂度不能突破$O(N \logN)$，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。主要实现有：桶排序、计数排序和基数排序。

通过这个的分类，可以先有一个基本的认识，就是比较类排序算法的平均时间复杂度最好的情况下是 $O(N\log N)$（一遍找元素 $O(N)$，一遍找位置$O(\log N)$）。

注：有重复大量元素的数组，可以通过三向切分快速排序，将平均时间复杂度降低到 $O(N)$

比较排序算法

因为非比较排序有其局限性，所以它们并不常用。本文将要介绍的 7 种算法都是比较类排序。

选择排序

原理：遍历数组，从中选择最小元素，将它与数组的第一个元素交换位置。继续从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。循环以上过程，直到将整个数组排序。

时间复杂度分析：$O(N^{2})$。选择排序大约需要 $N^{2}/2$ 次比较和 $N$ 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要很多的比较和交换操作。

selection sort

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


// 选择排序 (selection sort)
package sorts

func SelectionSort(arr []int) []int {

	for i := 0; i < len(arr); i++ {
		min := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[min] {
				min = j
			}
		}

		tmp := arr[i]
		arr[i] = arr[min]
		arr[min] = tmp
	}
	return arr
}

冒泡排序

原理：遍历数组，比较并将大的元素与下一个元素交换位置，在一轮的循环之后，可以让未排序i的最大元素排列到数组右侧。在一轮循环中，如果没有发生元素位置交换，那么说明数组已经是有序的，此时退出排序。

时间复杂度分析： $O(N^{2})$

bubble sort

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


// 冒泡排序 (bubble sort)
package sorts

func bubbleSort(arr []int) []int {
	swapped := true
	for swapped {
		swapped = false
		for i := 0; i < len(arr)-1; i++ {
			if arr[i+1] < arr[i] {
				arr[i+1], arr[i] = arr[i], arr[i+1]
				swapped = true
			}
		}
	}
	return arr
}

插入排序

原理：数组先看成两部分，排序序列和未排序序列。排序序列从第一个元素开始，该元素可以认为已经被排序。遍历数组，每次将扫描到的元素与之前的元素相比较，插入到有序序列的适当位置。

时间复杂度分析：插入排序的时间复杂度取决于数组的排序序列，如果数组已经部分有序了，那么为排序元素较少，需要的插入次数也就较少，时间复杂度较低。

平均情况下插入排序需要 $N^{2}/4$ 次比较以及 $N^{2}/4$ 次交换；
最坏的情况下需要 $N^{2}/2$ 比较以及 $N^{2}/2$ 次交换，最坏的情况是数组都是未排序序列（倒序）的；
最好的情况下需要 $ N-1$ 次比较和 0 次交换，最好的情况就是数组已经是排序序列。

insertion sort

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


// 插入排序 (insertion sort)
package sorts

func InsertionSort(arr []int) []int {
	for currentIndex := 1; currentIndex < len(arr); currentIndex++ {
		temporary := arr[currentIndex]
		iterator := currentIndex
		for ; iterator > 0 && arr[iterator-1] >= temporary; iterator-- {
			arr[iterator] = arr[iterator-1]
		}
		arr[iterator] = temporary
	}
	return arr
}

希尔排序

原理：希尔排序，也称递减增量排序算法，实质是插入排序的优化（分组插入排序）。对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素位置，每次只能将未排序序列数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，通过交换不相邻的元素位置，使每次可以将未排序序列的减少数量变多。

希尔排序使用插入排序对间隔 d 的序列进行排序。通过不断减小 d，最后令 d=1，就可以使得整个数组是有序的。

时间复杂度：$O(dN*M)$， M 表示已排序序列长度，d 表示间隔，即 N 的若干倍乘于递增序列的长度

shell sort

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// 希尔排序 (shell sort)
package sorts

func ShellSort(arr []int) []int {
	for d := int(len(arr) / 2); d > 0; d /= 2 { 
		for i := d; i < len(arr); i++ {
			for j := i; j >= d && arr[j-d] > arr[j]; j -= d {
				arr[j], arr[j-d] = arr[j-d], arr[j]
			}
		}
	}
	return arr
}

归并排序

原理：将数组分成两个子数组，分别进行排序，然后再将它们归并起来（自上而下）。

具体算法描述：先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。

归并算法是分治法 的一个典型应用，所以它有两种实现方法：

自上而下的递归：每次将数组对半分成两个子数组再归并（分治）
自下而上的迭代：先归并子数组，然后成对归并得到的子数组

时间复杂度分析: $O(N\log N)$

merge sort

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48


// 归并排序 (merge sort)
package sorts

func merge(a []int, b []int) []int {

	var r = make([]int, len(a)+len(b))
	var i = 0
	var j = 0

	for i < len(a) && j < len(b) {

		if a[i] <= b[j] {
			r[i+j] = a[i]
			i++
		} else {
			r[i+j] = b[j]
			j++
		}

	}

	for i < len(a) {
		r[i+j] = a[i]
		i++
	}
	for j < len(b) {
		r[i+j] = b[j]
		j++
	}

	return r

}

// Mergesort 合并两个数组
func Mergesort(items []int) []int {

	if len(items) < 2 {
		return items

	}

	var middle = len(items) / 2
	var a = Mergesort(items[:middle])
	var b = Mergesort(items[middle:])
	return merge(a, b)

}

快速排序

原理：快速排序也是分治法的一个应用，先随机拿到一个基准 pivot，通过一趟排序将数组分成两个独立的数组，左子数组小于或等于 pivot，右子数组大于等于 pivot。然后可在对这两个子数组递归继续以上排序，最后使整个数组有序。

具体算法描述：

从数组中挑选一个切分元素，称为“基准” （pivot）
排序数组，把所有比基准值小的元素排到基准前面，所有比基准值大的元素排到基准后面（相同元素不对位置做要求）。这个排序完成后，基准就排在数组的中间位置。这个排序过程称为“分区” （partition）
递归地把小于基准值元素的子数组和大于基准值的子数组排序

空间复杂度分析：快速排序是原地排序，不需要辅助数据，但是递归调用需要辅助栈，最好情况下是递归 $\log 2N$ 次，所以空间复杂度为 $O(\log 2N)$，最坏情况下是递归 $N-1$次，所以空间复杂度是 $O(N)$。

时间复杂度分析：

最好的情况是每次基准都正好将数组对半分，这样递归调用最少，时间复杂度为 $O(N \log N)$
最坏的情况是每次分区过程，基准都是从最小元素开始，对应时间复杂度为 $O(N^{^{2}})$

算法改进：

分区过程中更合理地选择基准（pivot）。直接选择分区的第一个或最后一个元素做 pivot 是不合适的，对于已经排好序，或者接近排好序的情况，会进入最差情况，时间复杂度为 $O(N^{2})$
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序
更快地分区（三向切分快速排序）：对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于 pivot、等于 pivot 和大于 pivot 切分元素

quick sort

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


// 三向切分快速排序 (quick sort)
package sorts

import (
	"math/rand"
)

func QuickSort(arr []int) []int {

	if len(arr) <= 1 {
		return arr
	}

	pivot := arr[rand.Intn(len(arr))]

	lowPart := make([]int, 0, len(arr))
	highPart := make([]int, 0, len(arr))
	middlePart := make([]int, 0, len(arr))

	for _, item := range arr {
		switch {
		case item < pivot:
			lowPart = append(lowPart, item)
		case item == pivot:
			middlePart = append(middlePart, item)
		case item > pivot:
			highPart = append(highPart, item)
		}
	}

	lowPart = QuickSort(lowPart)
	highPart = QuickSort(highPart)

	lowPart = append(lowPart, middlePart...)
	lowPart = append(lowPart, highPart...)

	return lowPart
}

堆排序

原理：堆排序是利用“堆积”（heap）这种数据结构的一种排序算法。因为堆是一个近似完全二叉树结构，满足子节点的键值或索引小于（或大于）它的父节点。

具体算法描述：

将待排序数组构建成大根堆，这个堆为初始的无序区
将堆顶元素 $R_{1}$ 与最后一个元素 $R_{n}$ 交换，此时得到新的无序区（$R_{1},R_{2},…R_{n-1}$）和新的有序区（$R_{n}$），并且满足 $R_{1,2,…n-1}<= R_{n}$
由于交换后新的堆顶 $R_{1}$可能违反堆的性质，需要对当前无序区调整为新堆，然后再次将 $R_{1}$与无序区最后一个元素交换，得到新的无序区 $R_{1},R_{2}…R_{n-2}$ 和新的有序区$R_{n-1},R_{n}$。不断重复此过程直到有序区的元素个数为$n-1$，则整个排序过程完成

时间复杂度分析：一个堆的高度为 $\log N$，因此在堆中插入元素和删除最大元素的时间复杂度为 $O(\log N)$。堆排序会对 N 个节点进行下沉操作，因为时间复杂度为 $O(N \log N)$

heap sort

实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


// 堆排序 (heap sort)
package sorts

type maxHeap struct {
	slice    []int
	heapSize int
}

func buildMaxHeap(slice []int) maxHeap {
	h := maxHeap{slice: slice, heapSize: len(slice)}
	for i := len(slice) / 2; i >= 0; i-- {
		h.MaxHeapify(i)
	}
	return h
}

func (h maxHeap) MaxHeapify(i int) {
	l, r := 2*i+1, 2*i+2
	max := i

	if l < h.size() && h.slice[l] > h.slice[max] {
		max = l
	}
	if r < h.size() && h.slice[r] > h.slice[max] {
		max = r
	}
	if max != i {
		h.slice[i], h.slice[max] = h.slice[max], h.slice[i]
		h.MaxHeapify(max)
	}
}

func (h maxHeap) size() int { return h.heapSize } 

func HeapSort(slice []int) []int {
	h := buildMaxHeap(slice)
	for i := len(h.slice) - 1; i >= 1; i-- {
		h.slice[0], h.slice[i] = h.slice[i], h.slice[0]
		h.heapSize--
		h.MaxHeapify(0)
	}
	return h.slice
}

算法复杂度比较

下面是以上 7 种排序算法各个维度的比较：

排序算法	时间复杂度（平均）	时间复杂度（最好）	时间复杂度（最坏）	空间复杂度	稳定性	备注
选择排序	$O(N^{2})$	$O(N^{2})$	$O(N^{2})$	$O(1)$	不稳定
冒泡排序	$O(N^{2})$	$O(N)$	$O(N^{2})$	$O(1)$	稳定
插入排序	$O(N^{2})$	$O(N)$	$O(N^{2})$	$O(1)$	稳定	时间复杂度和初始顺序有关
希尔排序	$O(N^{1.3})$	$O(N)$	$O(N^{2})$	$O(1)$	不稳定	改进版插入排序
归并排序	$O(N \log N)$	$O(N \log N)$	$O(N \log N)$	$O(N)$	稳定
快速排序	$O(N \log N)$	$O(N \log N)$	$O(N^{2})$	$O(N \log N)$	不稳定
堆排序	$O(N \log N)$	$O(N \log N)$	$O(N \log N)$	$O(1)$	不稳定	无法利用局部性原理

注：

稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。

Go 标准库排序源码分析

总结

这里推荐 B 站上一个有趣的排序算法动画演示视频：