03-归并排序、随机快排.md

[TOC]
# 1 归并排序、随机快排

## 1.1 归并排序

1、 整体是递归的，左边排好序右边排好序，最后merge让整体有序，merge过程需要申请和被排序数组等长度的辅助空间

2、 让其整体有序的过程里用了排外序的方法

3、 利用master公式来求解归并的时间复杂度

4、 归并排序可改为非递归实现

### 1.1.1 递归思路：

> 主函数希望一个数组的0~3位置排序f(arr, 0, 3)

> 第一层递归希望f(arr, 0, 1)和f(arr, 2, 3)分别有序。

> 第二层递归：f(arr, 0, 1)希望f(arr, 0, 0)和f(arr, 1, 1)有序, f(arr, 2, 3)希望f(arr, 2, 2)和f(arr, 3, 3)分别有序。

> f(arr, 0, 0)和f(arr, 1, 1)已经有序，回到第一层递归f(arr, 0, 1)中去merge0位置的数和1位置的数后刷回元素组的0到1位置，0到1位置变为有序; f(arr, 2, 2)和f(arr, 3, 3)已经有序，回到f(arr, 2, 3)中去merge2位置的数和3位置的数后刷回原数组的2到3位置，2到3位置变为有序。

> f(arr, 0, 3)需要merge f(arr, 0, 1)和f(arr, 2, 3)此时f(arr, 0, 1)和f(arr, 2, 3)已经有序merge后copy到原数组的0到3位置。于是f(arr, 0, 3)整体有序

### 1.1.2 非递归思路

> 对于一个给定长度为n的数组arr，我们希望arr有序

> 初始分组为a=2，我们让每两个有序，不够一组的当成一组

> 分组变为a=2*2=4,由于上一步已经保证了两两有序，那么我们可以当前分组的四个数的前两个和后两个数merge使得每四个数有序

> 分组变为a=2*4=8，...直至a>=n,整体有序

```Go
// mergeSort归并排序递归实现
func mergeSort(arr []int) {
	// 空数组或者只存在1个元素
	if len(arr) < 2 {
		return
	}

	// 传入被排序数组，以及左右边界到递归函数
	process(arr, 0, len(arr)-1)
}

// process 使得数组arr的L到R位置变为有序
func process(arr []int, L, R int) {
	if L == R { // base case
		return
	}

	mid := L + (R-L)/2
	process(arr, L, mid)
	process(arr, mid+1, R)
	// 当前栈顶左右已经排好序，准备左右merge，注意这里的merge动作递归的每一层都会调用
	merge(arr, L, mid, R)
}

// merge arr L到M有序 M+1到R有序 变为arr L到R整体有序
func merge(arr []int, L, M, R int) {
	// merge过程申请辅助数组，准备copy
	help := make([]int, 0)
	p1 := L
	p2 := M + 1
	// p1未越界且p2未越界
	for p1 <= M && p2 <= R {
		if arr[p1] <= arr[p2] {
			help = append(help, arr[p1])
			p1++
		} else {
			help = append(help, arr[p2])
			p2++
		}
	}

	// p2越界的情况
	for p1 <= M {
		help = append(help, arr[p1])
		p1++
	}

	// p1越界的情况
	for p2 <= R {
		help = append(help, arr[p2])
		p2++
	}

	// 把辅助数组help中整体merge后的有序数组，copy回原数组arr中去
	for j := 0; j < len(help); j++ {
		arr[L+j] = help[j]
	}
}
```

