快速排序原理
对于一个数组，选择数组中一个随机元素x做划分，将<=x的放到x的左边，将>x的放到x的右边，此时x所在的位置一定是最后排完序后x的最终位置。然后我们对x左边的数组和右边的数组做同样的工作，最终得到一个有序数组。
快排原理
具体实现
划分方法
遍历该部分数组，若该数字<=x，将其交换到数组的左边，同时如果该数字==x，要记录下该数字被交换过后的下标，最后遍历完数组后，我们可以得到<=x的边界位置，此时将某一个=x的数放到边界位置处，就完成了一次划分，返回此次划分被确定最终位置元素的下标。
划分方法
public static int partition(int[] arr,int l,int r,int x){
int left=l; //用于记录<=x的边界
int i=l; // 用于遍历数组
int num=l; //用于记录==x元素的下标位置
while(i<=r){
if(arr[i]<=x){
swap(arr,left,i);
if(arr[left]==x) num=left;
left++;
}
i++;
}
//最后还要将=x的元素放到边界处
swap(arr,num,left-1);
return left-1;
}
快排递归
public static void quickSort(int[] arr,int l,int r){
if(l>=r) return;
int x=arr[l+(int)(Math.random()*(r-l+1))];// 在[l，r]范围随机取一个数
int mid=partition(arr,l,r,x);
quickSort(arr,l,mid-1);
quickSort(arr,mid+1,r);
}
快速排序的优化
当我们将上述code提交之后，大部分案例都能通过，但会有超时案例
超时状况
可以看到，该案例中包含了非常多相同的数，而上面的划分方法，每次调用都只能确定一个数的位置，因此可以进行优化。通过划分，使得<x的数在左边，==x的数在中间，>x的数在右边，这样每次划分可以确定所有==x的数的位置。
划分方法的优化
遍历该部分数组，将<x的元素交换到数组的左边，>x的元素交换到数组的右边，中间剩下的就是==x的元素。
划分的优化
这里分为了三种情况
1）<x的情况，a，i所指元素交换，交换之后，a就是<x的边界，此时再让i++，a++；
2）==x的情况，只用i++；
3）>x的情况，b，i所指元素交换，此时b就是>x的边界，此时再让b--，而i不变，因此此时并不知道交换过来的在i位置上的元素的大小，所以需要进行判断。
public static int first,last;
public static void partition2(int[] arr,int l,int r,int x){
first=l;
last=r;
int i=l;
while(i<=last){
if(arr[i]<x){
swap(arr,i,first);
i++;
first++;
}
else if(arr[i]==x) i++;
else {
swap(arr,i,last);
last--;
}
}
}
需要定义全局变量first和last辅助完成，partition2执行完成后，[first,last]区域就是==x的区域。
总方法
class Solution {
public static int first,last;
public int[] sortArray(int[] nums) {
quickSort2(nums,0,nums.length-1);
return nums;
}
public static void quickSort2(int[] arr,int l,int r){
if(l>=r) return;
int x=arr[l+(int)(Math.random()*(r-l+1))];
partition2(arr,l,r,x);
// 为了防止底层的递归过程覆盖全局变量
// 这里用临时变量记录first、last
int left=first;
int right=last;
quickSort2(arr,l,left-1);
quickSort2(arr,right+1,r);
}
public static void partition2(int[] arr,int l,int r,int x){
first=l;
last=r;
int i=l;
while(i<=last){
if(arr[i]<x){
swap(arr,i,first);
i++;
first++;
}
else if(arr[i]==x) i++;
else {
swap(arr,i,last);
last--;
}
}
}
// public static void quickSort(int[] arr,int l,int r){
// if(l>=r) return;
// int x=arr[l+(int)(Math.random()*(r-l+1))];
// int mid=partition(arr,l,r,x);
// quickSort(arr,l,mid-1);
// quickSort(arr,mid+1,r);
// }
// public static int partition(int[] arr,int l,int r,int x){
// int left=l;
// int i=l;
// int num=l;
// while(i<=r){
// if(arr[i]<=x){
// swap(arr,left,i);
// if(arr[left]==x) num=left;
// left++;
// }
// i++;
// }
// swap(arr,num,left-1);
// return left-1;
// }
public static void swap(int[] arr,int l,int r){
int temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
}
}
时间、空间复杂度
最坏情况下，数组原本有序，而每次我们又都选择了最大或者是最小的元素，每次都需遍历一遍划分后的部分数组，时间复杂度会达到O（n2）,空间复杂度会达到O（n）。
最坏情况
平均情况时间复杂度
平均情况空间复杂度
