冒泡排序 + 二分查找 寻找数字

举报
游离 发表于 2023/02/23 19:20:20 2023/02/23
【摘要】 总体思路:要想查找某一个数字,我们最先想到的就是二分查找,但是二分查找有一个前提,数组的元素必须要是有序的,所以查找数字之前要进行数字排序冒泡排序思路冒泡排序是十分经典的排序方法,首先要知道有n个数字就意味着有n-1趟排序,趟数也决定了后面要进行的判断的次数,再进行判断每一趟排序要判断是否满足升序的条件,要是满足就进行交换前后的数字即可public static void bubbleSor...

总体思路:

要想查找某一个数字,我们最先想到的就是二分查找,但是二分查找有一个前提,数组的元素必须要是有序的,所以查找数字之前要进行数字排序

冒泡排序

思路

冒泡排序是十分经典的排序方法,首先要知道有n个数字就意味着有n-1趟排序,趟数也决定了后面要进行的判断的次数,再进行判断每一趟排序要判断是否满足升序的条件,要是满足就进行交换前后的数字即可

public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flg = true;
                }
            }
  
         }
    }
复制代码

优化

要是数组的元素已经是升序的,这样子的运行效率就不会很好了,所以可以设一个标示量flg,通过判断它的状态,进行代码的优化

 public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flg = false;//每一趟都要将flg置为false,所以要将flg=false放第一层for循环里面
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flg = true;
                }
            }
            if (flg == false) {
                return;     // 要是flg还是等于false,就是没交换,说明都满足升序,所以直接return或者break结束最外面的for循环
            }
        }

    }

复制代码

在解决了数组元素有序性的问题之后,我们就可以开始写二分查找了

二分查找

二分查找思路:

给定一个数组,首先求出数组的左右端数字的下标使之分别为l r,接着求出数组的中间元素arr[mid]


接着输入要查找的数字key

1.当arr[mid]>key时,说明key出现在arr[mid]左边,所以需要将 右下标r 进行左移,左移至mid-1处,进入循环再判断,直至 arr[mid]等于key或者 l 与 r 相等退出循环


2.当arr[mid] <key时,说明key出现在arr[mid]右边,所以需要将 左下标r 进行右移,有移至mid+1处,进入循环再判断,直至arr[mid]等于key或者 l 与 r 相等退出循环



3.要是数组中不存在要查找的数字,就直接返回一个-1

小细节

在求中间元素的下标时,可以使用mid=(l+r)/2 ,但是规定mid是int类型的,有可能有超出int表示的范围,使用可以写成mid=l+(r-l)/2 的形式来避免超出int的范围

原理如图,就是将r多出l的部分一切为二,将其加到 l 上即可使两者一样大


最终代码如下

//冒泡排序
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            boolean flg = false;//每一趟都要将flg置为false
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flg = true;
                }
            }
            if (flg == false) {
                return;     // 要是flg还是等于false,就是没交换,说明都满足升序,所以直接return或者break结束最外面的for循环
            }
        }

    }

    //二分查找
    public static int binarySearch(int[] arr, int key) {
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] > key) {
                r = mid - 1;
            } else if (arr[mid] < key) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 6, 3, 12, 45, 4};
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {  //多组输入要查找的数字
            int key = scanner.nextInt();
            bubbleSort(arr);//进行冒泡排序
            System.out.println(Arrays.toString(arr));//输出排序后的数组
            System.out.println(binarySearch(arr, key));
        }
    }
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。