荷兰国旗-快速排序应用

发布于 2019-05-23 17:46:55

6780

发布于 2019-05-23 17:46:55

文章被收录于专栏：swag codeswag code

荷兰国旗

”荷兰国旗难题“是计算机科学中的一个程序难题，它是由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]);
	}

}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

dijkstra