冒泡排序、选择排序和二分查找

最近有小伙伴后台留言表示要详细了解一下冒泡排序和选择排序的原理，so阿Q便在这里做一个简单的介绍，希望对小伙伴加深冒泡排序以及选择排序的理解有点小帮助吧。

冒泡排序算法的原理如下：

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

代码如下：

public static void bubbleSort(int[] arr) {
    //{24, 69, 57, 13, 80};
    for (int i = 0; i < arr.length - 1; i++) {//外循环只需要比较arr.length-1次就可以了
        for (int j = 0; j < arr.length - 1 - i; j++) {  //-1为了防止索引越界,-i为了提高效率，因为每一次排序最后边排好的已经不用再比较了。
            if(arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j+1] = temp;
            }
        }
    }
}

选择排序算法的原理如下：

1. 从0索引开始，依次和后面元素比较，如果0索引的元素小则不变，反之，交换他们的值。第一次完毕，最小值出现在了0索引处；
2. 从1索引开始，重复1步骤，第二小的值出现在了1索引处；
3. 针对所有的元素重复以上的步骤，除了最后一个。

代码如下：

public static void selectSort(int[] arr) {
    //{24, 69, 80, 57, 13};
    for (int i = 0; i < arr.length - 1; i++) {//只需要比较arr.length-1次，i控制第几个索引处的值
        for (int j = i + 1; j < arr.length; j++) {//j控制后边的元素值
            if(arr[i] > arr[j]) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

二分法查找：

前提是数组必须是有序的。先设要查找的值为x，中间索引为y，总长度为length。

1. 判断数组y索引处的值是否与x相等，若相等则得到该索引值，若不相等则进行判断：如果中间值大于x，则去索引值为0—[y-1]区间查找；若中间值小于x，则去[y+1]—[length-1]区间查找，
2. 去重新确定的区间内重复步骤1操作；
3. 如果查到最后发现最小索引大于了最大索引,就没有查找的可能性了即查找失败。

代码如下：

//int[] arr = {11,22,33,44,55,66,77};
public static int getIndex(int[] arr, int value) {
    int min = 0;
    int max = arr.length - 1;
    int mid = (min + max) / 2;

    while(arr[mid] != value) {      //当中间值不等于要找的值,就开始循环查找
        if(arr[mid] < value) {      //当中间值小于了要找的值
            min = mid + 1;      //最小的索引改变
        }else if (arr[mid] > value){    //当中间值大于了要找的值
            max = mid - 1;      //最大的索引改变
        }
        mid = (min + max) / 2;      //无论最大还是最小改变,中间索引都会随之改变

        if(min > max) {         //如果最小索引大于了最大索引,就没有查找的可能性了
           return -1;       //返回-1
        }
     }
     return mid;
}

这三块知识就梳理到这边了，想了解更多学习知识，请关注微信公众号“阿Q说”，获取更多学习资料吧！你也可以后台留言说出你的疑惑，阿Q将会在后期的文章中为你解答。每天学习一点点，每天进步一点点。