《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 来提高代码的效率，只要这一趟没有发生交换，则说明数组已经有序，则直接跳出总循环。结束排序。
总结：
冒泡排序与二分查找是我们算法入门必学的内容。
感谢阅读！
与君共勉！