冒泡排序实现思路及优化

news/2024/3/28 17:46:42/文章来源:https://blog.csdn.net/zlpzlpzyd/article/details/129700907

冒泡排序,即一个无序的数组中,经过处理的数组后面的元素比前一个大。

int[] arr = new int[]{6, 2, 1, 3, 5, 4};

判断条件

arr[j] < arr[j + 1]

要做到这个,在程序中实现需要通过循环外加一个临时变量来处理

if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;
}

考虑到数组里的元素顺序发生变化,一般一次完整下来无法达到目的,数组 arr 一个完整循环排序下来的结果是

[2, 1, 3, 5, 4, 6]

显然1和2,5和4还不能满足,所以需要一个外层循环来处理这个问题

for (int i = 0; i < arr.length; i++) {for (int j = 0; j < arr.length - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}
}

至此,一个简单的冒泡排序结束。

看一下哪里可以有优化的地方

从循环次数入手

发现外层循环总共30次。循环次数多意味着计算量大,消耗cpu高

减少外层循环次数

外层循环第一次排序后的数组依次为

[2, 6, 1, 3, 5, 4]
[2, 1, 6, 3, 5, 4]
[2, 1, 3, 6, 5, 4]
[2, 1, 3, 5, 6, 4]
[2, 1, 3, 5, 4, 6]

即6个元素遍历了5次,有一次不用循环

for (int i = 0; i < arr.length-1; i++) {for (int j = 0; j < arr.length - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}
}

这次循环次数为25次,(30-25)/30*100≈17%,即提升了 17%

鉴于第一次外层循环结束后,数组最后一个值是最大的,接下来下来只需要对前面的5个元素进行比较

内层循环在现有的基础上减少外层循环次数

在上面优化的基础上,在外层循环的基础上数组后面的大小都是已经固定的。接下来每次外循环下来内循环只需要对数组未进行正常排序的进行处理即可。

for (int i = 0; i < arr.length -1; i++) {int len = arr.length - 1 -i;for (int j = 0; j < len; j++) {// 5 > 3if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}
}

这次循环次数为15次,(30-15)/30*100=50%,即相对原始算法提升了 50%,相对于第一次优化后 (25-15)/25=40%,即提升了40%

这是这两种都无法解决重复判断的问题

把内循环的判断提到 for 循环条件上

代码如下

for (int i = 0; i < arr.length -1; i++) {int len = arr.length - 1 -i;for (int j = 0; j < len && arr[j] > arr[j + 1]; j++) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}
}

这次循环次数为6次,解决了重复循环的问题,(30-6)/30*100=80%,即相对原始算法提升了 80%,相对于第二次优化后 (15-6)/15=60%,即提升了60%

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

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

相关文章

本地资源检测|单规则多阈值设置功能上线

作为一款可以全面自动检测项目静态工程内各项资源、代码和设置的UWA服务&#xff0c;本地资源检测能够帮助项目组制定合理的资源与代码标准&#xff0c;及时发现潜在的性能问题和异常错误&#xff0c;建立有效的开发规范意识。 此次3.1.0版本更新&#xff0c;在优化和完善现有…

Rcpp包运行C++代码

提高 R 脚本性能的最简单、最快捷的方法是更改脚本的问题部分并用 C 重写它们。Rcpp包提供了 R 和 C 之间的接口。1. cppFunction()转换简单的C函数### 1. cppFunction()转换简单的C函数 library(Rcpp) cppFunction(codeint fibonacci(const int x){if(x < 2) return x;if(x…

项目日记:学成在线(第二天P24~p34)

1、注入的两种方式&#xff1a;Autowired、Resource&#xff08;基于类型和名称&#xff09; 相同&#xff1a; Resource和Autowired都是做bean的注入时使用 不同&#xff1a; ①Autowird 属于spring框架,默认使用类型(byType)进行注入&#xff1a;&#xff08;基于类型&#x…

堆溢出——unlink漏洞攻击(bamboobox)

题目自取&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1S9xbAWhFw0xFqFyQTACqLA?pwdvvud 提取码&#xff1a;vvud 介绍&#xff1a; 终于学到Unlink了&#xff0c;不得不说和栈的难度相比确实大了很多&#xff0c;学起来确实很淦&#xff0c;一个unlink漏洞也确…

VSCode配置git bash为默认终端

