一、在学快速排序之间我们必须先要学会递归

1.递归的本质就是方法调用方法本身，进而达到循环的目的

这个循环我们还可以这样去写

大家可以看到两种循环有什么区别，第一种是run()当中的for循环，执行了10次，第二种没有for循环我们让run方法执行了10次，结果是一样的，那么第二种就是我们的递归。

2.练习使用递归

经典的斐波那契数列，（我们这里不要画递归树，就讲我们这种方法）

递归出口：这里可以给同学们展示为什么要有递归出口

 /**
  *  斐波那契
  * @param n
  * @return
  */
public static int Fibonacci(int n){
     if(n == 1){
         return 1;
     }else if(n == 2){
        return 1;
    }else {
         return Fibonacci(n -1 ) + Fibonacci(n-2);
     }

}

经典题目 1 + 2 + 3 + 4 + ... + 100 = 5050 计算前n个数的和

 /**
  *   1  + 2 + 3 + 4  + ... + n
  * @param n
  */
public static int sum(int n){
    if(n == 1) {
        return 1;
    }else {
        return sum(n-1) + n;
    }
}

求一个数组当中数的和（讲这个有两个目的：第一给同学们知道数组和数据的区别，二是我们用数组的递归，其实本质上还是对我们这个数组操作，所以递归关系和递归出口上都有arr）

public static int sum(int[] arr,int n){
     if(n == 0){
         return arr[0];
     }else {
         return sum(arr,n-1) + arr[n];
     }
}

二、快速排序（将整个递归分为两步，第一步是基本算法，第二步是递归）

基本思想

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法描述

快速排序使用分治法来把一个串（名单）分为两个子串（子列表）具体算法描述如下：

1. 会把数组当中的一个数当成基准数
2. 一般会把数组中最左边的数当成基准数，然后丛两边进行检索。丛右边检索比基准数小的，

然后左边检索比基准数大的。如果检索到了，就停下，然后交换这两个元素，然后继续检索。

第一步是基本算法

动态图：（这里的数据是经过特殊处理的）

①:首先找到一个基准数 temp = 5

②：先移动右边的 指针 j ,找到第一个小于 5 的数 也就是 1

·· 然后在移动 执行 i ，找到第一个大于 5 的数 也就是 6

然后进行交换

③：i 和 j 一旦相遇,就停止检索 。 把基准数和相遇位置为树进行交换

④:第一次排序完毕，排序完成以后我们会发现排序的左边比基准数小，右边比基准数大

这里是我们第一次排序的代码

public class ThreadNew{
    public static void main(String[] args) {
        int[] arr = new int[] {5,6,3,2,7,1,8};
        quickSort(arr,0,arr.length -1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int arr[],int left,int right) {
       
        //定义变量保存基准数
        int base = arr[left];
        //定义变量 i 指向最左边
        int i = left;
        //定义变量 j 指向最右边
        int j = right;

        //当 i 和  j 不相遇的时候，再循环中进行解锁
        while (i != j) {
            //先由j 从 右向左检索比基准数小的，如果检索到比基准数小的就停下
            while (arr[j] >= base && i < j) {
                j--; //j从右往左移动
            }
            // i 从左向右检索
            while (arr[i] <= base && i < j) {
                i++; //i从右往左移动
            }
            //代码走到这里。i 和 j 都停下了，然后交换 i 和 j的位置元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        // 如果while循环条件不成立，这就代表了 i和 j相遇了，就停止检索
        //交换基准数和这个相遇位置的元素进行交换
        arr[left] = arr[i];
        //把基准数赋值给相遇位置的元素
        arr[i] = base;
    }
}

第二步递归

同学们我们可以看到是只能是第一轮排序，我们的顺序还是没有排好，但是我们也可以发现一个规律就是在基准数左边的数据比基本数小，右边的都比基准数大。如果我们把左右两边的数据都看成一个新的数组，那么这个新数组和原来的数据会经历同样的方式进行排序，那么这是用递归的最好的案例。

分析递归表达式和递归出口

从上一张图当中我么可以看出我们需要将整个数据根据我们原来的游标i或j分成左右两部分，那我们的递归关系是不是可以写成：（这个为什么是left和right不讲）

以上我们研究出来了递归关系，那么递归出口呢？（这个地方可以提问）

只有数据拆分到只有一个的情况我们才能说每个序列都是有序的

注意这个地方，所以我们可以用 ==

代码：

public class QuickSort {
	public static void main(String[] args) {
		int[] arr = new int[] {6,1,2,7,9,3,4,5,10,8};
		quickSort(arr,0,arr.length -1);
		System.out.println(Arrays.toString(arr));
	}
	
   /**
     *  定义方法，实现快速排序
     *                                  : f(arr ,right ,i-1)
     *  递归关系 ： f(arr, right ,left)
     *                                  : f(arr ,i+1 ,left)
     *   递归出口 ： right ＜ left
     * @param arr     数组
     * @param left
     * @param right
     */
	public static void quickSort(int arr[],int left,int right) {
		//进行判断 如果左边索引比右边的索引要大 是不合法的 直接使用 return 结束这个方法
           // 这个地发不写 == 是有原因的，因为会出现死循环
		if (left == right) {
			return ;
		}
		
		//定义变量保存基准数
		int base = arr[left];
		//定义变量 i 指向最左边
		int i = left;
		//定义变量 j 指向最右边
		int j = right;
		
		//当 i 和  j 不相遇的时候，再循环中进行解锁
		while (i != j) {
			//先由j 从 右向左检索比基准数小的，如果检索到比基准数小的就停下
			while (arr[j] >= base && i < j) {
				j--; //j从右往左移动
			}
			// i 从左向右检索
			while (arr[i] <= base && i < j) {
				i++; //i从右往左移动
			}
			//代码走到这里。i 和 j 都停下了，然后交换 i 和 j的位置元素
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		// 如果while循环条件不成立，这就代表了 i和 j相遇了，就停止检索
		//交换基准数和这个相遇位置的元素进行交换
		arr[left] = arr[i];
		//把基准数赋值给相遇位置的元素
		arr[i] = base;
		
		//交换完成之后基准数就归位了 左边的数字都比他小 右边的都比他大
		//下一步该排基准数的左边
		quickSort(arr, left, i - 1);
		//排右边
		quickSort(arr, i + 1, right);
	}
}