Java数组中的排序和二分查找

男娘i 2022-06-02 11:21 163阅读 0赞

【题目】

建立一个关于日期的类，其中包括日期比较的类，并且重写toString方法。在main函数中创建一个find()方法，利用二分查找的方法找出日期，若有则返回其在数组中的位置，若不存在则给出提示。

【相关内容】

一、toString方法的重写

toString回反应当前对象的自我描述。

在System.out.print()方法中如果插入的是一个对，就会调用对象中的toString方法。

package testCode123;
    
    class people{
    	String name;
    	people(String n){
    		this.name = n;
    	}
    }
    
    public class TestCode {
    	public static void main(String[] args){
    		people p = new people("小明");
    		System.out.println(p);
    	}
    }

输出为 testCode123.people@6f7a29a1

如果在类中重写toString方法

class people{
    	String name;
    	people(String n){
    		this.name = n;
    	}
    	 
    	public String toString() {
    		return "我的名字是:"+name;
    	}
    }

输出为 我的名字是:小明 所以我们可以通过重写toString方法来实现我们想要的输出。

二、日期的排序（自定义排序的书写）

在冒泡排序的基础上，可以在类中创建cmp()方法来实现日期之间的比较。

顺序为 年份--》月份--》日期

返回不同的值，来判日期之间的大小。若比当前日期大则返回1，若相同返回0，小则返回-1。

public int cmp(Date a){
    	return year>a.year ? 1
    		:year < a.year ? -1
    		:month > a.month ? 1
    		:month < a.month ? -1
    		:day > a.day ? -1
    		:day < a.day ? 1  
    		: 0;
    }

三、二分查找

二分查找建立在一个有序序列上，每次查找序列的中间值进行比较，并更新左右位置的数值。

middle = left + ( right - left) / 2

代码：

package testCode123;
    
    class Date{
    	int year;
    	int month;
    	int day;
    	
    	Date(int y,int m,int d){
    		this.year=y;this.month=m;this.day=d;
    	}
    	
    	public int cmp(Date a){
    		return year>a.year ? 1
    				:year < a.year ? -1
    				:month > a.month ? 1
    				:month < a.month ? -1
    				:day > a.day ? -1
    				:day < a.day ? 1  
    				: 0;
    	}
    	
    	public String toString(){
    		return year  + "年" + month + "月" + 
    				day + "日";
    	}
    }
    
    public class TestDateSort {
    	
    	public static void main(String[] args){
    		
    		Date[] days = new Date[10];
    		days[0] = new Date(2006, 5, 4);
    		days[1] = new Date(2006, 7, 4);
    		days[2] = new Date(2008, 5 ,4);
    		days[3] = new Date(2004, 5, 9);
    		days[4] = new Date(2004 ,5, 4);
    		days[5] = new Date(2005 ,2,18);
    		days[6] = new Date(2007, 10,29);
    		days[7] = new Date(2002,11,28);
    		days[8] = new Date(2010,6,3);
    		days[9] = new Date(2007,1,6);
    		
    		bubbleSort(days);
    		
    		for(int i = 0; i < days.length ; i++ ){
    			/*
    			System.out.println(days[i].year  + "年" + days[i].month + "月" + 
    				days[i].day + "日");
    			*/
    			System.out.println(days[i]); //当我们直接打印一个对象的时候，我们调用其中的toString方法
    		}
    		
    		Date test1 = new Date(2010,6,3);
    		
    		int l = find(test1,days);
    		if(l==-1)
    			System.out.println("未找到当前日期！！！");
    		else
    			System.out.println(l);
    	}
    	
    	public static Date[] bubbleSort(Date[] a){
    		int len = a.length;
    		for(int i = 0; i < len; i++){
    			for(int j = 0 ;j<i;j++){
    				if(a[j].cmp(a[i])>0){ //返回值去和0进行比较，大于零说明a[j]要比a[i]大    所以大的就要往后走
    					Date z;
    					z = a[i];
    					a[i] = a[j];
    					a[j] = z;
    				}
    			}
    		}
    		return a;
    	}
    	
    	public static int find(Date obj,Date[] cal){
    		int location= 0;
    		
    		int left,right,middle;
    		left = 0;
    		right = cal.length-1;
    		
    		while(left <= right){
    			middle = left + (right - left)/2;
    			if(obj.cmp(cal[middle])==0)
    			{
    				location = middle;
    				return location;
    			}
    			else if(obj.cmp(cal[middle])>0){
    				left = middle + 1;
    			}else{
    				right = middle - 1;
    			}
    			//System.out.println(left + " "  +right +" "+ middle);
    		}
    		return -1;
    	}
    }