快速排序
快速排序法介绍：
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两 部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排 序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
思路分析
快速排序的思路由上图所示：
首先是找到一个基准点，这个不一定非要是中位数，也可以是任意一位，可以自主分割，在什么位置都可以，这里我们以中位来学习
根据中位数为基准，将需要排序的数组分为两份，之后分别交换位置，保证比中位数小的都在左边，比中位数的都在右边，此时左右两边虽然无序，但是都保证一定规则
之后按照递归，再次将左边选出中位数，右边选出中位数，递归到不能交换为止
快速排序案例
要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序，要求使用快速排序法。【测试 8w 和 800w】 说明[验证分析]:
如果取消左右递归，结果是 -9 -567 0 23 78 70
如果取消右递归,结果是 -567 -9 0 23 78 70
如果取消左递归,结果是 -9 -567 0 23 70 78
public static void quickSort(int[] arr, int left, int right) { // left index int l = left; int r = right; // pivot 中轴值 int pivot = arr[(left + right) / 2]; //临时变量 int temp = 0; // while 循环的目的是比比中轴的pivot值小的放在左边 // 比pivot 值大的放在右边 while (l < r) { // 在pivot的左边一直寻找 找到大于等于pivot 的值才退出 while (arr[l] < pivot) { l += 1; } // 在pivot的右边一直寻找 找到小于等于pivot 的值才退出 while (arr[r] > pivot) { r -= 1; } // 如果 l>=r说明pivot的左右两个值已经按照左边全都是小于等于pivot，右边去哪不是大于等于pivot排列好了 if (l >= r) { break; } // 交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; // 如果交换玩发现这个arr[l]==pivot值 相等r--前移 if (arr[l] == pivot) { r -= 1; } //如果交换玩发现 arr[r] == pivot值 相等l++ 后移 if (arr[r] == pivot) { l += 1; } } // 如果l==r 必须是 l++ r-- 否则会出现栈溢出 if (l == r) { l += 1; r -= 1; } //向左递归 if (left < r) { quickSort(arr, left, r); } //向右递归 if (right > l) { quickSort(arr, l, right); } }
排序过程断点调试
int arr[] = {-9, 78, 0, 23, -567};
我们的测试数组是一个五位数的数组，
进入循环，此时我们看到，中位数和左右两边的索引，0和4
这里我们可以看第一组数据，
下标0 arr[l] =- 9, -9小于0于是 左边下标后移继续寻找，找到78，此时l = 1 是78对应的数组下标 此时的78 比中位 0 要大，进入右侧比对
显然 arr[r] = -567 比中位数小，不需要改变下标，跳出循环，
此时我们对比因为我们之后需要重复的递归，这里就是我们递归的跳出条件，如果左边大于右边了，代表左边已经没有大于中位数的数了，反之右边也一定没有小于中位数的
此时，交换两边不符合条件的数字，将比0大的七十八交换到右边吗，将比0小的-567交换到左边
交换完成之后，判断左右两边此时小标的数字是否与中位数相等，如果相等就后移，不需要重复比对
此时我们的第一次循环就结束了，可以看到，数组已经被交换到了，我们的思路第一步的样子，
比中位数0 小的都在左边，比中位数0大的都在右边，之后我们需要重复递归，一直到交换不了为止
此时 r 与l相等，就代表都到中位数了，左右两边都递归有序了，此时我们需要将l后一位，r前移一位，防止栈溢出，并且再继续向下，再最后一次递归之前会结束，
后面的递归就是重复的分组重复的交换，一直到左索引小于又索引，代表还可以继续分组排序，直到左边递归完毕
右索引大于左索引代表可以继续向右边递归，一直到右边递归完毕
快速排序测速
八十万长度存放0-80w的随机数
可以看到，效率是十分的快速
有兴趣的小伙伴可以自己试试写一个冒泡排序测试一下，再拿小冷的快速排序测试一下，算法的精妙之处一下就能感受到了
