荷兰国旗-快速排序应用


荷兰国旗

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



分析

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

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


代码

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]);
	}

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券