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

news/2024/4/24 21:46:32/

关注公众号:”奇叔码技术“
回复:“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-icount++;                 //统计比较次数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-icount++;                 //统计比较次数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-icount++;                       //统计比较次数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
下篇来临!


http://www.ppmy.cn/news/48324.html

相关文章

大数据数仓维度建模

目录 维度建模分为三种&#xff1a; 1、星型模型&#xff1a; 2、雪花模型&#xff1a; 3、星座模型&#xff1a; 模型的选择&#xff1a; 维度表和事实表&#xff1a; 维度表&#xff1a; 维度表特性 &#xff1a; 事实表&#xff1a; 事实表特性&#xff1a; 事务型…

KDXJ-8 SF6气体泄漏报警在线检测系统

一、功能特点 1. 定量测量SF6&#xff08;六氟化硫&#xff09;气体浓度&#xff1b; 2. 定量测量O2&#xff08;氧气&#xff09;气体浓度&#xff1b; 3. 定量测量大气温湿度&#xff1b; 4. 可根据需要设置SF6和O2气体浓度的报警点&#xff1b; 5. 后台监控&#xff1b; 6.…

电脑不限时长的录屏软件分享

案例&#xff1a;有没有录屏软件不限时长录制视频&#xff1f; “今天的视频会议特别重要&#xff0c;我想用录屏的方式记录下来。在网上下载了一个录屏软件&#xff0c;录到3分钟的时候&#xff0c;需要解锁高级功能才能继续录制。想问问大家有没有电脑免费不限时长的录屏软件…

\r与\n详解

在 C 语言中&#xff0c; 回车符可以用 “\r” 来表示&#xff0c; 换行符可以用 “\n” 来表示。 例如&#xff0c;在代码中使用 printf() 函数输出 “Hello\r\nWorld”&#xff0c;那么输出的结果将会是&#xff1a; Hello World其中&#xff0c;"\r\n" 表示一个回…

根据身份证号码判断是否是未成年人

