Java 气泡排序详情(代码示例)
本篇文章给大家带来的内容是关于Java冒泡排序的详细介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
1、 导言
因为这是排序算法系列的第一篇文章,所以多啰嗦几句。
排序是很常见的算法之一,现在很多编程语言都集成了一些排序算法,比如Java 的Arrays.sort()方法,这种方式让我们可以不在乎内部实现细节而直接调用,在实际的软件开发当中也会经常使用到。但是站在开发者的角度而言,知其然必须知其所以然。多练练排序算法,不仅能够让我们知道一些排序方法的底层实现细节,更能够锻炼我们的思维,提升编程能力。现在很多技术面试也会涉及到基本的排序算法,所以多练习是有好处的。(推荐:Java视频教程)
文中涉及到的代码都是Java实现的,但是不会涉及到太多的Java语言特性,并且我会加上详细的注释,帮助你理解代码并且转换成你熟悉的编程语言。
常见的排序算法有以下10种:
- 冒泡排序、选择排序、插入排序,平均时间复杂度都是O(n2)
- 希尔排序、归并排序、快速排序、堆排序,平均时间复杂度都是O(nlogn)
- 计数排序、基数排序、桶排序,平均时间复杂度都是O(n + k)
在开始具体的排序算法讲解之前,先得明白两个概念:
- 原地排序:指的是在排序的过程当中不会占用额外的存储空间,空间复杂度为O(1)。
- 排序算法的稳定性:一个稳定的排序,指的是在排序之后,相同元素的前后顺序不会被改变,反之就称为不稳定。举个例子:一个数组 [3,5,1,4,9,6,6,12] 有两个6(为了区分,我把其中一个 6 加粗),如果排序之后是这样的:[1,3,4,5,6,6,9,12](加粗的 6 仍然在前面),就说明这是一个稳定的排序算法。
2. 言归正传
冒泡排序的思路其实很简单,一个数据跟它相邻的数据进行大小的比较,如果满足大小关系,就将这两个数据交换位置。一直重复这个操作,就能将数据排序。
举个例子,假如有数组 a[3,5,1,4,9,6],第一次冒泡的操作如下图所示:
重复进行这个操作,6次冒泡之后,数据排序完成。
根据这个思路,应该能很容易能够写出下面的代码实现冒泡排序:
public class BubbleSort { //data表示整型数组,n表示数组大小 public static void bubbleSort(int[] data, int n){ //数组大小小于等于1,无须排序 if (n data[j + 1],交换两个数据的位置 if (data[j] > data[j + 1]){ int temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; } } } } }
但是这个排序算法还可以进行优化,当冒泡操作已经没有数据交换的时候,说明排序已经完成,就不用在进行冒泡操作了。例如上面的例子,第一次冒泡之后,数据为 [3,1,4,5,6,9],再进行一次冒泡,数据变为 [1,3,4,5,6,9],此时已经完成了排序,就可以结束循环了。
所以针对这个数组的排序,上面的代码需要6次冒泡才能完成,其中有4次都是不需要的。所以可以对代码进行优化:
public class BubbleSort { //优化后的冒泡排序 //data表示整型数组,n表示数组大小 public static void bubbleSort(int[] data, int n){ //数组大小小于等于1,无须排序,返回空 if (n data[j + 1],交换两个数据的位置 if (data[j] > data[j + 1]){ int temp = data[j]; data[j] = data[j + 1]; data[j + 1] = temp; flag = true;//表示有数据交换 } } //如果没有数据交换,则直接退出循环 if (!flag) break; } } }
好了,冒泡排序的基本思路和代码都已经实现,最后总结一下:
- 冒泡排序是基于数据比较的
- 最好情况时间复杂度是O(n),最坏情况时间复杂度是O(n2),平均时间复杂度是O(n2)
- 冒泡排序是原地排序算法,并且是稳定的。
以上就是Java冒泡排序的详细介绍(代码示例)的详细内容,更多请关注php中文网其它相关文章!
上一篇: Python 冒泡排序算法的图形细节
推荐阅读
-
Java 随机生成身份证完整示例代码
-
35 岁实现财务*,腾讯程序员手握2300万提前退休?-1000万房产、1000万腾讯股票、加上300万的现金,一共2300万的财产。有网友算了一笔账,假设1000万的房产用于自住,剩下1300万资产按照平均税后20-50万不等进行计算,大约花上26-60年左右的时间才能赚到这笔钱。也就是说,普通人可能奋斗一辈子,才能赚到这笔钱。在很多人还在为中年危机而惶惶不可终日的时候,有的人的35岁,就已经安全着陆,试问哪个打工人不羡慕?但问题是有这样财富积累必然有像样的实力做靠山。没有人可以不劳而获。 看到这里,肯定有人说,那么对于普通人来说,卷可能真就成了唯一的出路。但是卷也有轻松的卷,“偷懒”的卷法,对于程序员而言,刨除掉一时无法改掉的开会传统占用的大部分时间,如何把有限的时间和精力放在真正重要的架构设计、需求设计上,而不是重复的造*,编码、改bug、手动测试。因此在科技改变生活的今天,学会使用AI工具成为程序员们的必备技能。 以全栈式全自动的软件开发工具飞算SoFlu软件机器人为例,作为全球首款面向微服务架构设计和最佳实践的软件机器人,SoFlu软件机器人改变了原来手工编码的作业模式,通过可视化拖拽方式以及参数配置就能实现等同于编写复杂代码的业务逻辑,在设计业务逻辑时就完成了微服务应用开发,做到“业务即图,图即代码”,实现“软件开发,十倍提效”。 而作为飞算SoFlu软件机器人的一个重要组成部分,FuncGPT(慧函数)支持所有类型函数创建。通过自然语言描述Java函数需求,实时生成高质量、高可读性的Java函数代码。生成代码可直接复制到IDEA,或一键导入Java全自动开发工具函数库。 FuncGPT(慧函数)具有五大核心能力: ● 自然语言:通过自然语言即可生成函数,降低软件开发门槛。 ● 秒级函数开发:全自动秒级开发函数,秒级完成,效率千倍提升。 ● 一站式函数开发应用:函数生成即可直接应用,效率、安全有保障。 ● 质量可靠:生成的函数代码符合业界规范、具备良好的可读性,符合最优解。 ● 灵活生成:可以根据开发人员的具体需求生成并支持调整和修改。 以“将文件流转换为File对象”这个需求为例,以下是FuncGPT(慧函数)秒级生成的代码: / 类名:FileConverter // 函数名:convertStreamToFile // 函数功能:将文件流转换为File对象 // POM依赖包:无 import java.io.File; import java.io.FileOutputStream; import java.io.IOException; import java.io.InputStream; public class FileConverter { /** * 将文件流转换为File对象 * @param inputStream 文件流 * @param filePath 文件路径 * @param fileName 文件名 * @return 转换后的File对象 * @throws IOException 如果发生I/O异常 */ public static File convertStreamToFile(InputStream inputStream, String filePath, String fileName) throws IOException { File file = new File(filePath + File.separator + fileName); // 创建File对象 try (FileOutputStream outputStream = new FileOutputStream(file)) { // 创建文件输出流 byte buffer = new byte[1024]; int bytesRead; while ((bytesRead = inputStream.read(buffer)) != -1) { // 从文件流读取数据并写入文件 outputStream.write(buffer, 0, bytesRead); } } return file; // 返回转换后的File对象 } } // 函数示例 // 将文件流转换为File对象示例 // 入参:inputStream,文件流 // 入参:filePath,文件路径 // 入参:fileName,文件名 // 出参:file,转换后的File对象 // 调用示例: // InputStream inputStream = new FileInputStream("example.txt"); // String filePath = "C:\\Users\\User\\Documents"; // String fileName = "example.txt"; // File file = FileConverter.convertStreamToFile(inputStream, filePath, fileName); // System.out.println(file.getAbsolutePath); // 输出结果:例如,将文件流转换为File对象后,文件的绝对路径为:C:\Users\User\Documents\example.txt // 则输出结果为:C:\Users\User\Documents\example.txt 通过分析,不难发现以上代码:
-
Java Swing 树组件 JTree 使用示例详情
-
一种结构设计模式,允许在对象中动态添加新行为。它通过创建一个封装器来实现这一目的,即把对象放入一个装饰器类中,然后把这个装饰器类放入另一个装饰器类中,以此类推,形成一个封装器链。这样,我们就可以在不改变原始对象的情况下动态添加新行为或修改原始行为。 在 Java 中,实现装饰器设计模式的步骤如下: 定义一个接口或抽象类作为被装饰对象的基类。 公共接口 Component { void operation; } } 在本例中,我们定义了一个名为 Component 的接口,该接口包含一个名为 operation 的抽象方法,该方法定义了被装饰对象的基本行为。 定义一个实现基类方法的具体装饰对象。 公共类 ConcreteComponent 实现 Component { public class ConcreteComponent implements Component { @Override public void operation { System.out.println("ConcreteComponent is doing something...") ; } } 定义一个抽象装饰器类,该类继承于基类,并将装饰对象作为一个属性。 公共抽象类装饰器实现组件 { protected Component 组件 public Decorator(Component component) { this.component = component; } } @Override public void operation { component.operation; } } } 在这个示例中,我们定义了一个名为 Decorator 的抽象类,它继承了 Component 接口,并将被装饰对象作为一个属性。在操作方法中,我们调用了被装饰对象上的同名方法。 定义一个具体的装饰器类,继承自抽象装饰器类并实现增强逻辑。 公共类 ConcreteDecoratorA extends Decorator { public ConcreteDecoratorA(Component 组件) { super(component); } } public void operation { super.operation System.out.println("ConcreteDecoratorA 正在添加新行为......") ; } } 在本例中,我们定义了一个名为 ConcreteDecoratorA 的具体装饰器类,它继承自装饰器抽象类,并实现了操作方法的增强逻辑。在操作方法中,我们首先调用被装饰对象上的同名方法,然后添加新行为。 使用装饰器增强被装饰对象。 公共类 Main { public static void main(String args) { Component 组件 = new ConcreteComponent; component = new ConcreteDecoratorA(component); 组件操作 } } 在这个示例中,我们首先创建了一个被装饰对象 ConcreteComponent,然后通过 ConcreteDecoratorA 类创建了一个装饰器,并将被装饰对象作为参数传递。最后,调用装饰器的操作方法,实现对被装饰对象的增强。 使用场景 在 Java 中,装饰器模式被广泛使用,尤其是在 I/O 中。Java 中的 I/O 库使用装饰器模式实现了不同数据流之间的转换和增强。 让我们打开文件 a.txt,从中读取数据。InputStream 是一个抽象类,FileInputStream 是专门用于读取文件流的子类。BufferedInputStream 是一个支持缓存的数据读取类,可以提高数据读取的效率,具体代码如下: @Test public void testIO throws Exception { InputStream inputStream = new FileInputStream("C:/bbb/a.txt"); // 实现包装 inputStream = new BufferedInputStream(inputStream); byte bytes = new byte[1024]; int len; while((len = inputStream.read(bytes)) != -1){ System.out.println(new String(bytes, 0, len)); } } } } 其中 BufferedInputStream 对读取数据进行了增强。 这样看来,装饰器设计模式和代理模式似乎有点相似,接下来让我们讨论一下它们之间的区别。 第三,与代理模式的区别: 代理模式的目的是控制对对象的访问,它在对象外部提供一个代理对象来控制对原对象的访问。代理对象和原始对象通常实现相同的接口或继承相同的类,以确保两者可以相互替换。 装饰器模式的目的是动态增强对象的功能,而这是通过对象内部的包装器来实现的。在装饰器模式中,装饰器类和被装饰对象通常实现相同的接口或继承自相同的类,以确保两者可以相互替代。装饰器模式也被称为封装器模式。 在代理模式中,代理类附加了与原类无关的功能。
-
Java Lambda 列表到映射代码示例
-
Java 的枚举枚举示例详情
-
贝塔分布采样的 Java 编程实现或采样示例代码
-
Java 气泡排序
-
[排序算法] - 气泡排序的三种实现(Java)
-
经典排序算法 (1) - 气泡排序算法详情