荷兰国旗-快速排序应用


荷兰国旗

”荷兰国旗难题“是计算机科学中的一个程序难题,它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。现有红白蓝三个不同颜色的小球,乱序排列在一起,请重新排列这些小球,使得红白蓝三色的同颜色的球在一起。
ps:我们可以将红白蓝三色小球想象成条状物,有序排列后正好组成荷兰国旗。


www.srblog.cn


分析

arr[i]< key时相当于“荷兰国旗问题”中的0
arr[i]= key时相当于“荷兰国旗问题”中的1
arr[i]> key时相当于“荷兰国旗问题”中的2

这样就可以使用“荷兰国旗问题”的解法来解决快速排序了,这样一来,即使待排序的元素中有一些元素和key一样,也能保证时间复杂度是最差是NlogN的,因为对于待排序的等于Key的数值,可以在执行下一次Partition时直接跳过,利于数据规模的降低。


代码

荷兰国旗
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
public class NetherlandsFlag {

public static int[] partition(int[] arr,int L,int R,int p) {
int less = L-1;
int more = R+1;
while(L < more) {
if(arr[L] < p) {
swap(arr,++less,L++);
}else if(arr[L] > p) {
swap(arr,--more,L);
}else {
L++;
}

}
return new int[] {less+1,more-1};

}

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

}
public static int[] getArray() {
int arr[] = new int[10];
for(int i = 0;i < arr.length;i++) {
arr[i] = (int)(Math.random()*3);
}
return arr;
}
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();

}
public static void main(String args[]) {
int test[] = getArray();
printArray(test);
int res[] = partition(test,0,test.length-1,1); //p值为1,用来判断0,1,2
printArray(test);
System.out.println(res[0]);
System.out.println(res[1]);
}

}
sr wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
0%