《JAVASE系列》二分查找算法以及冒泡排序

前言

本章主要讲解二分查找算法以及冒泡排序的优化版本。

二分查找

二分查找的基本思想是

将n个元素分成大致相等的两部分 ，取a [n/2]与x做比较，如果x=a [n/2],则找到x,算法中止；如果x<a [n/2],则只要在数组a的左半部分继续搜索x,如果x>a [n/2],则只要在数组a的右半部搜索x.

二分查找的前提：

排序的内容已经是有序的了。

二分查找代码：

public static int binarysearch(int[] array,int n){
        int left = 0;
        int right = array.length-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(array[mid]<n){
                left = mid + 1;  //n大于中间值，在右半部分查找
            }
            else if(array[mid]>n){
                right = mid - 1; //n小于中间值，在左半部分查找
            }
            else{ 
                return mid;     //返回正确值的数组下标
            }
        }
        return -1;
    }

代码讲解：

二分查找，也叫折半查找，先定义一个 left变量作为左移动标志，定义一个 right变量作为右移动标志。开始循环查找我们想要的数字在数组中对应元素的下标。

查找失败的条件是： left左移动标志的大小已经超过right。

查找成功的条件是：有对应的下标等于我们想要查找的数组。

把问题分三部分，左半部分、中间值、右半部分。将目标数值与中间值比较，若小于中间则与左半部分比较，若大于中间则与右半部分比较，等于中间值直接返回，否则不断迭代得出结果。

冒泡排序（优化）

冒泡排序的基本思想：

它的基本思想是对所有相邻记录的关键字值进行比效，如果是逆顺（a[j]>a[j+1]），则将其交换，最终达到有序化;

冒泡排序代码：

public static void bubblesort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            boolean falg = true;
            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;
                    falg = false;
                }
            }
            if(falg == true){
                break;
            }
        }
    }

代码讲解：

第一个for循环确定总共需要比较的趟数，由于n个数只需要比较n-1趟，所以趟数为数组元素个数减一。

第二个for循环确定每一趟需要比较的个数。

每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。

可以定义一个falg 来提高代码的效率，只要这一趟没有发生交换，则说明数组已经有序，则直接跳出总循环。结束排序。

总结：
冒泡排序与二分查找是我们算法入门必学的内容。
感谢阅读！
与君共勉！