```Go
// 归并排序非递归实现
func mergeSort2(arr []int) {
	if len(arr) < 2 {
		return
	}

	N := len(arr)
	// 当前有序的，左组长度, 那么实质分组大小是从2开始的
	mergeSize := 1
	for mergeSize < N {
		// L表示当前分组的左组的位置，初始为第一个分组的左组位置为0
		L := 0
		for L < N {
			// L...M  当前左组（mergeSize）
			M := L + mergeSize - 1
			// 当前左组包含当前分组的所有元素，即没有右组了，无需merge已经有序
			if M >= N {
				break
			}
			//  L...M为左组   M+1...R(mergeSize)为右组。
			//  右组够mergeSize个的时候，右坐标为M + mergeSize，右组不够的情况下右组边界坐标为整个数组右边界N - 1
			R := math.Min(float64(M+mergeSize), float64(N-1))
			// 把当前组进行merge
			merge(arr, L, M, int(R))
			L = int(R) + 1
		}
		// 如果mergeSize乘2必定大于N，直接break。
		// 防止mergeSize溢出，有可能N很大，下面乘2有可能范围溢出（整形数大于21亿）
		if mergeSize > N/2 {
			break
		}
		mergeSize *= 2
	}
}

// merge arr L到M有序 M+1到R有序 变为arr L到R整体有序
func merge(arr []int, L, M, R int) {
	// merge过程申请辅助数组，准备copy
	help := make([]int, 0)
	p1 := L
	p2 := M + 1
	// p1未越界且p2未越界
	for p1 <= M && p2 <= R {
		if arr[p1] <= arr[p2] {
			help = append(help, arr[p1])
			p1++
		} else {
			help = append(help, arr[p2])
			p2++
		}
	}

	// p2越界的情况
	for p1 <= M {
		help = append(help, arr[p1])
		p1++
	}

	// p1越界的情况
	for p2 <= R {
		help = append(help, arr[p2])
		p2++
	}

	// 把辅助数组help中整体merge后的有序数组，copy回原数组arr中去
	for j := 0; j < len(help); j++ {
		arr[L+j] = help[j]
	}
}
```

### 1.1.3 归并排序时间复杂度

> 递归复杂度计算，用master公式带入，子问题规模N/2，调用2次，除了递归之外的时间复杂度为merge的时间复杂度，为O(N)。a=2,b=2,d=1满足master第一条logb^a == d规则

```math
T(N) = 2T(N/2) + O(N) => O(N*logN)
```

> 非递归复杂度计算，mergeSize*2等于分组从2->4->8->...,每个分组下执行merge操作O(N)。所以非递归和递归的时间复杂度相同，也为O(N)*O(logN) = O(NlogN)

> 所以递归和非递归的归并排序时间复杂度都为O(NlogN)

Tips: 为什么选择，冒泡，插入排序的时间复杂度为O(N^2)而归并排序时间复杂度为O(NlogN)，因为选择，冒泡，插入排序的每个元素浪费了大量的比较行为，N次。而归并没有浪费比较行为，每次比较的结果有序后都会保存下来，最终merge

### 1.1.4 归并面试题

1、在一个数组中，一个数左边比它小的数的总和，叫做小和，所有数的小和累加起来，叫做数组的小和。求数组的小和。例如[1, 3, 4, 2, 5]

```
    1左边比1小的数：没有
    
    3左边比3小的数：1
    
    4左边比4小的数：1、3
    
    2左边比2小的数为：1
    
    5左边比5小的数为：1、3、4、2
    
    所以该数组的小和为：1+1+3+1+1+3+4+2 = 16
```

> 暴力解法，每个数找之前比自己小的数，累加起来，时间复杂度为O(N^2)，面试没分。但是暴力方法可以用来做对数器

> 归并排序解法思路：O(NlogN)。在递归merge的过程中，产生小和。规则是左组比右组数小的时候产生小和，除此之外不产生；当左组和右组数相等的时候，拷贝右组的数，不产生小和；当左组的数大于右组的时候，拷贝右组的数，不产生小和。实质是把找左边比本身小的数的问题，转化为找这个数右侧有多少个数比自己大，在每次merge的过程中，一个数如果处在左组中，那么只会去找右组中有多少个数比自己大

