大厂面试-算法优化:冒泡排序你会优化吗?

关注公众号:”奇叔码技术“
回复:“java面试题大全”或者“java面试题”
即可领取资料

原文:冒泡排序及优化代码

https://blog.csdn.net/weixin_43989347/article/details/122025689

原文:十大经典排序算法


https://frxcat.fun/pages/eab19d/

内容分为:

1、总结算法思路

2、冒泡排序算法演示图

3、冒泡排序算法可运行代码

4、大厂面试会问到算法和算法优化

一、总结算法思路

冒泡排序是经典算法了,它的时间复杂度:最好O(n),最坏O(n^2)。

接下来直接说明它的优化算法思路:


自己理解:

第一次优化是指:如果内层循环经过一轮的比较,没有进入if判断语句进行交换,则代表后续的元素已经排好序了,已经是小的在前面,大的在后面,则也就证明了不用下一轮的比较了,直接退出循环,返回结果。


第二次优化是指:在原有第一次优化的基础上进行记录,经过内层循环的一轮比较,进入if判断语句,第j个数和第j+1个数比较,记录进行交换的交换位置的第j个数。内层循环一轮比较完毕之后,记录的第j个数,证明了,该数后面的数都已经排好序了,无序再进行排序。则下一轮的内层循环比较的最大索引位置就是第j个数,依此类推。


原作者的理解:

第一次优化:经过一轮的比较,如果没有交换,说明已经排好序了

第二次优化:记录每次最后一次交换的位置,说明这个位置往后,都是已经排好序了;那么下轮比较时,只需要比较到上次记录索引的位置即可。

二、冒泡排序算法演示图

冒泡排序

三、冒泡排序算法可运行代码

//冒泡排序,最好的O(n),最坏的O(n^2)
//第一次优化是指,如果内层循环经过一轮的比较,没有进入if判断语句进行交换,则代表后续的元素已经排好序了,已经是小的在前面,大的在后面,则也就证明了不用下一轮的比较了,直接退出循环,返回结果。
//第二次优化是指,再原有第一次优化的基础上进行记录,经过内层循环的一轮比较,进入if判断语句,第j个数和第j+1个数比较,,记录进行交换的交换位置的第j个数,
//内层循环一轮比较完毕之后,记录的第j个数,证明了,该数后面的数都已经排好序了,无序再进行排序。则下一轮的内存循环比较的最大索引位置就是第j个数,以此类推。
//原作者的理解:
//第一次优化:经过一轮的比较,如果没有交换,说明已经排好序了
//第二次优化:记录每次最后一次交换的位置,说明这个位置往后,都是已经排好序了;那么下轮比较时,只需要比较到上次记录索引的位置即可。


/*
 * n是数组个数,i代表循环次数,j代表每轮比较次数,count是算法一共比较的次数,
 * 冒泡排序:例子是从小大到排序
 *
 * 规律:
 *   从第一个数,依次往后进行比较,若第一个大于第二个数,则交换。(稳定排序)
 *   每一轮for循环,比较出一个最大或最小的数,放在确定的位置。

 *
 *
 * */
public class BulleSort {
    public static void main(String[] args) {
        bubble1();
        /*
        * bubble1();
        * 循环次数:
        *   n-1次    比如3个数,最多只需要循环2次,就可以得出结果
        * 每轮比较次数:
        *   n-1-i次  第一轮比较n-1,第二轮比较n-2,最后一轮比较n-1-(n-2)=1次
          这个算法,是固定循环n-1次,并且固定每轮比较次数:[n*(n-1)]/2
        * 缺点:
           当出现只需要交换一次的数组:{2,1,3,4,5},再用上面方法就资源浪费了
            排序前:
            2,1,3,4,5,
            排序后:
            1,2,3,4,5,
            总共比较次数:10  //优化后其实只需要比较7次就可以了
        */

       bubble2();
        /*
        * 优化:
        *   减少不必要的循环和比较次数。
        * 目标:
        *   数组{2,1,3,4,5},只需要循环2次,比较前两次循环的次数:(n-1)+(n-2)
        * 结果:
            排序前:
            2,1,3,4,5,
            排序后:
            1,2,3,4,5,
            总共比较次数:7

        */
        bubble3();
        /*
        * 经过上面的优化,可以将固定的比较次数,减少到循环2次,比较前两次循环次数
        * 那么有没有更好的优化方法呢?
           比如只要循环一次,就可以知道下次从没有确定最终位置的地方开始
        * 目标:
        *  1:数组{2,1,3,4,5},只需要循环1次,比较第1次循环的次数:(n-1)
        *  2:数组{1,2,3,5,4},只需要循环2次,比较前两次即可,是因为方法buble2()的test=1/0
        * 方法:
        *   记录每次最后一次交换的位置,说明这个位置往后,都是已经排好序了
        *   那么下轮比较时,只需要比较到上次记录索引的位置即可。
        *
        * */

    }

