荷兰国旗
”荷兰国旗难题“是计算机科学中的一个程序难题，它是由Edsger Dijkstra提出的。荷兰国旗是由红、白、蓝三色组成的。现有红白蓝三个不同颜色的小球，乱序排列在一起，请重新排列这些小球，使得红白蓝三色的同颜色的球在一起。
ps:我们可以将红白蓝三色小球想象成条状物，有序排列后正好组成荷兰国旗。
分析
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);
printArray(test);
System.out.println(res[0]);
System.out.println(res[1]);
}
}
|