打开左下角齿轮图标 打开Settings 搜索框输入 terminal.integrated.profiles.windows, 在下方显示的内容上点击 Edit in settings.json 配置修改如下 "terminal.integrated.profiles.windows": {"PowerShell": {"source": "PowerShell&qu…

Python每日一练(20230322)

目录 1. Excel表列序号 &#x1f31f; 2. 单词拆分 &#x1f31f;&#x1f31f; 3. 删除有序数组中的重复项 II &#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 C/C每日一练 专栏 Java每日一练…

营销即服务!怎么做小程序店铺打造优质用户体验?

随着移动互联网的快速发展&#xff0c;小程序已经成为了许多企业打造优质用户体验的重要工具。一个好的小程序店铺能够为用户提供良好的购物体验&#xff0c;提高用户满意度和转化率。那么&#xff0c;怎么做小程序店铺打造优质用户体验呢&#xff1f; 一&#xff1a;做小程序店…

Linux 信号(signal):信号的捕捉流程

目录一、程序的运行状态二、信号捕捉流程在处理信号的时候&#xff0c;其实要经过一系列流程的&#xff0c;本文就来简单介绍一下信号处理的捕捉流程。 一、程序的运行状态 程序运行状态分为内核态和用户态。程序在运行库函数、用户自定义函数等第三方函数时就会在用户态运行&…

VSCode for C/C++ 插件

VSCode for C/C 插件功能性插件C/C【千万级下载&#xff01;】必选C/C Extension Pack【千万级下载&#xff01;】扩展包Code Runner【千万级下载&#xff01;必备】右键代码运行&#xff0c;格式化在终端的显示CMake、 CMake Integration、CMake Language Support、CMake Tool…

达梦数据库普通表转分区表

在生产环境中&#xff0c;数据库中一开始用的是普通表&#xff0c;但随着时间推移&#xff0c;数据量越来越大&#xff0c;可以考虑将普通表转换为分区表&#xff0c;提升数据库的性能。本文将介绍在DM8数据库中&#xff0c;实现将普通表转换为分区表的方法。环境说明数据库版本…

SpringBoot基础教程

springboot基础 一、springboot介绍 Spring Boot 提供一种快速使用spring的方式&#xff0c;基于约定大于配置的思想&#xff0c;可以让开发者不必在配置与逻辑业务中来回进行思维切换&#xff0c;全身心的投入到业务的代码编写中&#xff0c;从而大大提高了开发效率。2014年…

TypeScript的枚举与类型约束

● 上一章我们讲了 TS 的接口 ● 这一章, 我们就来聊一聊 TS 的枚举和约束 枚举 认识枚举 ● 在很多计算机语言中都有枚举的概念, 但是 JS 中是没有枚举这个概念的, 为了弥补这个缺憾 在 TS 加入了枚举类型 ● 什么是枚举呢 ? 枚举( mei ju ) : 枚举的意思就是一一列举,…

PyTorch 深度学习实战 | 基于 ResNet 的花卉图片分类

“工欲善其事&#xff0c;必先利其器”。如果直接使用 Python 完成模型的构建、导出等工作&#xff0c;势必会耗费相当多的时间&#xff0c;而且大部分工作都是深度学习中共同拥有的部分&#xff0c;即重复工作。所以本案例为了快速实现效果&#xff0c;就直接使用将这些共有部…

【C++初阶】六、模板初阶(函数模板+类模板)

文章目录泛型编程函数模板函数模板的概念函数模板的格式函数模板的原理函数模板的实例化模板参数的匹配原则类模板类模板的定义格式类模板的实例化泛型编程 引入 - 通用的交换函数 如果让你编写一个函数&#xff0c;用于两个数的交换。在C语言中&#xff0c;我们会用如下方法…

我让Chat GPT准备了几份SAP 顾问英文面试自我介绍的模板,大家感受一下

有个朋友说有个面试要用英文来做自我介绍&#xff0c;我灵机一动&#xff0c;不如让Chat GPT准备了几份SAP 顾问英文面试自我介绍的模板&#xff0c;大家感受一下。我看下来感觉写的还是中规中矩&#xff0c;可以一用&#xff0c;。 模板1 Sure, I can help you with that! Her…

【Java学习笔记】39.Java 多线程编程

Java 多线程编程 Java 给多线程编程提供了内置的支持。 一条线程指的是进程中一个单一顺序的控制流&#xff0c;一个进程中可以并发多个线程&#xff0c;每条线程并行执行不同的任务。 多线程是多任务的一种特别的形式&#xff0c;但多线程使用了更小的资源开销。 这里定义和…

navigator 拓宽前端视野

前言&#x1f490; 写本文的起因是最近做了一个共享屏幕在线演示ppt的需求&#xff0c;发现了navigator的新大陆。原来web端开启屏幕共享是如此的简单&#xff0c;在接触之前还以为是多么高大上的功能,需求评审时内心还有些慌张。 人总是对自己不了解的东西心生恐惧&#x1f6…

VMware虚拟机卸载详细教程

安装过VMware虚拟机的小伙伴&#xff0c;90%可能都会遇到这样的问题&#xff1a;安装容易&#xff0c;卸载难。而且卸载不干净&#xff0c;就会导致后续安装和使用出现各种Bug。今天就给大家详细说说如何彻底干净的从本机卸载VMware。 1. 卸载之前&#xff0c;需要先关闭VMware…

【ChatGPT】Notion AI 从注册到体验:如何免费使用

欢迎关注【youcans的GPT学习笔记】原创作品&#xff0c;火热更新中 【ChatGPT】Notion AI 从注册到体验1. Notion AI 介绍1.1 Notion AI 简介1.2 Notion AI 的核心能力1.3 Notion AI 与 ChatGPT 的比较2. Notion AI 国内用户注册2.1 PC 端用户注册2.2 移动端用户注册3. Notion …

如何用C语言实现渣男通讯录

注意&#xff1a;纯属玩笑&#xff0c;博大家一乐&#xff0c;切勿当真&#x1f4d6;首先我们要知道一个渣男通讯录有哪些信息要包含哪些功能1.你的通讯录要装多少个女朋友你得规定吧&#xff1b;2.每个女朋友的姓名&#xff0c;年龄&#xff0c;电话&#xff0c;爱好这些要有吧…