    public static void bubble3(){
        System.out.println("\n"+"方法三:每次循环,只需要比较未确定最终位置的数");
        int count=0;                        //总共比较次数
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};           //排序的数组
        int n = arr.length;                 //数组中有几个数

        int test = 0;
        /*如果某一次循环,没有交换,那就是已经排好序了。那么就退出。
        1假如可能排好序了,0代表肯定没有排好序 */
        int p1=0;   // 记录最后一次交换位置
        int p2=n-1;
        /*由于j循环,每次都需要判断j的本次i轮循环的最大比较位置
        所以需要引出p2,来通过本次确定已经排好序的位置,
        下次i轮循环时,j需要比较最大索引位置即可
        那么初始化,第一次比较次数应该是n-1次*/

        System.out.print("排序前:");
        print_Array(arr, n);                //打印数组

        //冒泡排序算法:
        for (int i = 0; i < n-1; i++) {        //一共循环n-1次
            test=1;                            //默认排好序了
            for (int j = 0; j < p2; j++) {  //比较n-1-i
                count++;                 //统计比较次数
                if(arr[j]>arr[j+1]) {          //第一个数和第二个数比较
                    test =0;                   //说明目前没有排好序
                    swap(arr,j,j+1);       //若第j个数大于第j+1个数,则交换
                    p1 = j;
                }
            }
            p2=p1;
            //下一轮比较的最大索引位置

            if(test==1) break;
            //经过一轮的比较,如果没有交换,说明已经排好序了
            p_Array(arr,n,i);                    //每轮循环的数组
        }
        System.out.print("排序后:");
        print_Array(arr, n);
        System.out.println("总共比较次数:"+count);
    }

    public static void bubble2(){
        System.out.println("\n"+"方法二:假如一次循环都没有交换,则说明已排好序");
        int test = 0;
        //如果某一次循环,没有交换,那就是已经排好序了。那么就退出。
        //1假如可能排好序了,0代表肯定没有排好序
        int count=0;                        //总共比较次数
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};           //排序的数组
        int n = arr.length;                 //数组中有几个数
        System.out.print("排序前:");
        print_Array(arr, n);                //打印数组

        //冒泡排序算法:
        for (int i = 0; i < n-1; i++) {        //一共循环n-1次
            test=1;                            //默认排好序了
            for (int j = 0; j < n-1-i; j++) {  //比较n-1-i
                count++;                 //统计比较次数
                if(arr[j]>arr[j+1]) {          //第一个数和第二个数比较
                    test =0;                   //说明目前没有排好序
                    swap(arr,j,j+1);       //若第j个数大于第j+1个数,则交换
                }
            }
            p_Array(arr,n,i);                    //每轮循环的数组
            if(test==1) break;
            //经过一轮的比较,如果没有交换,说明已经排好序了
        }

        System.out.print("排序后:");
        print_Array(arr, n);
        System.out.println("总共比较次数:"+count);
    }

    public static void bubble1(){
        System.out.println("方法一:未优化");
        int count=0;         //统计一共比较多少次数
        int[] arr = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};           //排序的数组
        int n = arr.length;  //数组中有几个数
        System.out.print("排序前:");
        print_Array(arr, n);          //打印数组

        //冒泡排序算法:
        for (int i = 0; i < n-1; i++) {        //一共循环n-1次
            for (int j = 0; j < n-1-i; j++) {  //比较n-1-i
                count++;                       //统计比较次数
                if(arr[j]>arr[j+1]) {          //第一个数和第二个数比较
                    swap(arr,j,j+1);       //若第j个数大于第j+1个数,则交换
                }
            }
            p_Array(arr,n,i);                    //每轮循环的数组
        }

        System.out.print("排序后:");
        print_Array(arr, n);          //打印数组
        System.out.println("总共比较次数:"+count);
    }


    //打印数组
    private static void print_Array(int[] arr, int length) {
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.println();
    }
    //交换数组中两个数的位置
    public static void swap(int[] a,int a0,int a1){
        int temp = a[a0];
        a[a0] = a[a1];
        a[a1] = temp;
    }

    //打印每循环一轮的数组
    public static void p_Array(int[] arr,int length,int i1){
        System.out.print("第"+(i1+1)+"轮循环的数组:");
        for (int i = 0; i < length; i++) {
            System.out.print(arr[i] + ",");
        }
        System.out.println();
    }
}

