什么是递归：方法调用其本身。
public void run(){
run();
}
*仅仅这样会造成栈溢出.
递归问题：
例 1
1 2 3 4 5 6 7. . .n 求第n个数?
1,递归关系表达式：f(n)=f(n-1)+1
2,递归出口：f(1)=1
public int run（int n）{
if（n==1）{
return 1;
}
return run(n-1)+1
}
例2.
1 1 2 3 5 8 13 21 ... n
求 n？
f(n)=f(n-1)+f(n-2)
......
f(2)=1;
f(1)=1;
递归表达式：f(n)=f(n-1)+f(n-2)
出口：f(2)=1;
f(1)=1;
public in run(int n){
if(n==1){
return 1;
}elseif(n==2)
{
return 1;
}
return run(n-1)+run(n-2);
}
例3
1+2+3+4+5+6+7 ....n
前 n 项的和？
递归表达式：f(n)=f(n-1)+n
出口：f(1)=1;
public void run(int n){
if(n==1){
return 1;
}
return run(n-1)+n
}
快排
找到第一个数为基准数（绿色）
再定义两个游标，
后边的 j 指针先走，去找比当前基准数小的数值，找到后停止
前边的 i 指针后走，去找比当前基准数大的数值，找到后停止。
两者指向的数值 进行互换，找到之后，继续执行上边的两步，直到两者相遇
相遇的位置和基准数互换
一轮后 基准数就到它准确位置了，
看不懂可以自己画图看看 ，时间复杂度 O(n)
然后重复操作，怎么重复呢？接着看
基准数已到它自己正确的位置，然后已它为分界点，分成左右两部分
然后这两部分就分别重复上边的操作，定义第一个为基准点，两个指针走，相遇交换，基准点到正确位置，然后再分解。
这样重复的逻辑是不是可以用递归了。递归结束就是 i j 最后相遇即结束
public static void main(String[] args) {
int[] arr= {5,6,1,2,7,4,3,9,8};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right) {
if(left>=right) {
return;
}
//定好基准数 就是数组中第一个数
int base=arr[left];
//定义出i和j
int i=left;
int j=right;
while (i!=j) {
//先执行j，从后向前找比基准数小的数据
while(arr[j]>=base && i
