快速排序和初识递归
1. 递归
1.1 求数组最大值
利用递归的方法，求一个数组中的最大值，画出递归树可以看出，每次都在比较左右子树上的值。
public static int getMaxNumber( int[] arr, int l, int r) {
// base case
if(l==r){
return arr[l];
}
// 递归主体
int mid = l + ((r-l)>>1);//等效于(l+r)/2
int leftMax = getMaxNumber(arr, l, mid);
int righMax = getMaxNumber(arr, mid+1, r);
return Math.max(leftMax, righMax);
} 时间复杂度: O(N)
额外空间复杂度: O(logN)
1.2 Master公式求复杂度
对于上述这种分治思想的递归代码的时间复杂度，由Master公式可以求出。注意⚠️ 所有的子问题都是等规模的！T [n] = aT[n/b] + f (n)（直接记为T [n] = aT[n/b] + O(N^d)
其中
- n表示:整个问题的规模
- a: 递归中子问题的次数，比如上述问题中就是两次子问题，求左Max和右Max
- n/b: 每个子问题的size，也就是对整个数据的划分规模, 等分:N/2, N/2; 不等分:2/3N
- f(n)=O(N^d): 递归之外的工作量，包括对整个大问题的分割，合并子问题的答案
根据公式可以计算复杂度:
- 当 log(b,a) > d时，时间复杂度为O(N^log(b,a))
- 当 log(b,a) = d时，时间复杂度为O(N^d*logN)
- 当 log(b,a) < d时，时间复杂度为O(N^d)
以上述问题为例，分析求最大值的时间复杂度:
1) 对大问题的分割，也就是求中间值，和子问题的合并，也就是求最大值，都是O(1)的常数复杂度
2）划分成两个子过程T(N/2) 和 T(N/2)，因此 a=b=2 且 d=0
3) 命中第一个公式，T(N)=O(Nˆ(log(b,a)))=O(N)
2. 归并排序(Merge Sort)
参考资料Anwen同学的博客
归并排序的整体就是一个简单递归，核心思想是先让序列的左半部分有序，再让序列的右半部分有序，最后整体有序。让整体有序的过程用了外排序的思想，最后从两个子序列（左右两半）从头开始逐次比较，往辅助序列中填较小的数。
对归并排序的理解要从分治的思想理解，不可被其中的递归代入进去，越分析越复杂。
再用一个实际的例子去分析排序的过程，以序列{2,1,4,3}为例，归并排序的过程大致如下：
代码思路就是:P(L, R)想在(L, R)上有序，则执行下面三步
P(L, M)左半部分有序P(M, R)右半部分有序- 合并左，右
MergeProcess也叫左外排序过程，其思想就是准备一个长度一样的“额外空间”，且有p1,p2两个指针，谁小就copy谁到额外空间去，并移动一格
/*
@ 归并排序，递归版本
@ 思路就是，数据划分为左右两半，左有序再右有序，最后合并
@ 合并的过程就是:
@ 1. 准备一个额外的数组，长度是左右数组长度之和
@ 2. 准备两个指针，p1p2，谁小复制谁，并移动
@ 3. 跳出循环后，再把剩下的数组都复制到help数组中
@ 4. 最后把help数组中的数组，全部复制到原数组中，并返回
@
*/
public static void mergeSort(int[] arr) {
if(arr==null || arr.length ==1){
return;
}
process(arr, 0, arr.length-1);
}
public static void process( int[] arr, int l, int r) {
// base case
if(l==r) {
return;
}
// 主体
//int mid = l + ( (r-l)>>1 );
int mid = (r+l)/2;
process(arr, l, mid);
process(arr, mid+1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int mid, int r) {
// 准备一个额外的数组，长度是左右数组长度之和
int len = r-l+1;
int[] help = new int[len];
int i = 0;
// 准备两个指针，p1p2
int p1 = l;
int p2 = mid+1;
// 谁小复制谁，并移动
while( p1<=mid && p2<=r ){
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
}
// 也许p1后遍历完
while( p1<=mid ){
help[i++] = arr[p1++];
}
// 也许p2后遍历完
while( p2<=r ){
help[i++] = arr[p2++];
}
// 转移结果，特别注意，help从0开始，arr从l+i开始
for(i=0; i<len; i++){
arr[l+i] = help[i];
}
} 复杂度分析:
根据Master公式，可得T(n)=2T(n/2)+O(n)，第一个2的含义是子过程（对子序列进行归并排序）要执行两次，第二个2的含义是子过程样本量占一半（因为分成了左右两半部分），最后O(n)表示左右有序之后进行的并入操作为O(n+n)=O(n)(L、R指针移动次数总和为n，将辅助数组覆盖源数组为n)，符合T(n)=aT(n/b)+O(n^d)，经计算该算法的时间复杂度为O(nlogn)。额外空间复杂度是O(n)。
为什么归并排序快？
每次合并之前，都在排序，没有浪费。
3. 快速排序
QuickSort1.0
问题描述:
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。要求额外空间复杂度是O(1)，就是说不能申请额外的数组，只能原地操作(Inplace操作)。
Given [3 7 6 2 0 5 3 4], 划分值num=4
结果分成[3 2 0 4 3 | 7 6 5]，不需要排序仅分成两部分
解题方法:
设置一个有效区在最左侧，初始长度设为(-1)
1). 当前数<=划分值，交换[当前数] 与 [<=区的下一个数], <=区往右扩一个位置，当前数跳下一个。
2). 当前数>划分值，<=区不扩，当前数跳下一个。
观察发现，划分过程就是推着>区前进。
QuickSort2.0
问题描述:
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放
在数组的中间，大于num的数放在数组的 右边。要求额外空间复杂度O(1)，时间复杂度O(N)
这次是划分成三个部分，就需要在开始规定两个区域。解题思路:
1). 当前数<区分值，交换[当前数] 与 [<区的下一个数], <区往右扩一个位置，当前数跳下一个。
2). 当前数==划分值，当前数直接跳下一个。
3). 当前数>划分值，交换[当前数] 与 [>区的下一个数], >区往左扩一个位置，当前数不动！
分析整个过程我们可以发现：
代码分析:
特别注意:
情况3中，当前数>划分值时，对当前值的处理是不动！
QuickSort3.0
由2.0得到启发，借助分治的思想，在第一次partion后，再在等于区的左右两侧继续partion，最后达到整体有序的效果。由于2.0中会存在时间复杂度高的问题，3.0中的改进就是:
- 在数组范围中，等概率随机选一个数作为划分值，然后把数组通过荷兰国旗问题分成三个部分:
左侧<划分值、中间==划分值、右侧>划分值 - 对左侧范围和右侧范围，递归执行
- 时间复杂度为O(N*logN)
// 交换数组中的两个数
public static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 改进的快排，也就是最终版本，是在数组范围中随机等概率选取一个数作为划分值
public static void quickSort(int[] arr){
if (arr == null || arr.length < 2){
return;
}
quickSortProcess(arr, 0, arr.length-1);
}
// 快排主体
public static void quickSortProcess(int[] arr, int l, int r){
// base case: 当 l >= r 自动退出
if (l < r){
// 把在 [l,r] 上随机选取的划分值与最右侧的交换，把它放到最右侧上
swap(arr, l + (int)( Math.random() * (r - l + 1) ), r);
// 在[l,r]上执行partition
int[] p = partition(arr, l, r);
// 在小于区 和 大于区分别递归执行
quickSortProcess(arr, l, p[0]-1);
quickSortProcess(arr, p[1]+1, r);
}
}
// 快排3.0中的partition，实际是在[l, r-1]上partition，arr[r]是我们的划分值，暂时不动
// 划分结束后，再把arr[r]与>区的边界交换，最后得到的等于区边界是[less+1, more]
public static int[] partition(int[] arr, int l, int r){
// <区的初始边界
int less = l - 1;
// >区的初始边界就在r, arr[r]是"固定的"作为比较值
int more = r;
// 当前值
int index = l;
while(index < more){
if (arr[index] < arr[r]){
swap(arr, ++less, index++);
}else if(arr[index] > arr[r]){
swap(arr, --more, index);
}else {
index++;
}
}
// 处理下，固定在arr[r]的划分值
swap(arr, index, r);
return new int[] { less + 1, more };
} 针对上述代码特别注意的是:
- 实际是在
[L, R-1]上做partion，是因为以arr[R]作为划分值，less=L-1,more=R - 在处理过程中，当前数
>划分值时，对交换后的当前值的处理是不动！因为这个数还没有判断处理。而当前数<划分值时，对交换后的当前值的处理是加1，因为交换后的当前值是等于区的数，要处理下一个当前值，整个模式是推着等于区前进的 - 返回的数组是
{less+1, more}，因为arr[R]作为划分值在最后没处理，要和more交换下，这样more恰好就是等于区的数。 partition的最后一步是，交换more和数组的最后一个值。- 终止条件是当前值下标和
more重合。
4.二叉树与排序
参考公众号labuladong
快速排序就是个二叉树的前序遍历，归并排序就是个二叉树的后续遍历。
4.1 快排和二叉树
为什么快速排序和归并排序能和二叉树扯上关系？我们来简单分析一下他们的算法思想和代码框架：
快速排序的逻辑是，若要对nums[lo..hi]进行排序，我们先找一个分界点p，通过交换元素使得nums[lo..p-1]都小于等于nums[p]，且nums[p+1..hi]都大于nums[p]，然后递归地去nums[lo..p-1]和nums[p+1..hi]中寻找新的分界点，最后整个数组就被排序了。
快速排序的代码框架如下：
void sort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p，先执行根
int p = partition(nums, lo, hi);
/************************/
// 左
sort(nums, lo, p - 1);
// 右
sort(nums, p + 1, hi);
} 先构造分界点，然后去左右子数组上执行递归体(名字是排序)，实际是再去构造分界点，这就是一个二叉树的前序遍历！
4.2 归并和二叉树
归并排序的逻辑是，若要对nums[lo..hi]进行排序，我们首先二分，对nums[lo..mid]排序，再对nums[mid+1..hi]排序，最后把这两个有序的子数组合并，整个数组就排好序了。
归并排序的代码框架如下：
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
// 左
sort(nums, lo, mid);
// 右
sort(nums, mid + 1, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
// 根，最后在合并执行
merge(nums, lo, mid, hi);
/************************/
} 先对左右子数组排序（执行递归体），然后合并（类似合并有序链表的逻辑），这就是二叉树的后序遍历框架，也是大名鼎鼎的分治算法！
网易公司福利 152人发布