当前位置:首页 > 开发 > IT生活 > 正文

笔试简单基础算法

发表于: 2012-11-08   作者:braveCS   来源:转载   浏览:
摘要: 最近太困太累,昨天宣讲会上打盹打得啊,最后笔试稀里糊涂地写了。回来后想起自己写的,太次了。冒泡排序也能写错,生产者和消费者也挂了。这里就补上冒泡,生生产者消费者另外一篇 http://bravecs.iteye.com/blog/1720415 。提醒自己做事不能随便,不能差不多,不能浮躁 import java.util.Scanner; class Sort { priv
最近太困太累,昨天宣讲会上打盹打得啊,最后笔试稀里糊涂地写了。回来后想起自己写的,太次了。冒泡排序也能写错,生产者和消费者也挂了。这里就补上冒泡,生生产者消费者另外一篇http://bravecs.iteye.com/blog/1720415 。提醒自己做事不能随便,不能差不多,不能浮躁
import java.util.Scanner;

class Sort
{
	private int[] a;
	private int len;
	private int count;
	//从console中输入
	public void input()
	{
		Scanner scanner=new Scanner(System.in);
		String str=scanner.nextLine();
		String[] temp=str.split(",");
		len=temp.length;
		a=new int[len];
		for(int i=0;i<len;i++)
			a[i]=Integer.parseInt(temp[i]);
	}
	//显示
	public void show()
	{
		for(int i=0;i<len;i++)
			System.out.print(a[i]+",");
		System.out.println("\n比较次数:"+count);
	}
	
	//冒泡排序
	public void sort()
	{
		boolean flag=false;
		count=0;
		int temp;
		for(int i=0;!flag&&i<len-1;i++)
		{
			flag=true;
			for(int j=0;j<len-i-1;j++)
			{
				if(a[j]<a[j+1])
				{
					temp=a[j];
					a[j]=a[j+1];
					a[j+1]=temp;
					flag=false;
					count++;
				}
			}
		}
	}
	
	/**
	 * 二分法dichotomy查找  非递归recursion
	 * 前提:已排好序
	 */
	public int dichotomy(int target)
	{
		int start=0,end=a.length-1,middle;
		while(start<end)
		{
			middle=(start+end)/2;
			if(a[middle]==target)
				return middle;
			else if(a[middle]<target)
				end=middle-1;
			else
				start=middle+1;	
		}
		return start==end&&a[start]==target?start:-1;
	}
	
	/**
	 * 二分法dichotomy查找 递归 recursion
	 * 前提:已排好序
	 */
	public int dichotomy(int target,int start,int end)
	{
		if(start>end)
			return -1;
		if(start==end)
			return a[start]==a[end]?start:-1;
		int middle=(start+end)/2;
		if(a[middle]==target)
			return middle;
		if(a[middle]<target)
			return dichotomy(target,start,middle-1);
		else
			return dichotomy(target,middle+1,end);		
	}	
}

public class Cs 
{
	public static void main(String[] args)
	{	
		Sort cs=new Sort();
		cs.input();
		cs.sort();
		cs.show();
	}	
}

笔试简单基础算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号