快速排序

1 荷兰国旗问题

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

• 快速排序1.0：每次确定一个数的位置
• 快速排序2.0：每次确定一个多个数（num相同，范围）的位置
• 快速排序3.0：随机快速排序+荷兰国旗问题

随机快排（快排3.0）：

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

1.在这个范围上，随机选择一个num
2.用num对该范围做partition（小于num的放左边，等于num的放中间，大于num的放右边，假设等于num的数所在范围是[a, b]）
3.对arr[L, a-1]进行快速排序（递归）
4.对arr[b+1, R]进行快速排序（递归）
因为每一次partition都会搞定一批数的位置不再变动，所以最终排序能完成

2 快速排序

2.1 递归实现

    public static void quickSort2(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        //让0 到 arr.length - 1有序
        process2(arr, 0, arr.length - 1);
    }

    public static void process2(int[] arr, int L, int R){
        if(L >= R){
            return;
        }
        //随机快排：随机选一个数与最右边的数交换
        //在arr的[L, R]上随机选择一个数进行交换
        swap(arr ,L + (int)(Math.random() * (R - L + 1)), R);
        int[] equalArea = netherlandsFlag2(arr, L, R);
        //新的左递归
        process2(arr, L, equalArea[0] - 1);
        //新的右递归
        process2(arr, equalArea[1] + 1, R);
    }

    //荷兰国旗问题
    public static int[] netherlandsFlag2(int[] arr, int L, int R){
        if(L > R){
            return new int[]{-1, -1};
        }
        if(L == R){
            return new int[]{1, 1};
        }
        int less = L - 1;
        int more = R;
        int index = L;
        while(index < more){
            if(arr[index] == arr[R]){
                index++;//等于，直接移动【index++】
            } else if(arr[index] < arr[R]){
                //小于，与小于区域的前一个数换
                swap(arr, index++, ++less);
            } else {
                //大于，与大于区域的前一个数换
                swap(arr, index, --more);
            }
        }
        swap(arr, more, R);
        //less+1：等于区的开始
        return new int[]{less + 1, more};
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

2.2 非递归实现【栈结构】

①定义内部类Op：用来存储要排序的范围信息
Op:

//排序范围
public static class Op{
    public int l;
    public int r;

    public Op(int left, int right){
        l = left;
        r = right;
    }
}   
1
2
3
4
5
6
7
8
9
10

②荷兰国旗问题：用来排序（小于放左，等于放中，大于放右）

//荷兰国旗问题
public static int[] netherlandsFlag2(int[] arr, int L, int R){
    if(L > R){
        return new int[]{-1, -1};
    }
    if(L == R){
        return new int[]{1, 1};
    }
    int less = L - 1;
    int more = R;
    int index = L;
    while(index < more){
        if(arr[index] == arr[R]){
            index++;//等于，直接移动【index++】
        } else if(arr[index] < arr[R]){
            //小于，与小于区域的前一个数换
            swap(arr, index++, ++less);
        } else {
            //大于，与大于区域的前一个数换
            swap(arr, index, --more);
        }
    }
    swap(arr, more, R);
    //less+1：等于区的开始
    return new int[]{less + 1, more};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

③交换：

public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
}
1
2
3
4
5

全部代码：

//排序范围
public static class Op{
    public int l;
    public int r;

    public Op(int left, int right){
        l = left;
        r = right;
    }
}   

 //非递归版本【用栈实现】
public static void quickSort3(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    int N = arr.length;
    swap(arr, (int) (Math.random() * N), N-1);
    int[] equalArea = netherlandsFlag(arr, 0, N - 1);
    int el = equalArea[0];
    int er = equalArea[1];
    Stack<Op> stack = new Stack<>();
    stack.push(new Op(0, el - 1));//类比：左边递归
    stack.push(new Op(er + 1, N - 1));//右边递归
    while(!stack.isEmpty()){
        Op op = stack.pop();
        if(op.l < op.r){
            swap(arr, op.l + (int)(Math.random() * (op.r - op.l + 1)), op.r);
            equalArea = netherlandsFlag(arr, op.l, op.r);
            el = equalArea[0];
            er = equalArea[1];
            //入栈：模拟向下递归
            stack.push(new Op(op.l, el - 1));
            stack.push(new Op(er + 1, op.r));
        }
    }
}




//荷兰国旗问题
public static int[] netherlandsFlag2(int[] arr, int L, int R){
    if(L > R){
        return new int[]{-1, -1};
    }
    if(L == R){
        return new int[]{1, 1};
    }
    int less = L - 1;
    int more = R;
    int index = L;
    while(index < more){
        if(arr[index] == arr[R]){
            index++;//等于，直接移动【index++】
        } else if(arr[index] < arr[R]){
            //小于，与小于区域的前一个数换
            swap(arr, index++, ++less);
        } else {
            //大于，与大于区域的前一个数换
            swap(arr, index, --more);
        }
    }
    swap(arr, more, R);
    //less+1：等于区的开始
    return new int[]{less + 1, more};
}
public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72