手撕十大排序算法（三）

前言

十大排序包含：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序（快排）、桶排序、计数排序、基数排序以及堆排序。

本文主要讲述归并排序和快速排序的原理和实现，并对两者进行一个简单的比较。

注：本文代码采用Golang实现。

快速排序

快速排序，又称分区交换排序（partition-exchange sort），关于快速排序这个名字的由来，个人猜测是是因为这句话”快速排序通常比其他算法更快“。

快速排序本质上是一种分治算法，它的思想是在一堆数字中选出一个基准值（亦称主元），通过遍历数字，把小于基准值的数字放左边，把大于基准值的数字放右边；再把左边和右边的数组做同样的操作（递归），直到子数组无法再分割，最后再将这些子数组合并起来（因为此时已经都排好序），即为排好序的数组。

在大部分的文章中都提到，快速排序是一种原地排序的算法，即不申请多余的空间，但其实更准确地说，快速排序是否原地，取决于你的实现方式，它既可以是原地的，也可以是不原地的，如下文。

非原地排序版本

首先展现的是非原地排序的版本，因为这种方式比较容易理解。

前面提到，快速排序是一种分治算法，所以常用递归来实现，而用递归实现，首要的就是知道递归结束条件，在这里就是当子数组的长度小于等于1时，因为这时候只有一个元素，已经无法再排序了。

接着就是利用基准值将数组分割，这里默认以第一个元素为基准值，基准值的选择也会影响到快速排序的时间复杂度（后面会讲到），最后就是将两个子数组和基准值合并。

// 快速排序：非原地排序版本
func quickSort1(arr []int) []int {
  n := len(arr)
  // 递归结束条件
	if n <= 1 {
		return arr
	}
	left, right := []int{}, []int{}
	// 挑选基准值，这里以第一个元素为基准值
	base := arr[0]
	arr = arr[1:]
	// 对数组进行分割
	for _, num := range arr {
		if num < base {
			left = append(left, num)
		} else {
			right = append(right, num)
		}
	}
	// 合并左右两个数组及基准值
	result := append(quickSort1(left), base)
	result = append(result, quickSort1(right)...)
	return result
}

原地排序的版本

对于原地排序的版本，其实也分为两种，一种是默认选择第一个元素为基准值，一种是默认选择最后一个元素为基准值，两者的原理相同，但是分区算法的写法不同。

这里以第一个元素为基准值的写法，讲解快速排序原地排序的思路：

首先原地排序需要三个指针，一个是基准值，一个是i指针，一个k指针，i指针的左边都是比基准值小的元素，i指针的右边都是比基准值大的元素（还有待比较的），k指针负责遍历。

第一轮遍历，k指针走到13，比基准值大，继续走到5，比基准值小，此时i指针需移动一步，并与k指针交换值。

第二轮遍历，k指针继续走，走到3这个位置发现又比基准值小，i指针再次移动一步，两者进行交换。

第三轮遍历同理。

第三轮遍历后，第一轮排序已经完成，此时由于我们默认选择第一个元素为基准值，所以还要把i指针和基准值互换，从而才能保证小于基准值的都在左边，大于基准值的都在右边！！

以第一个元素为基准值的写法

// 快速排序：原地排序版本
// 基准值默认选择第一个元素
func quickSort2(arr []int, startIdx, endIdx int) {
	// 递归截止条件
	if startIdx >= endIdx {
		return
	}
	// p是基准值
	p := partition(arr, startIdx, endIdx)
	// 对子数组进行排序，因为p是基准值，所以不用进入下一轮的排序中
	quickSort2(arr, startIdx, p-1)
	quickSort2(arr, p+1, endIdx)
}

// 对数组进行划分，并返回下次划分的基准值
func partition(arr []int, startIdx, endIdx int) int {
	// 设定基准值
	base := arr[startIdx]
	i := startIdx
	// 把小于基准值的元素都挪到左边
	for k := startIdx + 1; k <= endIdx; k++ {
		if arr[k] < base {
			i++
			arr[k], arr[i] = arr[i], arr[k]
		}
	}
	// 这一步把基准值放到比它小的元素的后面
	arr[i], arr[startIdx] = arr[startIdx], arr[i]
	return i
}

func quickSort2Test() {
	nums := []int{6, 10, 13, 5, 8, 3, 2, 11}
	quickSort2(nums, 0, len(nums)-1)
	fmt.Println(nums)
}

以最后一个元素为基准值的写法

