数据结构与算法（一）：排序算法之 - 快速排序（详细步骤图解，附代码）_数据结构快速排序每一趟过程

快速排序

引子：Partition 过程

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

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

思路

维护一个 小于区，i 从第一个数开始：

• 只要 i 小于 num，就把 i 与 *小于区右侧的第一个数 *交换，并将小于区向右扩大一个数
• 如果 i 大于等于 num，将 i++

这样做的原理依据是：
在 i 的左侧，都是看过的数，并且每一次比较，都把比 num 小的数发送到小于区。而 i 右侧是没看过的数，随着 i++，将来一定会被看。

Partition 过程升级版：荷兰旗问题

荷兰器问题的描述，可查看：https://www.jianshu.com/p/356604b8903f

我们将数组划分为三个区域，即：小于区，等于区，大于区

1. 首先，随机选择一个基准数字 num

2. 下标 i 从第一个数字开始，与基准数字 num 比较，分为三种情况：

   • 如果 [i] == num，则 i++

   • 如果 [i] < num，则让 [i] 与小于区右侧的第一个元素交换，小于区右移一个元素，i++

   • 如果 [i] > num，则让 [i] 与大于区左侧的第一个元素交换，大于区右移一个元素，i 留在原地

3. 直到 i 与大于区相撞，即可停止，此时已经完成第一轮比较

4. 此时可以认为，等于区已经在它们正确的位置上。用同样的方法，递归对小于区、大于区分别进行再一次划分

第一轮排序过程 详细图解

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

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

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

1）用num对该范围做partition，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]

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

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

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

随机快排：时间复杂度分析

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

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

1）用num对该范围做partition，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]

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

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

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

代码

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

public static void process(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);
    process(arr, L, equalArea[0] - 1); // 小于区递归
    process(arr, equalArea[1] + 1, R); // 大于区递归
}

// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值，分为：小于区，等于区，大于区
public static int[] netherlandsFlag(int[] arr, int L, int R) {
    if (L > R) {
        return new int[] { -1, -1 };
    }
    if (L == R) {
        return new int[] { L, R };
    }
    int less = L - 1; // 小于区的右边界，L-1保持基准始终在最右侧，或者你可以用独立的变量记录它
    int more = R;     // 大于区的左边界
    int index = L;
    while (index < more) {
        if (arr[index] == arr[R]) {
            index++;
        } else if (arr[index] < arr[R]) {
            swap(arr, index++, ++less);
        } else {
            swap(arr, index, --more);
        }
    }
    swap(arr, more, R);
    return new int[] { less + 1, more };
}

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
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

---

完整代码（带对数器）

package class03;

public class Code03_PartitionAndQuickSort {

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

    public static int partition(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }
        int lessEqual = L - 1;
        int index = L;
        while (index < R) {
            if (arr[index] <= arr[R]) {
                swap(arr, index, ++lessEqual);
            }
            index++;
        }
        swap(arr, ++lessEqual, R);
        return lessEqual;
    }

    // arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
    //  <arr[R]  ==arr[R]  > arr[R]
    public static int[] netherlandsFlag(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        int less = L - 1; // < 区 右边界
        int more = R;     // > 区 左边界
        int index = L;
        while (index < more) {
            if (arr[index] == arr[R]) {
                index++;
            } else if (arr[index] < arr[R]) {
                swap(arr, index++, ++less);
            } else { // >
                swap(arr, index, --more);
            }
        }
        swap(arr, more, R);
        return new int[]{less + 1, more};
    }

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

    public static void process1(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // L..R partition arr[R]  [   <=arr[R]   arr[R]    >arr[R]  ]
        int M = partition(arr, L, R);
        process1(arr, L, M - 1);
        process1(arr, M + 1, R);
    }

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

    public static void process2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalArea = netherlandsFlag(arr, L, R);
        process2(arr, L, equalArea[0] - 1);
        process2(arr, equalArea[1] + 1, R);
    }

    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);
        process3(arr, L, equalArea[0] - 1);
        process3(arr, equalArea[1] + 1, R);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            int[] arr3 = copyArray(arr1);
            quickSort1(arr1);
            quickSort2(arr2);
            quickSort3(arr3);
            if (!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) {
                succeed = false;
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Oops!");
    }
}
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176