Java 二分法,递归，冒泡

刺骨的言语ヽ痛彻心扉 2023-05-30 14:57 4阅读 0赞

**1 二分法**  
1）原理：二分法适用于有序的数据。  
1.只要低位下标不大于高位下标，就继续二分法；  
2.如果要查找的值等于中间值，即find == arr\[mid\],则返回下标mid;  
如果要查找的值小于中间值，即find < arr\[mid\],则往小端找，high=mid-1;  
如果要查找的值大于中间值，即find > arr\[mid\],则往大端找，low=mid+1;  
2) 代码实现

package com.test.test1;
    
    import java.util.Arrays;
    
    public class Test2 {
    
    	public static void main(String[] args){
    		int[] arr = {5,7,22,2,16,33,65,87,23,19};//定义一个无序的数组
    		Arrays.sort(arr); //对数组进行排序
    		System.out.println(Arrays.toString(arr));//输出排序的数组
    		System.out.println(binarySearch(arr,65));//写出要查找的数据，调用二分法方法
    		
    	}
    	//定义一个二分法方法
    	public static int binarySearch(int[] arrs, int find){
    		int low = 0;  //定义一个低位
    		int high = arrs.length-1;  //定义一个高位
    		int mid = 0;   //定义一个中间值
    		while(low<high){//只要低位下标不大于高位下标，就继续二分法
    			mid = (high+low)/2;  //给中间值赋值
    			if(find < arrs[mid]){ 
    				 high = mid-1;  //二分之后中位比find值大，说明find值在中位的右边，那么高位就是此时的中位，然后继续二分
    			}else if(find>arrs[mid]){
    				low = mid +1; //二分后中位比find值小，说明find值在中位的左边，那么低位就是此时的中位，然后继续二分
    			}else {
    				return mid; //当中位值和find值相等时，找到find值所对应的下标，二分结束
    			}
    		}
    		return -1;
    				
    	}
    	
    }

**2 递归**  
在定义一个函数时，出现直接或间接调用自己的成分，成为递归。  
最常见的递归是阶乘。

package com.test.test1;
    public class Test3 {
    	public static void main(String[] args){	
    		int s = product(6);//求6!
    		System.out.println(s);
    	}
    	public static int product(int n){
    		if(n==1){
    			return 1;
    		}
    		return  n*product(n-1);
    	}
    }

**3 冒泡排序**  
1)依次比较相邻两个元素的大小，按照想要的顺序交换位置，直到没有可以交换的元素。

package com.test.test1;
    import java.util.Arrays;
    public class Test3 {
    	public static void main(String[] args){		
    		int[] arr = {2,6,3,7,9,12,55,21,1,12};
    		int[] arrs = sortMethod(arr); //对数组进行从小到大排序
    		System.out.println(Arrays.toString(arrs));
    	}
    	public static int[] sortMethod(int[] arr){
    		for(int i=0;i<arr.length-1;i++){//控制循环多少趟
    			for(int j=0;j<arr.length-1-i;j++){ //控制每一趟的循环次数
    				if(arr[j]> arr[j+1]){
    					int temp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = temp;
    				}
    			}
    		}
    		return arr;
    	}
    }

1.  奇偶交换排序  
    排序过程分为两个阶段：奇交换和偶交换。奇交换就是比较奇数索引及其相邻的后续元素，偶交换就是比较偶数索引及其相邻的后续元素。

package com.smart.Test;
    public class Test2 {
    	public static void main(String[] args) {
    		int[] s = { 12, 22, 1, 34, 6, 8, 13, 66 };
    		System.out.println(getStr(s));
    	}
    	public static String getStr(int[] arr) {
    		int exchFlag = 1, start = 1;
    		while (exchFlag == 1 || start == 1) {
    			exchFlag = 0;
    			for (int i = start; i < arr.length - 1; i += 2) {
    				if (arr[i] > arr[i + 1]) {
    					int temp = arr[i];
    					arr[i] = arr[i + 1];
    					arr[i + 1] = temp;
    					exchFlag = 1;
    				}
    			}
    			if (start == 0) {
    				start = 1;
    			} else {
    				start = 0;
    			}
    		}
    		return arr.toString();
    	}
    
    }

**4. 插入排序**

package com.smart.Test;
    public class Test3 {
    	public static void main(String[] args) {
    		int[] s = { 12, 22, 1, 34, 6, 8, 13, 66 };
    		System.out.println(getStr(s));
    	}
    	public static String getStr(int[] ar) {
    		int i, j, target;
    		for (i = 1; i < ar.length; i++) {
    			target = ar[i];
    			j = i - 1;
    			while (j >= 0 && ar[j] > target) {
    				ar[j + 1] = ar[j];
    				j--;
    			}
    			ar[j + 1] = target;
    		}
    		return ar.toString();
    	}
    }