快速排序（二叉树的前序递归遍历思想）
思路
之前我们从选择排序，到选择排序的稳定性优化，到冒泡排序，到插入排序，到插入排序的提前截止时间，到希尔排序，虽然逐步一直都在优化，但是时间复杂度还是N得平方，力扣提交的结果一直都是时间超时，因为时间复杂度并没有发生量级级别的减少，都是通过常规的优化思维，说白一点，就是没有创新的优化点，都是一步一步，一点一点优化，想方设法能能提高一点效率就提高一点。
那么从快速排序就是要开始坐飞机了往前冲了，直接打破一个量级的时间复杂度，从N的平方，到Nlogn，N就是二叉树的深度，logn就是每一层的时间复杂度。
为什么说快速排序是结合了二叉树前序递归思想的排序，后面我把快速排序的代码写出来吗，你对比一下二叉树的前序遍历，结构基本都是差不多的。
快速排序的解题思路就是：一般默认选择第一个数组元素作为起点，将第一个元素处理一下，使得左边的元素都小于它，右边的元素都大于它。第二就开最左右的数组继续处理，左边的数据选择当前第一个元素再左边找到位置是的左边都小于它，右边的都大于它，右边同理。你看这不就是二叉树的前序递归遍历吗？
接下来直接看代码，如果说你明白了在快排中使用到了二叉树的前序遍历思想，那你成功的解决了50的问题，剩下的50%是看你嫩不能解决数组中的一个点，如何找到它所在的位置，并且交换好数据吗，这个还需要主要的是一个数组的边界问题（如果数组题好好刷了，知道数组边界的处理，不混乱），那第二个难点也就不是什么难点，我还是讲一下找到中间位置的函数的思路吧，但是边界为就不讲了，这块儿还是有点技巧的，回头再来刷这个题目的时候再看吧
代码
class Solution {
public int[] sortArray(int[] nums) {
sort(nums,0,nums.length-1);
return nums;
}
//定义一个递归遍历的函数sort
void sort(int[] nums,int lo,int hi){
if(lo > hi){
return;
}
int p = partition(nums, lo, hi);
sort(nums,lo,p-1);
sort(nums,p+1,hi);
}
//定义一个找到位置的partition函数
int partition(int[] nums, int lo, int hi){
int pivot = nums[lo];
// 关于区间的边界控制需格外小心，稍有不慎就会出错
// 我这里把 i, j 定义为开区间，同时定义：
// [lo, i) <= pivot；(j, hi] > pivot
// 之后都要正确维护这个边界区间的定义
int i = lo + 1, j = hi;
// 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
while (i <= j) {
while (i < hi && nums[i] <= pivot) {
i++;
// 此 while 结束时恰好 nums[i] > pivot
}
while (j > lo && nums[j] > pivot) {
j--;
// 此 while 结束时恰好 nums[j] <= pivot
}
if (i >= j) {
break;
}
// 此时 [lo, i) <= pivot && (j, hi] > pivot
// 交换 nums[j] 和 nums[i]
swap(nums, i, j);
// 此时 [lo, i] <= pivot && [j, hi] > pivot
}
// 最后将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
swap(nums, lo, j);
return j;
}
// 原地交换数组中的两个元素
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
这个运行后还是超出运行限制，到底是哪里还可以继续优化呢，肯定是可以的，我们先不纠结了，能和面试官谈到这里，说不定他还没有懂得深的。差不多了，优化的点我先提一下，就是在上面的基础上加了一个洗牌算法
直接看代码：
class Solution {
public int[] sortArray(int[] nums) {
// 为了避免出现耗时的极端情况，先随机打乱
shuffle(nums);
sort(nums,0,nums.length-1);
return nums;
}
//定义一个递归遍历的函数sort
void sort(int[] nums,int lo,int hi){
if(lo > hi){
return;
}
int p = partition(nums, lo, hi);
sort(nums,lo,p-1);
sort(nums,p+1,hi);
}
//定义一个找到位置的partition函数
int partition(int[] nums, int lo, int hi){
int pivot = nums[lo];
// 关于区间的边界控制需格外小心，稍有不慎就会出错
// 我这里把 i, j 定义为开区间，同时定义：
// [lo, i) <= pivot；(j, hi] > pivot
// 之后都要正确维护这个边界区间的定义
int i = lo + 1, j = hi;
// 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
while (i <= j) {
while (i < hi && nums[i] <= pivot) {
i++;
// 此 while 结束时恰好 nums[i] > pivot
}
while (j > lo && nums[j] > pivot) {
j--;
// 此 while 结束时恰好 nums[j] <= pivot
}
if (i >= j) {
break;
}
// 此时 [lo, i) <= pivot && (j, hi] > pivot
// 交换 nums[j] 和 nums[i]
swap(nums, i, j);
// 此时 [lo, i] <= pivot && [j, hi] > pivot
}
// 最后将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
swap(nums, lo, j);
return j;
}
// 原地交换数组中的两个元素
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 洗牌算法，将输入的数组随机打乱
private static void shuffle(int[] nums) {
Random rand = new Random();
int n = nums.length;
for (int i = 0 ; i < n; i++) {
// 生成 [i, n - 1] 的随机数
int r = i + rand.nextInt(n - i);
swap(nums, i, r);
}
}
}
加上洗牌算法果然就通过了
接下来就继续分析一下，为什么加了一个洗牌算法就能提交通过呢，这里面到底优化什么？
明天继续~