```Go
// smallSum 数组小和问题
func smallSum(arr []int) int {
	if len(arr) < 2 {
		return 0
	}

	return sSum(arr, 0, len(arr) - 1)
}

// arr[L..R]既要排好序，也要求小和返回
// 所有merge时，产生的小和，累加
// 左 排序   merge
// 右 排序  merge
// arr 整体 merge
func sSum(arr []int, l, r int) int {
	// 只有一个数，不存在右组，小和为0
	if l == r {
		return 0
	}

	mid := l + (r - l) / 2
	// 左侧merge的小和+右侧merge的小和+整体左右两侧的小和
	return sSum(arr, l, mid) + sSum(arr, mid + 1, r) + sumMerge(arr, l, mid, r);
}

func sumMerge(arr []int, L, M, R int) int {
	// merge过程申请辅助数组，准备copy
	help := make([]int, 0)
	p1 := L
	p2 := M + 1
	res := 0
	// p1未越界且p2未越界
	for p1 <= M && p2 <= R {
		// 当前的数是比右组小的，产生右组当前位置到右组右边界数量个小和，累加到res。否则res加0
		if arr[p1] < arr[p2] {
			help = append(help, arr[p1])
			res += (R - p2 + 1) * arr[p1]
			p1++
		} else {
			help = append(help, arr[p2])
			res += 0
			p2++
		}
	}

	// p2越界的情况
	for p1 <= M {
		help = append(help, arr[p1])
		p1++
	}

	// p1越界的情况
	for p2 <= R {
		help = append(help, arr[p2])
		p2++
	}

	// 把辅助数组help中整体merge后的有序数组，copy回原数组arr中去
	for j := 0; j < len(help); j++ {
		arr[L+j] = help[j]
	}
	return res
}
```

> 什么样的题目以后可以借助归并排序：纠结每个数右边(左边)有多少个数比自身大，比自身小等。求这种数的数量等等

## 1.2 快排

### 1.2.1 Partion过程

> 给定一个数组arr，和一个整数num。请把小于等于num的数放在数组的左边，大于num的数放在数组的右边(不要求有序)。要求额外空间复杂度为O(1)，时间复杂度为O(N)。例如[5,3,7,2,3,4,1]，num=3,把小于等于3的放在左边，大于3的放在右边

思路：设计一个小于等于区域，下标为-1。

1、 开始遍历该数组，如果arr[i]<=num,当前数和区域下一个数交换，区域向右扩1，i++

2、 arr[i] > num, 不做操作，i++

> 给定一个数组，和一个整数num。请把小于num的数放在数组的左边，等于num的放中间，大于num的放右边。要求额外空间复杂度为O(1)，时间复杂度为O(N)。[3,5,4,0,4,6,7,2]，num=4。该问题实质就是经典的荷兰国旗问题

思路：设计一个小于区域，下标为-1。设计一个大于区域，下表为arr.length, 数组的左右越界位置。

1、 如果arr[i]等于当前位置的数num， i++直接跳下一个。间接的扩大了等于区域

2、 如果arr[i]当前位置的数小于num，当前位置的数arr[i]和小于区域的右一个交换，小于区域右扩一个位置，当前位置i++

3、 如果arr[i]当前位置的数大于num，当前位置的数arr[i]与大于区域的左边一个交换，大于区域左移一个位置，i停在原地不做处理，这里不做处理是因为当前位置的数是刚从大于区域交换过来的数，还没做比较

4、当i和大于区域的边界相遇，停止操作

### 1.2.2 快排1.0：每次partion搞定一个位置

思路：在给定数组上做partion, 选定数组最右侧的位置上的数作为num，小于num的放在该数组的左边，大于num的放在该数组的右边。完成之后，把该数组最右侧的数组num，交换到大于num区域的第一个位置，确保了交换后的num是小于等于区域的最后一个数(该数直至最后可以保持当前位置不变，属于已经排好序的数)，把该num左侧和右侧的数分别进行同样的partion操作(递归)。相当于每次partion搞定一个数的位置，代码实现quickSort1


### 1.2.3 快排2.0：每次partion搞定一批位置

思路：借助荷兰国旗问题的思路，把arr进行partion，把小于num的数放左边，等于放中间，大于放右边。递归时把小于num的区域和大于num的区域做递归，等于num的区域不做处理。相当于每次partion搞定一批数，该批数都与标记数相等。代码实现quickSort2

> 第一版和第二版的快排时间复杂度相同O(N^2)：用最差情况来评估，本身有序，每次partion只搞定了一个数是自身，进行了N次partion

### 1.2.4 快排3.0：随机位置作为num标记位

> 随机选一个位置i，让arr[i]和arr[R]交换，再选取arr[R]的值作为标记位。剩下的所有过程跟快排2.0一样。即为最经典的快排，时间复杂度为O(NlogN)

