荷兰国旗-快排应用

荷兰国旗问题:

”荷兰国旗难题“是计算机科学中的一个程序难题,它是由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);
                //p值为1,用来判断0,1,2                                           
		int res[]=partition(test,0,test.length-1,1);
		printArray(test);
		System.out.println(res[0]);
		System.out.println(res[1]);
	}

}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1935: [Shoi2007]Tree 园丁的烦恼

1935: [Shoi2007]Tree 园丁的烦恼 Time Limit: 15 Sec  Memory Limit: 357 MB Submit: 648 ...

2948
来自专栏算法修养

HYSBZ 2160 拉拉队排练(回文树)

2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

3387
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

3765
来自专栏数据结构与算法

BZOJ3884: 上帝与集合的正确用法(欧拉函数 扩展欧拉定理)

第二天, 上帝创造了一个新的元素,称作“α”。“α”被定义为“元”构成的集合。容易发现,一共有两种不同的“α”。

1332
来自专栏落影的专栏

程序员进阶之算法练习(十一)有感而发

前言 经过这几年的观察,我发现,国内本科高校的ACM集训队,往往汇聚着该校相对靠谱的那一批人。 拿本校举例,队内的众学长学姐毕业之后,有去国内top2的高校...

37010
来自专栏C语言及其他语言

【每日一题】问题 1431: 分糖果

问题描述 有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果,然后进行下面的游戏: 每个小朋友都把自己的糖果分一半给左手边的孩子。 一轮分糖后,...

852
来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

3177
来自专栏专注研发

poj-1008-玛雅历

上周末,M.A. Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳(玛雅人用于记事的工具)中,教授发现玛雅人使用了一个一年有365天的叫做Haab的历法...

1653
来自专栏JetpropelledSnake

Python实现简单的三级菜单

话不多说,直奔代码 # 要处理的字典 dic1 = { '北京': { '东城': { ...

6289
来自专栏我的python

递归方法的理解

递归思想算是编程中比较常见但对初学者而言又有些难以理解的方法了。在leetcode上刷了几道题都用递归思想成功解决后觉得应该贯彻互联网的开源共享精神,总结一下自...

930

扫码关注云+社区