手撕十大排序算法（三）
前言
十大排序包含：冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序（快排）、桶排序、计数排序、基数排序以及堆排序。
本文主要讲述归并排序和快速排序的原理和实现，并对两者进行一个简单的比较。
注：本文代码采用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.处理过程：快速排序是递归地划分数组，归并排序是递归地合并数组
注：这里为了更好理解，引用了极客时间的一张图
写在最后
本文如有错漏，麻烦在评论区指出，言某感激不尽，另外，如果本文对你有用，还麻烦客官们点个小小的爱心💖！