> 为什么随机选择标记位的时间复杂度由原本不随机的O(N^2)变为O(NlogN)了呢? 如果我们随机选择位置那么就趋向于标记位的左右两侧的递归规模趋向于N/2。那么根据master公式，可以计算出算法复杂度为O(NlogN)。实质上，在我们选择随机的num时，最差情况，最好情况，其他各种情况的出现概率为1/N。对于这N种情况，数学上算出的时间复杂度最终期望是O(NlogN),这个数学上可以进行证明，证明相对较复杂

> 例如我们的num随机到数组左侧三分之一的位置，那么master公式为

```math
T(N) = T((1/3)N) + T((2/3)N) + O(N)
```

> 对于这个递归表达式，master公式是解不了的，master公式只能解决子问题规模一样的递归。对于这个递归，算法导论上给出了计算方法，大致思路为假设一个复杂度，看这个公式是否收敛于这个复杂度的方式

### 1.2.5 快排的时间复杂度与空间复杂度

> 时间复杂度参考上文每种的复杂度

> 空间复杂度：O(logN)。空间复杂度产生于每次递归partion之后，我们需要申请额外的空间变量保存相等区域的左右两侧的位置。那么每次partion需要申请两个变量，多少次partion？实质是该递归树被分了多少层，树的高度，有好有坏，最好logN,最差N。随机选择num之后，期望仍然是概率累加，收敛于O(logN)。

```Go
package main

// swap 交换数组中的两个位置的数
func swap(arr []int, i, j int) {
	tmp := arr[i]
	arr[i] = arr[j]
	arr[j] = tmp
}

// partition 对数组进行partition处理
func partition(arr []int, L, R int) int {
	if L > R {
		return -1
	}
	if L == R {
		return L
	}
	// 选定左边界的左边一个位置作为小于区域的起点
	lessEqual := L - 1
	index := L
	// 每次搞定一个位置
	for index < R {
		if arr[index] <= arr[R] {
			lessEqual++
			swap(arr, index, lessEqual)
		}
		index++
	}
	lessEqual++
	swap(arr, lessEqual, R)
	return lessEqual
}

//  arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
//  小于arr[R]放左侧  等于arr[R]放中间  大于arr[R]放右边
//  返回中间区域的左右边界
func netherlandsFlag(arr []int, L, R int) []int {
	// 不存在荷兰国旗问题
	if L > R {
		return []int{-1, -1}
	}

	// 已经都是等于区域，由于用R做划分返回R位置
	if L == R {
		return []int{L, R}
	}

	// < 区 右边界
	less := L - 1
	// > 区 左边界
	more := R
	index := L
	for index < more {
		// 当前值等于右边界，不做处理，index++
		if arr[index] == arr[R] {
			index++
		} else if arr[index] < arr[R] { // 小于交换当前值和左边界的值
			less++
			swap(arr, index, less)
			index++
		} else { // 大于右边界的值
			more--
			swap(arr, index, more)
		}
	}
	// 比较完之后，把R位置的数，调整到等于区域的右边，至此大于区域才是真正意义上的大于区域
	swap(arr, more, R)
	return []int{less + 1, more}
}

func QuickSort1(arr []int) {
	if len(arr) < 2 {
		return
	}

	sortByPartition(arr, 0, len(arr)-1)
}

func sortByPartition(arr []int, L int, R int) {
	if L >= R {
		return
	}

	// L到R上进行partition 标记位为arr[R] 数组被分成  [   <=arr[R]   arr[R]    >arr[R]  ]，M为partition之后标记位处在的位置
	M := partition(arr, L, R)
	sortByPartition(arr, L, M-1)
	sortByPartition(arr, M+1, R)
}

func QuickSort2(arr []int) {
	if len(arr) < 2 {
		return
	}
	sortByNetherlandsFlag(arr, 0, len(arr)-1)
}

func sortByNetherlandsFlag(arr []int, L int, R int) {
	if L >= R {
		return
	}

	// 每次partition返回等于区域的范围,荷兰国旗问题
	equalArea := netherlandsFlag(arr, L, R)
	// 对等于区域左边的小于区域递归，partition
	sortByNetherlandsFlag(arr, L, equalArea[0]-1)
	// 对等于区域右边的大于区域递归，partition
	sortByNetherlandsFlag(arr, equalArea[1]+1, R)
}
```