【左神3】归并排序与随机快排

【左神3】归并排序与随机快排

归并什么意思？

递归+合并 = 归并

归并排序的思想

每次都把数从中间一分为二，直到不能分了为止，然后从下往上，先排序后合并。

非归并排序的思想

原始n个数，第一层先让相邻的2个数排序，第二层让相邻的4个数排序，假设相邻数的个数为x，每加一层x以2倍增长，当相邻的x大于2n就排序完成了。

归并排序的时间复杂度

带入master公式。
(N) = 2T(N/2) + O(N) => O(N*logN)

非归并排序的时间复杂度

以最坏的打算来算，假设每一层左边都大于右边，那么每一层的复杂度都是O（n），每一层合并几次呢？O(logN),所以也是(N*logN)

经典面试题 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

最简单粗暴的做法（我能想到的算法）
就是写一个for循环，没个数都和他前面的数比一下，因此复杂度我想应该是O(n*n)。

如果是利用归并排序的思想呢。我要找我比谁小是不是等于找比我大的数？如上这个题是不是相当与找到一个数右边有几个比他大的数？比如1, 3, 4, 2, 5这五个数，1比3，4，2，5都小，那是不是说1这个数有4个数比他大，以此类推。

从最底下开始看啊，

1. 最下面：2和5比，2比5小，记2一次，2、5变成有序的2、5
2. 向上走一层：1和3比，1比3小，记1一次，1、3变成有序的1、3。425比，4比5小，记4一次，2比5小，记2一次，4、2、5变成有序的2、4、5。
3. 向上走一层，此时变成了13和245比，记住是左边和右边比，因为1和3已经比过了，所以1和2开始比，1比2小，由于245是有序的所以1肯定也比45小，所以1记3次，接着3和245比，3比4小一定比5小，因此3记2次。

把上面的都提取出来 记2一次，记1一次，记4一次记，2一次，1记3次，3记2次

2*1+1*1+4*1+3*1+3*2 = 2+1+4+3+6 = 16

是不是和上面的16相等，那你这么作好在哪呢？由于归并排序的复杂度是O(N*logN)，所以费半天劲就这些提升。

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

Partion过程 和 荷兰国旗过程

partion与荷兰国旗的区别在于，partion会分成2个区域，<=和>,荷兰国旗会分成3个区域，<,=,>。我猜是因为荷兰国旗是三个颜色。
不管是荷兰国旗还是partion核心思想都是在一个数组里找这个数应该存放的位置，在所有数都不相等的情况下有几个数找几次。

    // partion问题
	//小于等于arr[R]方左侧
	//把左侧边界右边第一个为止和R交换
	public static int partition(int[] arr, int L, int R) {
		if (L > R) {
			return -1;
		}
		if (L == R) {
			return L;
		}
		int lessEqual = L - 1;
		int index = L;
		while (index < R) {
			if (arr[index] <= arr[R]) {
				swap(arr, index, ++lessEqual);
			}
			index++;
		}
		swap(arr, ++lessEqual, R);
		return lessEqual;

从代码中就可以看出就一个判断<=，因此说明parttion是把数组分成了两部分。

//  arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
	//  小于arr[R]放左侧  等于arr[R]放中间  大于arr[R]放右边
	//  返回中间区域的左右边界
	public static int[] netherlandsFlag(int[] arr, int L, int R) {
	    // 不存在荷兰国旗问题
		if (L > R) {
			return new int[] { -1, -1 };
		}
		// 已经都是等于区域，由于用R做划分返回R位置
		if (L == R) {
			return new int[] { L, R };
		}
		int less = L - 1; // < 区 右边界
		int more = R;     // > 区 左边界
		int index = L;
		while (index < more) {
		    // 当前值等于右边界，不做处理，index++
			if (arr[index] == arr[R]) {
				index++;
			// 小于交换当前值和左边界的值
			} else if (arr[index] < arr[R]) {
				swap(arr, index++, ++less);
			// 大于右边界的值
			} else {
				swap(arr, index, --more);
			}
		}
		// 比较完之后，把R位置的数，调整到等于区域的右边，至此大于区域才是真正意义上的大于区域
		swap(arr, more, R);
		return new int[] { less + 1, more };

反之荷兰国旗问题一看就能看出来有三个判断。

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

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[i]当前位置的数==num， i++直接跳下一个
2. 如果arr[i]当前位置的数< num，当前位置的数arr[i]和小于区域的右一个交换，小于区域右扩一个位置，当前位置i++
3. 如果arr[i]当前位置的数> num，当前位置的数arr[i]与大于区域的左边一个交换，大于区域左移一个位置，i停在原地不做处理，这里不做处理是因为当前位置的数是刚从大于区域交换过来的数，还没做比较
   4.i和大于区域的边界相遇，停止操作

上图偷了懒，只画到一半。

快排

快排1.0版本

思路：核心就是给数组递归做partion过程。
下面分析一下第一次partion过程。用选定数组最右侧的位置上的数作为num，小于num的放在该数组的左边，大于num的放在该数组的右边。完成之后，把该数组最右侧的数组num，交换到大于num区域的第一个位置，确保了交换后的num是小于等于区域的最后一个数。
把该num左侧和右侧的数分别进行同样的partion操作(递归)。相当于每次partion搞定一个数的位置，代码实现快排1.0版本

上图是一次partion过程，只是找到了2应该在的地方，但是从上图中发现一个问题就是2左边的区间还有一个2，2等于2，如果左侧的2不用在做一次partion过程了是不是就完美了，就引入荷兰国旗问题，因为荷兰国旗过程能够返回等于2的范围。

public static void quickSort1(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process1(arr, 0, arr.length - 1);
	}
 
	public static void process1(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		// L..R上partition 标记位为arr[R] 数组被分成  [   <=arr[R]   arr[R]    >arr[R]  ]，M为partion之后标记位处在的位置
		int M = partition(arr, L, R);
		process1(arr, L, M - 1);
		process1(arr, M + 1, R);
	}

快排2.0版本

引入荷兰国旗思想，把小于num的数放左边，等于放中间，大于放右边。递归时把小于num的区域和大于num的区域做递归，等于num的区域不做处理。相当于每次搞定一批数（等于num的数），与标记为相等的数。实现快排2.0版本。

public static void quickSort2(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		process2(arr, 0, arr.length - 1);
	}
 
	public static void process2(int[] arr, int L, int R) {
		if (L >= R) {
			return;
		}
		// 每次partion返回等于区域的范围
		int[] equalArea = netherlandsFlag(arr, L, R);
		// 对等于区域左边的小于区域递归，partion
		process2(arr, L, equalArea[0] - 1);
	    // 对等于区域右边的大于区域递归，partion
		process2(arr, equalArea[1] + 1, R);
	}

上面说过《不管是荷兰国旗还是partion核心思想都是在一个数组里找这个数应该存放的位置，在所有数都不相等的情况下有几个数找几次》，所以，假设12345五个数，每个数都不相等，那么每个数都是在找自己应该时间复杂度都是O(N^2)，

因此引入了快排3.0版本

快排3.0版本

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

怎么理解这个复杂度呢？这个复杂度是经过数学推导出来的，死记硬背一下吧。我理解就是取了一个最好的情况正好i在中间，根据master公式推出来是O(N*logN)。