// 快速排序：原地排序版本
// 基准值默认选择最后一个元素
func partition2(arr []int, startIdx, endIdx int) int {
	// 基准值
	base := arr[endIdx]
	i := startIdx - 1
	// 这一步把小于基准值的元素都挪到前面
	for k := startIdx; k < endIdx; k++ {
		if arr[k] < base {
			i++
			arr[k], arr[i] = arr[i], arr[k]
		}
	}
	// 这一步把基准值放到比它小的元素的后面
	arr[i+1], arr[endIdx] = arr[endIdx], arr[i+1]
	return i + 1
}

func quickSort3(arr []int, startIdx, endIdx int) {
	// 递归截止条件
	if startIdx >= endIdx {
		return
	}
	p := partition2(arr, startIdx, endIdx)
	quickSort3(arr, startIdx, p-1)
	quickSort3(arr, p+1, endIdx)
}

func quickSort3Test() {
	nums := []int{6, 10, 13, 5, 8, 3, 2, 11}
	quickSort3(nums, 0, len(nums)-1)
	fmt.Println(nums)
}

关于快速排序的时间复杂度： 快速排序的复杂度取决于挑选的基准值，当数组本身有序（正序或者逆序），且每次都选第一个元素作为基准值，则划分的次数为O（n）

如果每次选取的基准值恰好都是中间值，那么划分的次数变为O(logn)，而每次依据基准值划分元素的复杂度都是 O(n)，所以快速排序的平均复杂度为 O（nlogn），最优时间复杂度为 O（nlogn），最坏的时间复杂度为O（$n^2$）。

关于快速排序是否稳定： 快速排序是一个不稳定的算法，以arr = [ 1, 2, 2, 3, 4, 5, 6 ]为例：在快速排序的分区阶段，如果选择arr[2]为基准值，且大于等于2的放在大数数组中，即arr[1]会到基准值的右边，那么数组中的两个2跟原来的顺序不一致，排序不稳定。

同理，如果选择arr[1]为基准值，且小于等于2的放在小数数组中，即arr[2]会到基准值的左边，那么数组中的两个2跟原来的顺序不一致，排序不稳定。

归并排序

如果你前面已经理解了快速排序，再来看归并排序，你会发现两个算法其实非常像，因为快速排序是递归地划分数组，归并排序是递归地合并数组，这也是我为什么将两个算法放在一起讲的原因。

这里盗了别人的一张图，可以看到归并排序前期不断将大数组划分成小数组，而当数组划分得足够小时（长度为1），再对比左右两个子数组的大小，并合成一个新的排序数组，层层递归的话，最终合并后的数组就是一个排好序的数组。

注：图片来源这里，侵权删

// 合并
func merge(left []int, right []int) []int {
	leftIdx, rightIdx := 0, 0
	result := []int{}
	for leftIdx < len(left) && rightIdx < len(right) {
		if left[leftIdx] <= right[rightIdx] {
			result = append(result, left[leftIdx])
			leftIdx += 1
		} else {
			result = append(result, right[rightIdx])
			rightIdx += 1
		}
	}
	// 上述for循环有两种情况：
	// 1.left数组和right数组长度一致
	// 2.left数组和right数组长度不一致，则必定有一方有多余元素，需要把这些多余元素复制到队尾
	result = append(result, left[leftIdx:]...)
	result = append(result, right[rightIdx:]...)
	return result
}

func mergeSort(arr []int) []int {
	n := len(arr)
	if n <= 1 {
		return arr
	}

  split := n / 2
  // 不断划分左子数组
	left := mergeSort(arr[:split])
	right := mergeSort(arr[split:])
	return merge(left, right)
}

关于归并排序是否稳定： 从上述划分的过程可以看到，归并排序只会两两比较，并没有快速排序根据基准值划分的操作，所以是稳定的。

关于归并排序是否原地： 从上述代码实现可以看到，归并排序需要一个中间数组存储排序后的值，所以不是原地排序。

关于归并排序的时间复杂度： 归并排序划分部分时间复杂度为O(logn)，合并部分时间复杂度为O(n)，所以总时间复杂度为O(nlogn)

归并排序 VS 快速排序

1.基准值：归并排序并不需要基准值，而快速排序需要一个基准值

2.稳定性：归并排序是稳定排序，但不是原地排序；快速排序是非稳定排序，但可以实现原地排序。

3.处理过程：快速排序是递归地划分数组，归并排序是递归地合并数组

注：这里为了更好理解，引用了极客时间的一张图

写在最后

本文如有错漏，麻烦在评论区指出，言某感激不尽，另外，如果本文对你有用，还麻烦客官们点个小小的爱心💖！