【韩老师零基础30天学会Java 02】学会 2种冒泡排序 和 2种二分查找 递归与非递归

冒泡

小的往前移动

        int[] arr = {1, 3, 5, 2, 11, 3, 44, 2, 23, 5};

        //从 0 到，最大索引 - 1 (所以是小于 最大索引)
        for (int i = 0; i < arr.length - 1; i++) {
            //从 i + 1，循环到最大索引
            for (int j = i + 1; j < arr.length; j++) {
                //如果 前一个位置 > 后一个位置 就交换，
                // 保证 前一个位置是 最小
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

大的往后移动

内部排序:
指将需要处理的所有数据都加载到内部存储器中进行排序。包括(交换式排序法、选择
式排序法和插入式排序法)；

外部排序法：
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。包括(合并排序法和直接合并排序法)。

冒泡排序法
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素
的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

总结冒泡排序特点

1. 我们一共有5个元素

2. 一共进行了 4轮排序,可以看成
   是外层循环

3. 每1轮排序可以确定一个数的位
   置，比如第1轮排序确定最大数，第
   2轮排序，确定第2大的数位置，
   依次类推

4. 当进行比较时，如果前面的数
   大于后面的数，就交换

5. 每轮比较在减少 4->3->2->1
   分析思路->代码…

分析量排序
数组[24,69,80,57,13]
第1轮排序：目标把最大数放在最后
第1次比较[24,69,80,57,13]
第2次比较[24,69,80,57,13]
第3次比较[24,69,57,80,13]
第4次比较[24,69,57,13,80]

第2轮排序：目标把第二大数放在倒数第二位置
第1次比较[24,69,57,13,80]
第2次比较[24,57,69,13,80]
第3次比较[24,57,13,69,80]

第3轮排序：目标把第3大数放在倒数第3位置
第1次比较[24,57,13,69,80]
第2次比较[24,13,57,69,80]

第4轮排序：目标把第4大数放在倒数第4位置
第1次比较[13,24,57,69,80]

        //如果长度为 5，最大索引为 4
        int maxIndex = arr.length - 1;
        //循环 0 - 3，循环 4次。控制比较多少轮（没轮挑出一个最大值）

        for (int i = 0; i < maxIndex; i++) {
            
            //已经完成，一定要定义到里面
        	boolean haveFinished = true;

            //第一次 循环为 0 - 3，4次循环(4-0)。 第二次为：0-2，3次循环(4-1)。控制比较的次数。
            // 4-0,4-1,4-2，4-3 。 0 1 2 3 和 外层循环的 i 一样。
            for (int j = 0; j < maxIndex - i; j++) {
                //如果 第一个 比 第二个 大，就交换
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                    haveFinished = false;
                }
            }
            System.out.println("第" + (i + 1) + "轮比较：" + Arrays.toString(arr));
            //已经完成，还为true
            if (haveFinished == true) {
                //直接跳出
                break;
            }

        }
        System.out.println(Arrays.toString(arr));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

查找

二分 递归

public static void main(String[] args) {

        int[] arr = {1, 2, 3, 8, 9, 11};
        int key = 3;

        //{0, 1, 2, 3, 4} 长度是5，最大索引为4，中间索引为2。就是2 存的位置。。
        Integer index = binarySearch2(arr, key, 0, arr.length - 1);

        System.out.println(index);

    }

    private static Integer binarySearch2(int[] arr, int value, int low, int high) {

        //中间位置 为 (低位+高位) /2
        int mid = (low + high) >>> 1;

        //如果高位 < 低位了
        if (high < low) {
            //没查到
            return -1;
        }

        //如果中间位置的值 == value，太好了，查到了
        if (arr[mid] == value) {
            return mid;
        } else if (arr[mid] > value) {
            //{0, 1, 2, 3, 4}，中间值为2，要查的值为1，在左边
            //为： 低位 至 mid-1
            return binarySearch2(arr, value, low, mid - 1);
        } else {
            //arr[mid] < value
            //{0, 1, 2, 3, 4}，中间值为2，要查的值为3，在右边
            //为： mid+1 至 高位
            return binarySearch2(arr, value, mid + 1, high);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

二分 非递归

public static void main(String[] args) {

        int[] arr = {0, 1, 2, 3, 4};
        int key = 3;

        Integer index = binarySearch(arr, key);

        System.out.println(index);

    }

    private static Integer binarySearch(int[] arr, int value) {

        //{0, 1, 2, 3, 4} 长度是5，最大索引为4，中间索引为2。就是2 存的位置。

        //定义中间 索引
        Integer mid;
        //最大索引
        int maxIndex = arr.length - 1;
        //低位
        int low = 0;
        //高位
        int high = maxIndex;

        //循环条件，如果 高位 >= 低位，就一直循环，直到 高位<低位 结束
        while (high >= low) {//或 low

            //中间索引赋值。无符号又移动1位，就是 /2
            mid = (high + low) >>> 1;

            //最好的情况 查询到了
            if (arr[mid] == value) {
                return mid;
            } else if (arr[mid] > value) {
                //如果 中间的值 > 要查找的值，如：{0, 1, 2, 3, 4}，中间值为2，要查找的为1。在左边
                //结果在： 低位 至 中间值-1 位置，所以对高位重赋值
                high = mid - 1;
            } else {

                //如果 中间的值 < 要查找的值，如：{0, 1, 2, 3, 4}，中间值为2，要查找的为3。在右边
                //结果在： 中间值+1 至 高位，所以对 低位重新赋值
                low = mid + 1;
            }

        }

        //如果循环中 没有返回，那就是没查到
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49