四、大厂面试会问到算法和算法优化:

冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

作为最简单的排序算法之一,冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。


1.算法步骤

比较相邻的元素。如果第一个比第二个大,就交换他们两个。

对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

针对所有的元素重复以上的步骤,除了最后一个。

持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。



2.算法优化

(1)记录进入if判断语句中比较之后的最后一次索引位置作为下一次内层循环的结束下标。

(2)记录没有进入if判断语句的flag标志,表明排序已完毕,无序再比较,退出循环,结束。


五、最后!!!

点赞
评论
关注我

END
下篇来临!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/14184.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

史上最详细的八大排序详解!(建议收藏)

&#x1f680;write in front&#x1f680; &#x1f4dc;所属专栏&#xff1a;初阶数据结构 &#x1f6f0;️博客主页&#xff1a;睿睿的博客主页 &#x1f6f0;️代码仓库&#xff1a;&#x1f389;VS2022_C语言仓库 &#x1f3a1;您的点赞、关注、收藏、评论&#xff0c;是对…

问题排查记录-ffmpeg链接libavfilter和libavcodec:未定义的引用

目录 一、问题背景 二、问题现象 2.1 ffmpeg测试例程 2.2 编译脚本 2.3 错误提示 三、问题排查 3.1 关于提示找不到“stdio" "iostream"头文件的问题 3.1.1查看工具链头文件检索位置 3.1.2 根据工具链路径查找头文件 3.1.3 在编译脚本中指定头文件路径…

第一章 Maven概述

第一节 为什么要学习Maven&#xff1f; maven-作为依赖管理工具 ①jar 包的规模 随着我们使用越来越多的框架&#xff0c;或者框架封装程度越来越高&#xff0c;项目中使用的jar包也越来越多。项目中&#xff0c;一个模块里面用到上百个jar包是非常正常的。 比如下面的例子…

Flex布局

flex是 W3C 提出的一种新的布局方案 当我将某一元素设置为 display&#xff1a;flex 时&#xff0c;这个元素所包含的直接子元素就成为了我的子民 但是我发现我无法控制我的子民&#xff0c; 首先我要解决的是我要控制子民的方向 flex-direction: row 以行排列row-reverse…

Linux-初学者系列2——用户组管理和权限管理

用户组管理和权限管理 Linux-初学者系列2_用户组管理和权限管理一、所有者1、查看文件的所有者指令 2、修改文件所有者指令实操 二、组创建语法指令&#xff1a;实操&#xff1a; 三、所在组1、查看文件/目录所在组基本指令&#xff1a;实操&#xff1a; 2、修改文件所在组基本…

在当前互联网行情下,Android想转音视频开发,会有前景吗?

前言 近年来&#xff0c;由于三年疫情的影响&#xff0c;很多公司都开始陆陆续续的在裁员&#xff0c;Android开发工作岗位也是&#xff0c;可能有些从事Android开发的朋友还没有意识到&#xff0c;Android开发岗位正在变少&#xff0c;求职者&#xff0c;僧多粥少&#xff0c…

020:Mapbox GL加载高德地图(影像瓦片图)

第020个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中加载高德地图(影像瓦片图)。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共80行)相关API参考:专栏目标示例效果 配置方式 1)查看基础设置:…

在金融领域使用机器学习的 9个技巧

机器学习已经倍证明可以预测结果和发掘隐藏的数据模式。但是必须小心使用&#xff0c;并遵循一些规则&#xff0c;否则就会在数据的荒野中徘徊而无所获。使用机器学习进行交易的道路充满了陷阱和挑战&#xff0c;只有那些勤奋认真地遵循规则的人才能从中获得收益。下面是一些技…

235:vue+openlayers 绘制带有径向渐变填充色的圆形

第235个 点击查看专栏目录 本示例的目的是介绍如何在vue+openlayer中绘制带有径向渐变填充色的圆形。 如果填充线性渐变的多边形,可以参考这个篇文章 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共136行)相关A…