/**** * 根据身份证号计算年龄 * param str * param currDate * return */ public boolean calcYear(String str, Date currDate){ DateFormat dateFormat new SimpleDateFormat("yyyyMMdd"); Long year Long.par…

ESP32学习笔记14-mqtt-连接官方mqtt,onenet,thingsboard物联网平台

12.MQTT 12.0工程里的WiFi密码和ssid设置 工程的WiFi配置 ssid password 打开配置 配置ssid和密码 工程配置文件sdkconfig IP和端口配置 乐鑫服务器mqtt 12.1数据结构和配置函

DQL查询语言(2)

目录 一交叉连接&#xff1a; 交叉连接的基本格式&#xff1a; 交叉连接的基本格式 笛卡尔积: 带条件的交叉连接: 二、内连接&#xff1a; 内连接的基本格式&#xff1a; 不带条件的内连接: 内连接和交叉连接的区别: 三、外连接&#xff1a; 1、左外连接&#xff08;简…

如今的就业环境下,怎样才能跻身于高收入的IC行业?

看到不少人失业找工作&#xff0c;其实现在不光是大学生难找工作&#xff0c;在职的人工作也不怎么开心。 要么累&#xff0c;要么没前途。 要么又累又没前途。 总的占个啥吧&#xff0c;现在大家面临的问题就是工作时间越来越久&#xff0c;人际关系也搞得很压抑&#xff0…

C嘎嘎~~【初识C++ 上篇】

初识C 上篇 &#x1fac5;1. C关键字&#x1fac5; 2.命名空间&#x1f937;‍♂️2.1命名空间的定义&#x1f937;‍♂️2.2命名空间的使用 &#x1fac5; 3.C输入 & 输出 转眼间&#xff0c; 就进入C这个新的篇章啦&#xff01; 我带着些许心悸 和 激动&#xff1a; 心悸…

借鉴《观沧海》作现代爱情诗一篇

《观星空》 浩瀚的星空&#xff0c;闪耀着无尽的光芒&#xff0c; 拥抱着几许的寂寥和宁静&#xff0c; 而你&#xff0c;如同在我心中灿然闪耀的繁星&#xff0c; 指引着我前行的方向。 天地万物&#xff0c;都有着各自的轨迹&#xff0c; 同样&#xff0c;我们也因着时空的巧…

大小字母转换

1.代码实例: public class UpString { public static void main(String[] args) { if(args!null && args.length 1){ String str new String(args[0]); System.out.println(“原字符&#xff1a;” str “\n”); String newA str.toUpperCase(); System.out.prin…

计算机网络科普

文章目录 1、集线器2、CSMA/CD协议3、交换机3.1 交换机的桥接 4、 路由器4.1 关于网关 5、 路由表6、IP地址6.1 DNS 7、MAC地址8、ARP协议9、关于网络层次模型10、路由器11、猫/光猫 1、集线器 计算机之间的相互通信&#xff0c;你会怎么设计&#xff1f; 如果是两台计算机&…

手机端无线投屏技术及方案推荐

目前主流的无线投屏技术主要又DLNA&#xff0c;Miracast&#xff0c;Airplay。 对协议的描述引用知乎作者的文章&#xff0c;原文&#xff1a;AirPlay、Miracast 、DLNA三大协议对比 - 知乎 (zhihu.com) 【DLNA】 DNLA&#xff0c;Digital Living Network Alliance&#xff…

LeetCode 1218. Longest Arithmetic Subsequence of Given Difference【哈希表,动态规划】中等

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…

nodejs扫描文件夹搜索包含关键词文件,可灵活配置

代码放在在末尾 文件说明&#xff1a; 关键代码&#xff1a;search.js 搜索结果&#xff1a;searchResult.txt 搜索日志&#xff1a;search.log 注&#xff1a;只保留一次的&#xff0c;需要多次自行修改logFile配置即可&#xff1b; 使用方式&#xff1a; 将代码放到需要…

容器内无tcpdump,如何在宿主机上抓容器的包

抓包的容器里&#xff0c;没有安装tcpdump 命令&#xff0c;我们可以去容器所在宿主机上&#xff0c;使用 nsenter 命令切换网络命名空间后&#xff0c;使用宿主机上的tcpdump 命令&#xff0c;对容器进行抓包分析。 此例中&#xff0c;我要抓取容器中端口是5240的包&#xff…

【论文阅读】CVPR2023 IGEV-Stereo

用于立体匹配的迭代几何编码代价体 【cvhub导读】【paper】【code_openi】 代码是启智社区的镜像仓库&#xff0c;不需要魔法&#xff0c;点击这里注册 &#x1f680;贡献 1️⃣现有主流方法 基于代价滤波的方法和基于迭代优化的方法&#xff1a; 基于代价滤波的方法可以在c…

(转)使用Midjourney进行图生图

原文链接:使用Midjourney进行AI绘画的基础手册-虎课网 接下来,我们讲一下,如果使用Midjourney的垫图功能,创作相同风格的图片 第一步: 1、打开discord,查看自己的服务器 2、我们双击“+”,来上传图片,图片上传后,按下enter发送图片; 图片发送成功后,点击图片放大…

nginx部署VUE项目

前言 目前公司的前端代码基本都是部署在nginx下&#xff0c;特此来记录一下 开发环境&#xff1a;window10 nginx环境搭建&#xff08;参考下方文章&#xff09; window环境安装 mac环境安装 本地我将nginx放置于F盘 前端项目打包 一个nginx服务下可能会放置多个前端包&…

Keil系列教程03_主窗口和工具栏详细说明

1写在前面 本文先让大家简单认识一下Keil的主窗口界面&#xff0c;然后再进一步认识Keil的文件、编译和调试工具栏。 Toolbars工具栏就是在菜单下面的两行快捷图标按钮&#xff0c;这些快捷按钮之所以在工具栏里面&#xff0c;在于它们使用的频率较高。比如保存按钮、编译按钮…