java引用类型的排序和搜索算法

╰半橙微兮° 2022-04-06 09:24 172阅读 0赞

# java引用类型的排序和搜索算法 #

PracticeDate.java

/*
    	对引用类型的数组
    	采用冒泡法排序
    	使用二分法查找指定对象在数组中的位置
    */
    public class PracticeDate {
    	
    	public static void main(String[] args) {
    		//引用类型数组
    		Date[] days = new Date[5];
    		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);
    		
    		//冒泡排序
    		bubbleSort(days);
    		
    		for(int i=0; i<days.length; i++) {
    			//打印对象的引用，相当与直接调用toString(),需要重写toString()
    			System.out.println(days[i]);//
    		}
    		
    		//
    		
    		System.out.println("返回值数组里面的位置（下标）");
    		Date val = new Date(2004, 5, 9);
    		System.out.println(binarySearch(days, val));//在days数组中的位置为1
    		
    	}
    	
    	//冒泡排序，返回一个数组的引用
    	public static Date[] bubbleSort(Date[] a){
            int len = a.length;
    		//从底往上
            for(int i = len-1;i>=1;i--){
    			//数组序号从小到大
                for(int j = 0;j<=i-1;j++){
    				//比较日期大小
                    if(a[j].compare(a[j+1]) > 0){
    					//下标值没变，指向的对象改变了
                        Date temp = a[j]; 
                        a[j]=a[j+1];
                        a[j+1]=temp;
                    }
                }
            }
            return a;
        }
    
    	//二分法查找
    	/*
    		Date[] a	查找的数组
    		Date num	查找数组中的值
    		return		返回值的位置
    	*/
    	public static int binarySearch(Date[] a, Date num) {
    		if (a.length==0) return -1;
    		
    		int startPos = 0; //起始位置
    		int endPos = a.length-1;//结束位置
    		int m = (startPos + endPos) / 2;//中间的位置
    		
    		/*
    			起始位置比结束位置小，或等于，执行循环
    			起始位置比结束位置大，循环结束
    		*/
    		while(startPos <= endPos){
    			if(num.compare(a[m]) == 0) return m;//找到了返回m
    			if(num.compare(a[m]) > 0) {
    				startPos = m + 1;//起始位置向右调整
    			}
    			if(num.compare(a[m]) < 0) {
    				endPos = m -1;//结束位置向左调整
    			}
    			m = (startPos + endPos) / 2;//重新计算中间的位置
    		}
    		
    		return -1;//没有找到返回-1
    	}
    	
    }
    
    //定义日期类
    class Date {
    	int year, month, day;
    
    	Date(int y, int m, int d) {
    		year = y; month = m; day = d;
    	}
    
    	//比较日期大小
    	public int compare(Date date) {
    		return year > date.year ? 1
    			   : year < date.year ? -1
    			   : month > date.month ? 1
    			   : month < date.month ? -1
    			   : day > date.day ? 1
    			   : day < date.day ? -1 : 0;
    	}
    
    	//重写toString()
    	public String toString() {
    		return "Year:Month:Day -- " + year + "-" + month + "-" + day;
    	}
    }

F:\java>javac PracticeDate.java
    
    F:\java>java PracticeDate
    Year:Month:Day -- 2004-5-4
    Year:Month:Day -- 2004-5-9
    Year:Month:Day -- 2006-5-4
    Year:Month:Day -- 2006-7-4
    Year:Month:Day -- 2008-5-4
    返回值数组里面的位置（下标）
    1
    
    F:\java>