java-冒泡，选择排序，二分查找

た入场券 2022-01-28 10:09 246阅读 0赞

**冒泡排序**

**-概述：数值小的上浮，数值大的下沉**

**-比较方法：int\[\] arr = \{** 12,54,21,67,33**\}**

**                \*第一次：arr\[0\]与arr\[1\]比较，arr\[1\]与arr\[2\]比较，arr\[2\]与arr\[3\]比较，arr\[3\]与arr\[4\]比较，共比较4次，arr\[4\]必然是最大的数**

**               \*第二次：arr\[0\]与arr\[1\]比较，arr\[1\]与arr\[2\]比较，arr\[2\]与arr\[3\]比较，共比较3次，arr\[3\]是剩下数中最大的**

**\*第三次：arr\[0\]与arr\[1\]比较，arr\[1\]与arr\[2\]比较，共比较2次**

**               \*第四次：arr\[0\]与arr\[1\]比较，只比较1次**

**-外循环：决定比较的次数**

**-内循环：决定相邻两个数比较的次数**

public static void main(String[] args) {
    		int[] arr = {12,54,21,67,33};
    		bubbleSort(arr);
    		print(arr);
    	}
    	public static void bubbleSort(int[] arr){
    		for (int i = 0; i < arr.length; i++) {                      //控制比较次数,外循环只需要比较arr.length-1次就好了
    			for (int j = 0; j < arr.length-1-i; j++) {           //-1为了防止溢出
    				if(arr[j]>arr[j+1]){
    					int temp = arr[j];
    					arr[j] = arr[j+1];
    					arr[j+1] = temp;
    				}
    			}
    		}
    	}
    	public static void print (int[] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    	}

**48.选择排序**

**-概述：用一个索引位置的元素依次与其他索引位置的元素比较，小的在前，大的在后**

**-比较方法：int\[\] arr = \{** 12,54,21,67,33**\}**

**                  \*第一次：arr\[0\]分别与arr\[1-4\]比较，比较4次**

**                  \*第二次：arr\[1\]分别与arr\[2-4\]比较，比较3次**

**                  \*第三次：arr\[2\]分别a与rr\[3-4\]比较，比较2次**

**                  \*第四次：arr\[3\]分别与arr\[4\]比较，比较1次**

**-图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

public static void main(String[] args) {
    		int[] arr = {12,54,21,67,33};
    		selectSort(arr);
    		print(arr);
    	}
    	public static  void  selectSort(int[] arr) {
    		for (int i = 0; i < arr.length - 1; i++) {
    			for (int j = i; j < arr.length; j++) {
    				if(arr[i]>arr[j]){
    					int temp = arr[i];
    					arr[i] = arr[j];
    					arr[j] = temp;
    				}
    			}
    		}
    	}
    	public static void print (int[] arr) {
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i]+" ");
    		}
    	}

**附上一个另外一种思路的C的选择排序**

void test01(int *arr,int len)
    {
        for(int i=0;i<len-1;i++){
            int min = i;
        for(int j=i+1;j<len;j++){  //每一轮都选出数组中最小的元素，并让它和当前未归序的首元素互换
            if(arr[j]<arr[min]){
                min = j;
            }
        }
        if(min!=i){
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
        }
    }

**49.二分查找**

**-使用前提：数组有序**

**-比较方法：**

**                \*int left = 0;**

**                \*int right = arr.length-1;**

**                \*int middle = (left +right) / 2;**

**-图解：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		System.out.println("请输入你想要查询的值:");
    		int value  = sc.nextInt();
    		int[] arr = {11,22,33,44,55,66};
    		int index = Method(arr,value);
    		if(index!=-1){
    			System.out.println("所查询数字在数组中的索引是:"+index);
    		}else{
    		    System.out.println("所查询数字在数组中不存在！！");	
    		}
    	}
    
    	public static int Method(int[] arr, int value) {
    		int left = 0;                                        
    		int right = arr.length-1;
    		while(left<=right){
    			int middle = (left + right) /2;                         //当找到value时，返回此时的索引
    			if(arr[middle] == value) return middle;
    			else if(arr[middle] < value){
    				left  = middle +1;
    			}else{
    				right = middle -1;
    			}
    		}
    		return -1;                                                            //当数组中不存在value时，返回-1
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20220128/008aff6d785f4de4a37f60ab21cf95ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20220128/077244598bc04b8b88c8e3b1518944bd.png