算法合集 | 光影N棱镜

冒泡排序

冒泡排序：

比较数组中，两个相邻的元素，如果第一个数比第二个数大，我们就交换他们的位置。
每一次比较，都会产生出一个最大和一个最小的数。
下一轮则可以少一次排序
依次循环，直到结束。
我们看到嵌套循环，想到这个算法的时间复杂度为O(n2)。

冒泡排序数字替换逻辑：

将第一额数存放到一个临时的空间当中
将后一个数字放入到前一个数字空间中
将存放在临时空间中的前一个数字放入到原本后一个数字的空间中

实例：

import java.util.Arrays;

public class Demo02 {
    public static void main(String[] args) {
        int[] arrays = {1, 23, 454, 342, 55, 8848, 367, 365, 9656};

        //冒泡排序前
        System.out.println(Arrays.toString(arrays));

        //进行冒泡排序
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 冒泡排序
     *
     * @param arrays
     * @return
     */
    public static int[] sort(int[] arrays) {
        //临时变量
        int num = 0;

        //外层循环：判断我们要走多少次
        for (int i = 0; i < arrays.length - 1; i++) {

            //通过flag标识来减少没有意义的比较
            boolean flag = false;

            //内层循环：比较判断两个数
            //如果第一个数比第二个数大，我们就交换他们的位置。
            //注意：这里的j < arrays.length - 1 之后还需要减去"i"
            for (int j = 0; j < arrays.length - 1 - i; j++) {
                //当后一个数比前一个数大
                if (arrays[j + 1] > arrays[j]) {
                    num = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = num;
                    flag = true;
                }
            }
            if (flag == false) {
                break;
            }
        }

        return arrays;
    }
}

二分查找

二分查找的主要特点是，每次查找能排除一般元素，这样效率明显提高。但是二分查找要求比较苛刻，它要求元素必须是有序的（重要），否则不能进行二分查找。

具体操作如下：

public class Test3 {
    public static void main(String[] args) {
        // 1、准备好一个数组。
        int[] arr = {7, 23, 79, 81, 103, 127, 131, 147};

        System.out.println(binarySearch(arr, 150));

        System.out.println(Arrays.binarySearch(arr, 81));
    }

    public static int binarySearch(int[] arr, int data){
        // 1、定义两个变量，一个站在左边位置，一个站在右边位置
        int left = 0;
        int right = arr.length - 1;

        // 2、定义一个循环控制折半。
        while (left <= right) {
            // 3、每次折半，都算出中间位置处的索引
            int middle = left + ((right - left) >> 1);
            // 4、判断当前要找的元素值，与中间位置处的元素值的大小情况。
            if (data < arr[middle]) {
                // 往左边找，截止位置（右边位置） = 中间位置 - 1
                right = middle - 1;
            } else if (data > arr[middle]) {
                // 往右边找，起始位置（左边位置） = 中间位置 + 1
                left = middle + 1;
            } else {
                // 中间位置处的元素值，正好等于我们要找的元素值
                return middle;
            }
        }
        return -1; // -1特殊结果，就代表没有找到数据！数组中不存在该数据！
    }
}