求中点位置，一般来说mid = （L+R）*0.5,这样写有一些问题
如果数组长度比较大，L+R可能会溢出，这样算出来的mid是不对的。
所以可以这么写
mid = L + (R-L)*0.5 //下面为右移一位（等同于除2），等同于上面 mid = L + (R-L)》》1
如下图就是递归的底层调用，相当于栈、树的后序遍历
p(0,2)相当于在0到2范围内求最大值
p(3,5)相当于在3到范围内求最大值
p(0,5)要调用要先调用p(0,2),p(3,5)压入栈中，
同理，p(0,2)要先调用p(0,1)，p(2,2)压入栈中，即二分
p(0,1)要先调用p(0,0)，p(1,1)压入栈中
p(0,0)算完，返回给p(0,1)，左侧部分返回值有了，右侧还没有，继续让p(0,1)进栈，算p(1,1)，算完以后返回p(0,1)的值就有了
往上依次类推
public static int process(int[] arr, int L, int R)
{
//找出arr中最大值
if(L == R)
return arr[L];
int mid = L + ((L-R) >> 1);
int leftmax = process(arr, L,mid);
int rightmax = process(arr,mid + 1, R);
return Math.max(leftmax,rightmax);
}
归并排序(mergeSort)
上图2：外排序：两个指针比较东西，放到外面新数组里面，最后再拷贝回来，这就叫外排序。
排序次数没有浪费，所以才能O(N*logN)
用指针。
左边小，将左边的数放入辅助数组，leftpoint右移1位，右边小，将右边的数字放入辅助数组，rightpoint右移一位，相等默认放左边。一边的指针越界以后，剩下的数字直接放。
最后将辅助数组copy到源数组。
)
上图，左侧一个下标指向1，右侧一个下标指向2
最后将辅助数组copy到源数组，如下图
package class02;
impoort java.util.Arrays;
public class Code01_MergeSort
{
public static void mergeSort(int[] arr)
{
if(arr == null || arr.length < 2)
return;
mergeSort(arr,0,arr.length-1);
}
public static void mergeSort(int[] arr,int L, int R)
{
if(L == R)
return;
int mid = L + ((R-L) >> 1);
mergeSort(arr, L,mid);//递归，左边排好序
mergeSort(arr,mid+1.R);//递归，右边拍好序
merge(arr,L,mid,R);//整体排好序
}
public static void merge(int[] arr,int L,int mid,int R)
{
int[] help = new int[R-L+1];
int p1 = L;//指针p1记录左边排好序的部分
int p2 = mid+1;//指针p2记录右边排好序的部分
int i = 0;//i记录辅助数组
while(p1 <= mid && p2 <= R)
{
help[i ++] = arr[p1] < arr[p2]?arr[p1 ++]:arr[p2 ++;]
}
while(p1 <= mid)
{
help[i ++] = arr[p1 ++];
}
while(p2 <= R)
{
help[i ++] = arr[p2 ++];
}
for(int j = 0; j < help.length.j ++)
{
arr[L+j] = help[j];
}
}
}
//LeetCode，牛客上找逆序对问题来熟练一下。
上图逆序直接逆向思维，[1,3,4,2,5]，1右边比1大的数字有4个，4*1.3右边比3大的数有2个，所以2*3，同理4*1+3*2+4*1+2*1=16
面对左组右组相等情况一定要先拷贝右组。
mergesort必考
package class02;
import java.util.Arrays;
public class02 Code02_SmallSum
{
public static void smallSum(int[] arr)
{
if(arr == null || arr.length < 2)
return;
mergeSort(arr, 0, arr.length -1);
}
public static int mergeSort(int[] arr, int L, int R)
{
if(L == R) return 0;
int mid = L + ((R-L) >> 1);
mergeSort(arr,L,mid);//左边排好序且返回小和的数量
mergeSort(arr,mid+1,R);//右边排好序并且返回小和的数量
merge(arr,L,mid,R);//整体排好序并且merge时求小和数量
return mergeSort(arr,L,mid)+mergeSort(arr,mid+1,R)+merge(arr,L,mid,R)//p(0,1)递归为p(0,0)和p(1,1)，
//这时左右两边相等，l=r=mid=0返回的是0，p(0,1）接受到的是L=0，R =1，mid = 0，merge(arr,0,0,1)返回的值，小和数量
}
public static int merge(int[] arr, int L, int mid, int R)
{
int[] help = new int[R-L+1];
int p1 = 0; //指向左边排好序的指针
int p2 = mid + 1; //指向右边排好序的指针
int i = 0;//辅助数组指针
int res = 0;//记录小和乘以的个数，比如有3个比1大的数，那么最终
while(p1 <= mid && p2 <= R)
{
res += arr[p1] < arr[p2]?arr[p1]*(R-mid+1):0;//比1大的数有3个，arr[p1]代指1，R-mid+1代指3，最终结果需要二者相乘
help[i ++] = arr[p1] < arr[p2] ? arr[p1 ++]:arr[p2 ++]l//当左边数字等于右边数字时，要先copy右边数字
}
while(p1 <= mid)
{
help[i ++] = arr[p1 ++];
}
while(p2 <= R)
{
help[i ++] = arr[p2 ++];
}
for(int j = 0; j < help.length;j ++)
{
arr[L + j] = help[j];
}
return res;
}
}
快速排序（空间复杂度O（logN），最差情况下空间复杂度O(N)）
下图就是荷兰国旗问题思路，设置三个区间，分别是
package class02;
import java.util.Arrys;
public class Code05_NetherlandsFlag{
public static int[] partition(int[] arr,int L, int R, int p)
{
int less = L - 1;//小于区
int more = R + 1;//大于区
int i = L;//i指向数组数字，从第一个开始
while(i < more//i是当前指针指向的数，more是大于区边界
{
if(arr[i] < p)
swap(arr,++less,i ++);//将当前指针所指的数和小于区边界的下一个交换，然后扩展小于区
else if(arr[i] > p)
swap(arr,--more,i);//当前指针所指的数和大于区边界左边一个做交换，扩展大于区。由于这时候i所指的数字是交换过来的新数字，所以。i不用继续指向下一个数
else
i ++;
}
return new int[] {less +1, more -1};//等于区域的左右边界
}
}
下图快排2.0
快排3.0才能O(N*logN)
package class02;
import java.util.Arrays;
public class Code06_QuickSort
{
public static void quickSort(int[] arr)
{
if(arr == null || arr.length < 2)
return;
quickSort(arr,0,arr.length-1)
}
public static void quickSort(int[] arr, int l, int r)
{
if(l < r)
{
swap(arr,l+int(Math.random()*(r-l+1)),r);
int[] p = partiton(arr,l,r);//用荷兰国旗函数，分为三个区域，返回等于区域的左边界和右边界，必定是个长度为2的数组
quickSort(arr,l,p[0]-1);//小于区域有序，p[0]是等予区域左边界，p[0]-1是小于区域的右边界
quickSort(arr,p[0]+1,r);//大于区域有序
}
//这是一个处理arr[l..r]的函数
//默认以arr[r]作划分，arr[r] ->p ==p >p
//返回等于区域(左边界，右边界)，所以返回一个长度为2的数组res,res[0],res[1]
public static int[] partition(int[] arr,int l, int r);
{
int less = l -1;//小于区左边界
int more = r;//大于区右边界，此时右边界最后一个是我们随机选取的那个数字
while(l < r)
{
if(arr[l] < arr[r])
{
swap(arr,++less,l ++);
}
else if( arr[l] > arr[r])
swap(arr, --more,l);//l不++，因为此时l指向交换过来的新数据
else
l ++
}
swap(arr,more,r);//交换最右边的随机选出的值到等于区域
return new int[] {less+1,more};
}
}
}
