原创

快速排序（Java版）

更新时间   2020-10-08   17:52:06
953


快速排序

荷兰国旗问题

问题一

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

代码实现：

/**
 * Author Zq Created By 2020/10/6 21:38
 *
 * @version 1.0
 * @Description 问题一
 *
 * 给定一个数组arr，和一个数num，
 * 请把小于等于num的数放在数组的左边，
 * 大于num的数放在数组的右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)。
 */
public class Solution1 {

    public static void partition(int[] arr, int target){
        int small = -1;
        for (int i = 0 ; i < arr.length ; i ++ ){
            if(arr[i] <= target){
                //++small;
                //if(small != i)
                //    swap(arr,small,i);
                swap(arr,++small,i);
            }
        }
    }

    private static void swap(int[] arr, int i, int j){
        //注：使用异或运算有一个问题，当和自身交换时，交换后为0
        //只适用于待交换数据不是同一个数的情况
        //arr[i] = arr[i] ^ arr[j];
        //arr[j] = arr[i] ^ arr[j];
        //arr[i] = arr[i] ^ arr[j];
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        int[] arr = new int[]{4,3,2,9,7,0,2,8,1};
        solution1.partition(arr,4);
        for (int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
        }
    }

}

运行结果：

4 3 2 0 2 1 7 8 9

问题二

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

代码实现：

/**
 * Author Zq Created By 2020/10/6 21:38
 *
 * @version 1.0
 * @Description 荷兰国旗问题
 *
 * 给定一个数组arr，和一个数num，
 * 请把小于num的数放在数组的左边，
 * 等于num的数放在数组的中间，
 * 大于num的数放在数组的右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)。
 */
public class Solution2 {

    //在arr[L...R]范围上，根据p分块，<p 在左边，==p在中间，>p在右边
    public static void partition(int[] arr, int l, int r, int p){
        int less = l - 1;
        int more = r + 1;
        int index = l;
        while(index < more){
            if(arr[index] > p){
                swap(arr,--more,index);
            }else if(arr[index] < p){
                swap(arr,++less,index++);
            }else {
                index++;
            }
        }
    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] arr = new int[]{3,5,5,4,6,7};
        int p = 5;
        solution2.partition(arr,0,arr.length - 1,p);
        for (int i = 0; i < arr.length ; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

运行结果：

3 4 5 5 7 6

一、不改进的快速排序1.0

  1. 把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题划分成三个部分；

左侧 <= 划分值、 中间 == 划分值、 右侧 > 划分值

  1. 对左侧范围和右侧范围，递归执行

分析

  1. 划分值越靠近两侧，复杂度越高；划分值越靠近中间，复杂度越低

  2. 可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2)

代码实现：

/**
 * Author Zq Created By 2020/10/7 21:31
 *
 * @version 1.0
 * @Description 不改进的快速排序
 *
 * 1) 把数组范围中的最后一个数作为划分值，然后把数组通过荷兰国旗问题划分成三个部分；
 *    左侧 <= 划分值、 中间 == 划分值、 右侧 > 划分值
 * 2) 对左侧范围和右侧范围，递归执行
 *
 * 分析
 * 1) 划分值越靠近两侧，复杂度越高；划分值越靠近中间，复杂度越低
 * 2) 可以轻而易举的举出最差的例子，所以不改进的快速排序时间复杂度为O(N^2)
 *
 */
public class MyQuickSort {

    public static void quickSort(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr,0,arr.length - 1);
    }

    private static void process(int[] arr, int l, int r){
        if(l >= r)
            return;
        int index = partition(arr,l,r);
        process(arr,l,index - 1);
        process(arr,index + 1, r);
    }