像素是什么

像素分为设备像素和设备无关像素。 下面说说来龙去脉。 一、显示器 显示图像的电子设备。 &#xff08;一&#xff09;显示器种类 1.LCD LCD&#xff08;Liquid crystal display&#xff09;&#xff0c;是液体晶体显示&#xff0c;也就是液晶显示器&#xff0c;LCD具有功耗低…

HTB靶机-Lame-WP

Lame 简介&#xff1a; Lame is a beginner level machine, requiring only one exploit to obtain root access. It was the first machine published on Hack The Box and was often the first machine for new users prior to its retirement Tags&#xff1a; Injection, C…

5.5G的关键一跳!将数智未来照进现实

编辑&#xff1a;阿冒 设计&#xff1a;沐由 作为数字时代的三大思想家之一&#xff0c;乔治吉尔德在1993年就指出&#xff0c;未来25年内主干网的带宽每6个月增长一倍&#xff0c;其增长速度是摩尔定律预测的CPU增长速度的3倍。 这就是著名的吉尔德定律&#xff08;Gilder’s …

搞懂 API ,地图 API 制作方法分享

地图 API 是一种基于 Web 开发的应用程序编程接口&#xff0c;可以用于创建和展示地图及地理信息。以下是一些地图 API 制作的方法&#xff1a; 选择地图 API 平台&#xff1a;目前市场上有很多地图 API 平台供选择&#xff0c;比如 Google Maps API、百度地图 API、高德地图 A…

Ubuntu 23.04 正式发布

Ubuntu 23.04 “Lunar Lobster” 是 Ubuntu 操作系统的最新短期支持版本&#xff0c;该版本将获得 9 个月的支持&#xff0c;直到 2024 年 1 月。如果你需要长期支持&#xff0c;建议使用 Ubuntu 22.04 LTS 代替。 Linux 内核 Ubuntu 23.04 采用了新的 Linux 6.2 内核。 值得注…

FPGA基于XDMA实现PCIE X8视频采集HDMI输出 提供工程源码和QT上位机程序和技术支持

目录 1、前言2、我已有的PCIE方案3、PCIE理论4、总体设计思路和方案5、vivado工程详解6、驱动安装7、QT上位机软件8、上板调试验证9、福利&#xff1a;工程代码的获取 1、前言 PCIE&#xff08;PCI Express&#xff09;采用了目前业内流行的点对点串行连接&#xff0c;比起 PC…

JUC概述

1. JUC是什么&#xff1f; 在 Java 5.0 提供了 java.util.concurrent(简称JUC)包&#xff0c;在此包中增加了在并发编程中很常用的工具类。此包包括了几个小的、已标准化的可扩展框架&#xff0c;并提供一些功能实用的类&#xff0c;没有这些类&#xff0c;一些功能会很难实现或…

单链表——“数据结构与算法”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰的内容终于是我们心心念念的单链表啦&#xff0c;这一块呢&#xff0c;是一个很重要的部分&#xff0c;也是一个对目前的我来说&#xff0c;比较困难的部分&#xff0c;下面&#xff0c;就让我们进入单链表的世界吧 之…

【linux】对于权限的理解

权限 Linux权限的概念用户之间的切换 Linux权限管理文件权限操作文件的人Linux文件默认权限的设置权限掩码 所属组/其他删除拥有者创建的文件文件拥有者、所属组的修改修改文件拥有者修改文件所属组一次性修改拥有者和所属组 目录的执行权限 Linux权限的概念 首先&#xff0c;…

电脑怎么远程控制另一台电脑

要从一台电脑远程控制另一台电脑&#xff0c;您可以使用远程桌面软件。 以下是远程控制另一台电脑的步骤&#xff1a; 一、在两台电脑上安装远程桌面软件 有多种远程桌面软件可用&#xff0c;例如 Splashtop、微软远程桌面。 在远程电脑和本地电脑上分别安装软件。访问各自软…

【产品经理】系统上线自查清单

产品上线之前的准备工作&#xff0c;看起来简单&#xff0c;实际做起来是非常繁杂的&#xff0c;如果没有尽早考虑和准备&#xff0c;可能会手忙脚乱甚至导致产品延迟上线。 产品上线前的准备工作听起来简单&#xff0c;但实际做起来非常繁杂。除了要考虑用户需求、商业需求外&…