• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【每日蓝桥】14、一三年省赛Java组真题“三部排序”

互联网 diligentman 1个月前 (01-25) 12次浏览

你好呀,我是灰小猿,一个超会写bug的程序猿!

欢迎大家关注我的专栏“每日蓝桥”,该专栏的主要作用是和大家分享近几年蓝桥杯省赛及决赛等真题,解析其中存在的算法思想、数据结构等内容,帮助大家学习到更多的知识和技术!

标题:三部排序

一般的排序有许多经典算法,如快速排序、希尔排序

但实际应用时,经常会或多或少有一些特殊的要求,我们没必要套用那些经典算法,可以根据实际情况建立更好的解法,

比如:对一个整型数组中的数字进行分类排序

使得负数都靠左端,正数都靠右端,0在中部,注意问题的特点是:负数区域和正数区域并不要求有序,可以利用这个特点进行一次线性扫描就结束战斗!!!

以下的程序实现了该目标:

static void sort(int[] x) 
{
	int p = 0;
	int left = 0;
	int right = x.length - 1;
	
	while (p <= right) {
	    if (x[p] < 0) {
	        int t = x[p];
                x[p] = x[left];
	        x[left] = t;
			
	        left++;
	        p++;
	    }
	    else if (x[p] > 0) {
		int t = x[p];
		x[p] = x[right];
		x[right] = t;
				
		right--;
	    }else {
		_______________________
	}		
}
		
	}

如果给定数组:

25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0

排序后为:

-3,-2,-16,-5,0,0,0,21,19,33,25,16,18,25

 

请分析代码逻辑,并推测划线处的代码,通过网页提交

注意:仅把缺少的代码作为答案,千万不要填写多余的代码,符号或说明文字!

答案源码:

package 一三年省赛真题;

public class Year2013_Bt6 {

	static public void sort(int[] x) 
	{
		int p = 0;
		int left = 0;
		int right = x.length - 1;
		
		while (p <= right) {
			if (x[p] < 0) {
				int t = x[p];
				x[p] = x[left];
				x[left] = t;
				
				left++;
				p++;
			}
			else if (x[p] > 0) {
				int t = x[p];
				x[p] = x[right];
				x[right] = t;
				
				right--;
			}else {
//				___________________________
				p++;
			}		
		}
		
	}
	
	public static void main(String[] args) {
		int[] x = {25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0};
		sort(x);
		for (int i = 0; i < x.length; i++) {
			System.out.print(x[i] + ",");
		}
		
	}

}

 

 

输出样例:

【每日蓝桥】14、一三年省赛Java组真题“三部排序”

其中有不足或者改进的地方,还希望小伙伴留言提出,一起学习!

感兴趣的小伙伴可以关注专栏!

灰小猿陪你一起进步!

最后,我正在参加2020年度博客之星的评选,求小伙伴们帮忙投票支持一下哟!

投票链接:https://bss.csdn.net/m/topic/blog_star2020/detail?username=weixin_44985880

【每日蓝桥】14、一三年省赛Java组真题“三部排序”


程序员灯塔
转载请注明原文链接:【每日蓝桥】14、一三年省赛Java组真题“三部排序”
喜欢 (0)