    private static int partition(int[] arr, int l, int r){
        int less = l - 1;
        for (int i = l; i < r; i++) {
            if(arr[i] <= arr[r]){
                swap(arr,++less,i);
            }
        }
        swap(arr,++less,r);
        return less;
    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static boolean isSorted(int[] arr){
        int len = arr.length - 1;
        for (int i = 0 ; i < len; i ++ ){
            if(arr[i] > arr[i + 1])
                return false;
        }
        return true;
    }

    private static int[] getRandomArray(int n, int rangeL, int rangeR){
        if(rangeL > rangeR){
            return new int[0];
        }
        int[] result = new int[n];
        for (int i = 0 ; i < n ; i ++ ) {
            result[i] = (int)(Math.random() * (rangeR - rangeL + 1) + rangeL);
        }
        return result;
    }

    public static void main(String[] args) {
        MyQuickSort myQuickSort = new MyQuickSort();
        int n = 1000000;
        int rangeL = 0;
        int rangeR = 100000;
        for (int i = 0 ; i < 10 ; i ++ ){
            int[] arr = getRandomArray(n,rangeL,rangeR);
            long startTime = System.currentTimeMillis();
            quickSort(arr);
            long endTime = System.currentTimeMillis();
            System.out.println("quickSort1: " + (endTime - startTime) / 1000.0 + "s");
            System.out.println(isSorted(arr));
        }
    }

}

运行结果： N = 1000000

quickSort1: 0.12s
true
quickSort1: 0.108s
true
quickSort1: 0.096s
true
quickSort1: 0.105s
true
quickSort1: 0.093s
true
quickSort1: 0.095s
true
quickSort1: 0.103s
true
quickSort1: 0.099s
true
quickSort1: 0.109s
true
quickSort1: 0.102s
true

二、改进的快速排序2.0

1.0中，每次partitin只能排好一个数字，而这里把待排序区间分为三段，如果有和划分值相等的，直接划分到一个区间，下次partition可以不用再次进排序。

代码实现：

/**
 * Author Zq Created By 2020/10/8 15:37
 *
 * @version 1.0
 * @Description 改进的快速排序
 */
public class MyQuickSort2 {

    public static void quickSort(int[] arr){
        if(arr == null || arr.length < 2)
            return ;
        process(arr,0,arr.length - 1);
    }

    private static void process(int[] arr, int l, int r){
        if(l >= r)
            return;
        int[] index = partition(arr,l,r);
        process(arr,l,index[0]);
        process(arr,index[1],r);
    }

    private static int[] partition(int[] arr, int l, int r){
        int less = l - 1;
        int more = r;
        for (int i = l; i < more;) {
            if(arr[i] < arr[r]){
                swap(arr,++less,i++);
            }else if(arr[i] > arr[r]){
                swap(arr,--more,i);
            }else{
                i++;
            }
        }
        swap(arr,more++,r);
        return new int[]{less, more};
    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static boolean isSorted(int[] arr){
        int len = arr.length - 1;
        for (int i = 0 ; i < len; i ++ ){
            if(arr[i] > arr[i + 1])
                return false;
        }
        return true;
    }

    private static int[] getRandomArray(int n, int rangeL, int rangeR){
        if(rangeL > rangeR){
            return new int[0];
        }
        int[] result = new int[n];
        for (int i = 0 ; i < n ; i ++ ) {
            result[i] = (int)(Math.random() * (rangeR - rangeL + 1) + rangeL);
        }
        return result;
    }

    public static void main(String[] args) {
        MyQuickSort2 myQuickSort2 = new MyQuickSort2();
        int n = 1000000;
        int rangeL = 0;
        int rangeR = 100000;
        for (int i = 0; i < 10; i++) {
            int[] arr = getRandomArray(n,rangeL,rangeR);
            long startTime = System.currentTimeMillis();
            myQuickSort2.quickSort(arr);
            long endTime = System.currentTimeMillis();
            System.out.println("quickSort2: " + (endTime - startTime) / 1000.0 + "s");
            System.out.println(isSorted(arr));
        }
    }
}

运行结果：

N = 1000000

quickSort2: 0.138s
true
quickSort2: 0.122s
true
quickSort2: 0.112s
true
quickSort2: 0.118s
true
quickSort2: 0.113s
true
quickSort2: 0.125s
true
quickSort2: 0.12s
true
quickSort2: 0.131s
true
quickSort2: 0.127s
true
quickSort2: 0.107s
true

当数组中重复数字比较多时，quickSort2远远快于quickSort1,且当数据量很大，此外数组中重复数字非常多时，如: N = 1000000，数据分布在0 - 10之间，有可能造成栈溢出。

例：

N = 1000000，rangeL = 0, rangeR = 100 时:

quickSort1:

quickSort1: 9.832s
true
quickSort1: 9.632s
true
quickSort1: 10.185s
true
quickSort1: 8.503s
true
quickSort1: 9.428s
true

quickSort2:

quickSort2: 0.064s
true
quickSort2: 0.053s
true
quickSort2: 0.052s
true
quickSort2: 0.044s
true
quickSort2: 0.042s
true

三、改进的快速排序3.0

前面的1.0、2.0的时间复杂度都是O(n^2)，比如待排序数组已经是一个有序数组的情况下。

这里改进的地方在于，每次不是在待排序区间里固定选择最后一个数字，而是随机选择一个数字，然后与该区间最后一个数字进行交换。这样在整体看来时间复杂度就变为了O(N*log(N))。

代码实现：

/**
 * Author Zq Created By 2020/10/8 16:40
 *
 * @version 1.0
 * @Description 改进的快速排序
 *
 *
 */
public class MyQuickSort3 {

