快速排序与荷兰国旗及Partition问题

需求:

1、Partition过程

给定一个数组arr，和一个整数num。请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)

2、荷兰国旗问题

给定一个数组arr，和一个整数num。请把小于num的数放在数组的左边，等于num的数放在中间，大于num的数放在数组的右边。

要求额外空间复杂度O(1)，时间复杂度O(N)

3、快速排序

思路:

1、Partition过程:

在原数组左边设置一个边界(left - 1),当index指向的数值比给定的值num小或等于时,

将这个数与边界右边的数交换,然后边界右移,

当index指向的数值比num大时,index右移动,边界

2、荷兰国旗问题(NetherLandsFlag):

在原数组左边设置一个左边界(left - 1),右边设置一个右边界(right+1),当index指向的数值比给定的值num小时,

将这个数与左边界右边的第一个数交换,然后左边界右移,index左移,当index指向的数值比num大时,将这个数与右边界左边的第一个数交换,然后i右边界左移,index不动,当index指向的数值与num相等时,边界均不动,index左移.

3、快速排序1.0:

用arr[R]对该范围做partition，小于等于 arr[R]的数在左部分并且保证arr[R]最后来到左部分的最后一个位置，记为M； 大于 arr[R]的数在右部分(arr[M+1..R]）

2）对arr[L..M-1]进行快速排序(递归)

3）对arr[M+1..R]进行快速排序(递归)

因为每一次partition都会搞定一个数的位置且不会再变动，所以排序能完成.

4、快速排序2.0:

在arr[L..R]范围上，进行快速排序的过程：

1）用arr[R]对该范围做NetherLandsFlag，小于 arr[R]的数在左部分，等于arr[R]的数中间大于arr[R]的数在右部分。假设等于arr[R]的数所在范围是[a,b]

2）对arr[L..a-1]进行快速排序(递归)

3）对arr[b+1..R]进行快速排序(递归)

因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成

5、快速排序3.0(随机快排+荷兰国旗技巧优化):

在arr[L..R]范围上，进行快速排序的过程：

1）在这个范围上，随机选一个数记为num，

1）用num对该范围做NetherLandsFlag，小于num的数在左部分，等于num的数中间，大于num的数在右部分。假设== num的数所在范围是[a,b]

2）对arr[L..a-1]进行快速排序(递归)

3）对arr[b+1..R]进行快速排序(递归)

因为每一次partition都会搞定一批数的位置且不会再变动，所以排序能完成

代码实现:

1、Partition过程:

//Partition

public static int quickSortPartition(int [] arr,int left,int right){

    if (arr == null || arr.length < 2){

        return -1;

    }

    if (left > right) {

        return -1;

    }

    if (left == right) {

        return right;

    }

    int lessEqual =  left - 1;

    int index = left;

    while(index < right){

        if (arr[index] <= arr[right]){

            swap(arr,index,++lessEqual);

        }

        index++;

    }

    swap(arr,right,++lessEqual);

    return lessEqual;

}

2、荷兰国旗问题(NetherLandsFlag):

public static int [] netherlandsFlag(int [] arr,int left,int right){

    if (left > right){

        return new int [] {-1,-1};

    }

    if (left == right){

        return new int [] {left,right};

    }

    int Value = arr[right];

    int lessEqual =  left  - 1;

    int moreEqual =  right + 1;

    int index = left;

    while(index < moreEqual){

        if (arr[index] < Value){

            swap(arr,index,++lessEqual);

        }

        if (arr[index] > Value){

            swap(arr,index,--moreEqual);

            index--;

        }

        index++;

    }

    return new int [] {lessEqual,moreEqual};

}

3、快速排序

//quickSort1.0

    public static void quickSort01(int [] arr){

        if (arr == null || arr.length < 2){

            return;

        }

        process01(arr,0,arr.length-1);

    }

    public static void process01(int [] arr, int left ,int right){

        if (left >= right){

            return;

        }

        int mid = quickSortPartition(arr,left,right);

        process01(arr,left,mid-1);

        process01(arr,mid+1,right);

    }

//quickSort2.0

// 主要是会有两个边界,没有浪费每次对比的信息

    public static void quickSort02(int [] arr){

        if (arr == null || arr.length < 2){

            return;

        }

        process02(arr, 0 ,arr.length-1);

    }

    public static void process02(int [] arr, int left ,int right){

        if(left >= right){

            return;

        }

        int[] bound = netherlandsFlag(arr, left, right);

        process02(arr,left,bound[0]);

        process02(arr,bound[1],right);

    }

//quickSort3.0

    public static void quickSort3(int[] arr) {

        if (arr == null || arr.length < 2) {

            return;

        }

        process3(arr, 0, arr.length - 1);

    }	

    public static void process3(int[] arr, int L, int R) {

        if (L >= R) {

            return;

        }

        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);

        int[] equalArea = netherlandsFlag(arr, L, R);

        process1(arr, L, equalArea[0] - 1);

        process1(arr, equalArea[1] + 1, R);

    }

快速排序与荷兰国旗及Partition问题的相关教程结束。