冒泡排序和二分查找

深碍√TFBOYSˉ_ 2022-01-27 07:35 169阅读 0赞

#### 有序数组二分查找实现： ####

public class BinarySearch{
        
    	/*
    		int midArray = (rightArray - leftArray) / 2; //每次循环都会改变，要重新算
    		
    		int midArray = leftArray + (rightArray - leftArray)/2; //为了防止溢出，
    	*/
    	
    	public static int binarySearch(int[] array, int key) {
        
    		int leftArray = 0;
    		int rightArray = array.length;
    		
    		//[leftArray, rightArra)区间还有数继续循环
    		while(leftArray < rightArray){
        
    			
    			int midArray = leftArray + (rightArray - leftArray)/2;
    			
    			if(key == array[midArray]){
        
    				return midArray;
    				
    			}else if(key < array[midArray]){
        
    				rightArray = midArray;
    			}else{
        
    				leftArray = midArray + 1;
    			}
    		}
    		return -1;
    }
    	
    	public static void main(String[] args) {
        
    		int[] array = {
        1,2,3,4,5,6,7,8,9};
    		
    		int index1 = binarySearch(array,7);
    		System.out.println("7 的下标是：" + index1);
    	}
    }

#### 运行结果： ####

![在这里插入图片描述][20190525214158748.png]

#### 冒泡排序 ####

import java.util.Arrays;
    
    public class BubbleSort{
        
    	public static void bubbleSort(int[] array){
        
    		//本质上是 减治算法
    		int tmp = 0;
    		for(int i=0; i<array.length-1; i++){
        //控制比较次数
    		
    			boolean isSwapped = false;
    			
    			//经过两两比较，将最大的数冒泡到最后
    			for(int j=0; j < array.length - i - 1; j++){
        
    				if(array[j] > array[j+1]) {
        
    					tmp = array[j];
    					array[j] = array[j+1];
    					array[j+1] = tmp;
    					isSwapped = true;
    				}
    			}	
    			if(!isSwapped){
         //优化
    				return;
    			}			
    		}
    	}
    	
    	public static void printArray(int[] array){
        
    		for(int i=0; i<array.length; i++){
        
    			System.out.printf("%d ",array[i]);
    		}
    		System.out.println();
    	}
    	
    	public static void main(String[] args){
        
    		
    		int[] randomArray = new int[]{
         3,5,2,12,3,56,75,32};
    		
    		//System.out.println(Arrays.toString(bubbleSort(randomArray)));//错误
    		
    		System.out.print("使用自定义方法打印数组： \t");
    		printArray(randomArray);
    		
    		System.out.print("使用toString方法打印数组： \t");
    		System.out.println(Arrays.toString(randomArray));//使用 toStirng()方法打印数组
    		
    		bubbleSort(randomArray);
    		System.out.print("排序后的数组： \t\t\t");
    		System.out.println(Arrays.toString(randomArray));
    		
    		//System.out.println(bubbleSort(randomArray));
    		//错误: 此处不允许使用 '空' 类型
            //System.out.println(bubbleSort(new int[]{ 3,5,2,12,3,56,75,32}));
    		//错误: 此处不允许使用 '空' 类型
    		//System.out.println(bubbleSort(randomArray)); 中直接传入数组是无法打印的，要使用toString()方法
    		
    	}
    }

![在这里插入图片描述][2019052521581312.png]

[20190525214158748.png]: /images/20220127/8a75cf6c031541d3a9443c4d8d0ad8fb.png
[2019052521581312.png]: /images/20220127/4947ec080fd447ad970dcdb1392b5a7f.png