一.经典快排思想
前提条件：给定一个无序数组arr
- 取这个数组最后一个数 num 作为标准，将前面部分的数分为两部分，使得<=num的部分在左边，>num的数在右边；
- 然后将最后一个数和>num部分的第一个数进行交换，就使得原本在数组最后位置的num找到了正确的位置，它的左边都是比它小的以及和它一样的数，右边都是比它大的数
- 回到1，进行递归或迭代，使得所有的数都找到正确的位
二.通过荷兰国旗问题改进快排
什么是荷兰国旗问题？
已知一个整形数组arr，和一个整数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
解决思路：
遍历数组
- 1. 若比num小，当前位置和小于的最后一个位置+1的值交换，并当前位置++；
- 2. 若比num大，当前位置和大于的第一个位置-1的值交换；
- 3. 若等于num的值，当前位置++；
附上代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static void netherlandsflag(int[] arr, int l, int r, int num) { int i = l; int p1 = l-1; int p2 = r+1; //终止条件：当前数的位置在大于区的前一个 while(i < p2) { if(arr[i] < num) { //当前数比num小，放左边，i位置上的数和l上的数进行交换，并且i++，l++ swap(arr, i++, ++p1); } else if(arr[i] == num) { //当前数和num相等，i++ i++; } else { //当前数比num大，放右边，i位置上的数和r上的数进行交换，并且i++，r-- swap(arr, i, --p2); } }} |
我们可以发现，荷兰国旗问题和经典快排不同的就只是将<=num改为了< num和=num两部分，借用这个思想使得原来每次只可以让一个数找到正确的位置改进为了每次至少让一个数找到位置。
三.在这基础上将其改为随机快排
随机快排改进的地方只是在选取数的时候，将每次都选取最后位置的数改为选取随机的一个数作为num，这样做的好处是什么呢？
1.选取最后一个数：如果是一个已经排好序的数组，每次找到位置之后，左边是要进行排序的部分，数组长度是原长度-1，它的时间复杂度就是o(n^2)；如果每次找到的数都是中间的位置，它的时间复杂度就只有o(logn)
2.然而以随机数作为选取的标准num的时候，因为是随机的，就只能通过数学期望去计算它的时间复杂度，时间复杂度是o(logn)
下面附上最终的快排代码及注释
|
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
|
/* * swap(int[] arr, int i, int j);是将arr数组的i和j位置上的数交换的方法 */public static void quicksort(int[] arr) { // 如果为空或长度为1不需要排序，直接返回 if(arr == null || arr.length < 2) return; else quicksort(arr, 0, arr.length - 1);}// 递归排序public static void quicksort(int[] arr, int l, int r) { if(l < r) { /* * 随机快排的随机就在这 * 是随机选取了一个数，和 r 进行了交换，然后使用这个数作为num， * 所以每次选取的num是随机的， * 在计算时间复杂度时，是没有最优最差情况的 * 而是通过一个长期的数学期望计算的，结果是o(n*logn) */ swap(arr, l + (int) (math.random() * (r - l + 1)), r); int[] border = partition(arr, l, r); // 小于区和大于区进行递归 quicksort(arr, l, border[0] - 1); quicksort(arr, border[1] + 1, r); }}// 将给定数组划分为小于区、等于区和大于区public static int[] partition(int[] arr, int l, int r) { int num = arr[r]; int less = l - 1; int more = r + 1; int curr = l; // 分为小于区等于区和大于区 while(curr < more) { if(arr[curr] < num) { swap(arr, curr++, ++less); } else if(arr[curr] > num) { swap(arr, curr, --more); } else { curr++; } } //返回等于区的左右边界的下标，通过下标确定小于区和大于区递归时的参数 return new int[] {less + 1, more - 1};} |
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对服务器之家的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/sdr_zd/article/details/79425077
