快排（拓展：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;
}