    public static void quickSort(int[] arr){
        if(arr == null || arr.length < 2)
            return;
        process(arr,0,arr.length - 1);
    }

    private static void process(int[] arr, int l, int r){
        if(l >= r)
            return;
        int[] index = partition(arr,l,r);
        process(arr,l,index[0]);
        process(arr,index[1],r);
    }

    private static int[] partition(int[] arr, int l, int r){
        int less = l - 1;
        int more = r;
        swap(arr,r,(int)(Math.random() * (r - l + 1) + l));
        for (int i = l; i < more; ) {
            if(arr[i] < arr[r]){
                swap(arr,++less,i++);
            }else if(arr[i] > arr[r]){
                swap(arr,--more,i);
            }else {
                i++;
            }
        }
        swap(arr,more++,r);
        return new int[]{less, more};
    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static boolean isSorted(int[] arr){
        int len = arr.length - 1;
        for (int i = 0 ; i < len; i ++ ){
            if(arr[i] > arr[i + 1])
                return false;
        }
        return true;
    }

    private static int[] getRandomArray(int n, int rangeL, int rangeR){
        if(rangeL > rangeR){
            return new int[0];
        }
        int[] result = new int[n];
        for (int i = 0 ; i < n ; i ++ ) {
            result[i] = (int)(Math.random() * (rangeR - rangeL + 1) + rangeL);
        }
        return result;
    }

    public static void main(String[] args) {
        MyQuickSort3 myQuickSort3 = new MyQuickSort3();
        int n = 1000000;
        int rangeL = 0;
        int rangeR = 100000;
        for (int i = 0; i < 10; i++) {
            int[] arr = myQuickSort3.getRandomArray(n, rangeL, rangeR);
            long startTime = System.currentTimeMillis();
            myQuickSort3.quickSort(arr);
            long endTime = System.currentTimeMillis();
            System.out.println("quickSort3: " + (endTime - startTime) / 1000.0 + "s");
            System.out.println(isSorted(arr));
        }
    }
}

运行结果：

N = 1000000

quickSort3: 0.121s
true
quickSort3: 0.108s
true
quickSort3: 0.106s
true
quickSort3: 0.105s
true
quickSort3: 0.103s
true
quickSort3: 0.111s
true
quickSort3: 0.116s
true
quickSort3: 0.116s
true
quickSort3: 0.113s
true
quickSort3: 0.119s
true

当数据量很大，此外数组中重复数字非常多时，

如: N = 1000000，数据分布在0 - 10之间

quickSort3: 0.027s
true
quickSort3: 0.017s
true
quickSort3: 0.016s
true
quickSort3: 0.017s
true
quickSort3: 0.017s
true

当数组已排好序时：

	public static void main(String[] args) {
        MyQuickSort3 myQuickSort3 = new MyQuickSort3();
        int n = 1000000;
        int rangeL = 0;
        int rangeR = 100000;
        for (int i = 0; i < 5; i++) {
            int[] arr = myQuickSort3.getRandomArray(n, rangeL, rangeR);
            myQuickSort3.quickSort(arr);
            long startTime = System.currentTimeMillis();
            myQuickSort3.quickSort(arr);
            long endTime = System.currentTimeMillis();
            System.out.println("quickSort3: " + (endTime - startTime) / 1000.0 + "s");
            System.out.println(isSorted(arr));
        }
    }

运行结果：

N = 1000000

quickSort3:

quickSort3: 0.12s
true
quickSort3: 0.103s
true
quickSort3: 0.101s
true
quickSort3: 0.085s
true
quickSort3: 0.102s
true

此时，quickSort1、quickSort2会出现栈溢出异常。

待续。。。

Java
快速排序
  • 作者：CodeC.C（联系作者）
  • 发表时间：2020-10-07 12:00:15
    •

    评论  null  条