快排（拓展：partition、荷兰国旗问题）
6.快速排序(量大时特快,不稳定,对基础类型 随机快排最常用)
快排的几种写法:
(基本快排,随机快排,优化随机快排,双轴快排)
时空分析:
平均时间复杂度:n*logn ;空间复杂度logN （因为要记录断点【放在数组的位置】，用数组记录相等的范围）
如果不用随机快排,最坏时间复杂度为N*2,随机快排最坏为nlogN
简单快排：
选第一个数字作为基准，分两个区
核心代码:
public static void qucikSort1(int[] A, int L, int R){
if(L < R){
int pivot = A[L];//最左边的元素作为中轴元素
int i = L;//初始化时小于等于pivot的部分，元素个数为0
int j = L+1; //大于pivot的部分，元素个数也为0
while(j <= R){
if(A[j] <= pivot){
swap(A, ++i, j++);
}else{
j++;//大于pivot的元素增加一个
}
}
//A[i]及A[i]以前的都小于等于pivot
//循环结束后A[i+1]及它以后的都大于pivot
//所以交换A[L]和A[i],这样我们就将中轴元素放到了适当的位置
swap(A, L, i);
qucikSort1(A, L, i-1);
qucikSort1(A, i+1, R);
}
} 优化随机快排:
1.范围内随机选一个数字做基准,小于它的放左边,大于它的放右边,等于它的放小于区右边;
2.利用小于区推动着等于区向大于区靠拢;同时大于区也会扩大.
2.当等于区与大于区相遇时,遍历完整个数组,将原数组分成了三个区域:小于区,等于区,大于区
3.对小于区和大于区再使用快排
其中partition的过程很重要,将数组分为三个区域.对应荷兰国旗问题.
public static void qucikSort(int [] a){
qucikSort(a,0,a.length-1);
}
public static void qucikSort(int [] a,int left,int right){
if(left<right){
swap(a, left + (int) (Math.random() * (right - left)), right);
int[] p = partition(a, left, right);
qucikSort(a, left, p[0] - 1);
qucikSort(a, p[1] + 1, right);
}
}
public static int[] partition(int [] a,int l,int r){
int less=l-1;//为l-1,因为小于区初始需要为0个
int more=r;//为r,因为最后要换
while(l<more){
if(a[l]<a[r]){
swap(a,l++,++less);//交换小于基准数时,小于区,等于区指针同时后移
}else if(a[l]>a[r]){
swap(a,l,--more);//交换大于基准数时,大于区扩大,指针左移
}else {
l++;//相等时,等于区指针后移
}
}
swap(a,more,r);//最后将基准数与等于区最后一个元素替换
return new int[]{less+1,more};//返回等于区的起始坐标和结束坐标
}
static void swap(int[] a,int i,int j){//快排的交换不能用位运算,因为小于区扩大时,可能涉及到自己与自己交换,位运算会将数交换成0
int temp=a[i];
a[i]=a[j];
a[j]=temp;
} 快排的拓展(partition)
问题一:(分两个区)
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
public static void partition(int[] a,int num) {
int R = a.length - 1;
int less = 0;
int more = 1;
while (more <= R) {
if (a[more] <= num) {
swap(a, ++less, more++);
} else {
more++;
}
}
}
static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
} 问题二（荷兰国旗问题）:（分三个区）
给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)
public static void partition(int[] a,int num) {
int more = a.length;
int less = -1;
int mid = 0;
while (mid < more) {
if (a[mid] < num) {
swap(a, ++less, mid++);
} else if(a[mid]>num){
swap(a,--more,mid);
}else{
mid++;
}
}
}
static void swap(int[] a, int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
} 