排序算法图解之Java冒泡排序及优化
作者:兴趣使然黄小黄 发布时间:2022-07-16 01:28:38
1.冒泡排序简介
冒泡排序(Bubble Sorting)即:通过对待排序的序列从前往后,依次比较相邻元素的值,若发现逆序则交换位置,使较大的元素逐渐移动到后部,就像水底的气泡一样逐渐从水面冒出来,这就是冒泡名称的由来
2.图解算法
以将序列{3, 9, -1, 10, -20}从小到大排序为例!
基本思想就是,在每一趟排序实现将最大的数移到序列的最后端!这主要通过比较相邻两个元素实现,当相邻的两个元素逆序的时候,我们就交换它们。
第1趟排序:
第1趟排序共比较了4次,将最大的数10冒泡到了序列的尾部。
第2趟排序:
由于第一趟排序已经将最大是数10给冒泡到了最末端,因此在本次排序中,不需要再比较最后一个元素,故共比较了3次,将子序列(前四个元素)中最大的数9(整个序列中倒数第二大的数)冒泡到了子序列的尾端(原序列的倒数第二个位置)。
第3趟排序:
在第三趟排序时,同理,倒数两个元素位置已经确定,即第一、第二大的数已经排好位置,只需要再将倒数第三大的数确认即可。故比较2次,实现倒数第三大的数3的位置确定。
第4趟排序:
在第四趟排序时,只有第一、第二个元素的位置还不确定,只需要比较一次,若逆序,则交换即可。到此,排序算法完成,原序列已经排序成为一个递增的序列!
小结
一共进行了数组大小-1次趟排序,即外层循环arr.length-1次;每趟排序进行了逐趟减小次数的比较,即内层循环arr.length-i-1次,i从0依次增加。
3.冒泡排序代码实现
参考代码如下,为了便于观察结果,在循环中添加了相应的输出语句:
import java.util.Arrays;
/**
* @author 兴趣使然黄小黄
* @version 1.0
* 冒泡排序
*/
public class BubbleSort {
public static void main(String[] args) {
int[] array = {3, 9, -1, 10, -20};
//排序前
System.out.println("排序前:" + Arrays.toString(array));
//冒泡排序
for (int i = 0; i < array.length - 1; i++) {
System.out.println("第" + (i+1) + "趟排序开始!");
for (int j = 0; j < array.length - i - 1; j++) {
//如果前面的数比后面的数大,则交换
if(array[j] > array[j+1]){
//交换
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
}
System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
System.out.println("================================================");
}
//输出排序后的结果
System.out.println("排序后:" + Arrays.toString(array));
}
}
实现结果:
4.冒泡排序算法的优化
举个例子,将待排序的序列改为:{5,1,2,3,4},用以上算法来处理,观察一下结果:
可以发现,当第一趟排序结束的时候,序列已经排序完成: 即将5冒泡到了最后,序列实现了从小到大排序。但是原冒泡排序算法,还是义无反顾的进行了数组大小-1趟排序(我可真是大冤种!)
因此,我们需要尝试对算法进行优化!
发现:在冒泡排序的过程中,各个元素都在不断的接近自己的位置,如果下一趟比较中没有进行过任何交换,则说明序列已经有序, 则排序算法已经可以返回结果。因此,考虑在排序算法过程中添加一个标志flag判断元素是否进行过交换,以减少不必要的冤种行为!
优化代码如下:
import java.util.Arrays;
/**
* @author 兴趣使然黄小黄
* @version 1.0
* 冒泡排序优化
*/
public class BubbleSort {
public static void main(String[] args) {
int[] array = {5, 1, 2, 3, 4};
//排序前
System.out.println("排序前:" + Arrays.toString(array));
boolean flag = false; //用于标记是否进行了交换,true则说明进行了交换,false表示无
//冒泡排序
for (int i = 0; i < array.length - 1; i++) {
System.out.println("第" + (i+1) + "趟排序开始!");
for (int j = 0; j < array.length - i - 1; j++) {
//如果前面的数比后面的数大,则交换
if(array[j] > array[j+1]){
//交换
flag = true; //标记进行了交换
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
}
System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
System.out.println("================================================");
if (!flag){
//如果没有进行交换则直接退出,说明排序已经完成
break;
}else {
//回退
flag = false;
}
}
//输出排序后的结果
System.out.println("排序后:" + Arrays.toString(array));
}
}
四趟排序,优化成了只需要两趟排序!又是一个不可多得的小技巧!在算法程序题中,flag的设置是一种常用的编程思想,常常用于回溯算法中,小伙伴们要学会举一反三~
来源:https://blog.csdn.net/m0_60353039/article/details/127670013
猜你喜欢
- 什么是委托?之前写了事件的介绍:https://www.jb51.net/article/59461.htm这里也把委托相关知识也总结一下。
- intellj idea的强大之处就不多说了,相信每个用过它的人都会体会到,但是我们也会被他的复杂搞的晕头转向,尤其刚从eclipse转过来
- 1、实现循环队列【OJ链接】循环队列一般通过数组实现。我们需要解决几个问题。(1)数组下标实现循环a、下标最后再往后(offset 小于 a
- 最近“全网域(Web Scale)”一词被炒得火热,人们也正在通过扩展他们的应用程序架构来使他们的系统变得更加“全网域”。但是究竟什么是全网
- 循环队列结构队列特点队列为一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,
- 定义jdk8发布新特性中,lambda是一大亮点之一。lambda表达式能够简化我们对数据的操作,减少代码量,大大提升我们的开发效率。Lam
- 本文实例为大家分享了java文件上传下载的具体代码,供大家参考,具体内容如下文件上传@RequestMapping(value="
- Java中throws和throw的区别讲解当然,你需要明白异常在Java中式以一个对象来看待。并且所有系统定义的编译和运行异常都可以由系统
- 数组的用处是什么呢?——当你需要将30个数进行大小排列的时候,用数组这样的数据结构存储是个很好的选择,当你是一个班的班主任的时候,每次要记录
- 前言前阵子有同学反馈Flutter中的http请求无法通过fiddler抓包,作者喜欢使用Charles抓包工具,于是抽时间写了个小demo
- 前言:项目是使用Java swing开发,可实现基础数据维护用户登录、系统首页酒店信息管理、主要模块是开房管理、退房管理、房间信息管理、顾客
- 记录自己用java swing做的第一个简易界面。LoginAction.javapackage com.QQUI0819;import j
- @Autowired注入依赖失败的问题1、现象描述在Spring Boot项目中使用@Autowired注解,程序启动时发现服务启动失败,提
- 序列化与反序列化序列化:把对象转换成字节的过程,称为对象序列化反序列化:把字节恢复成对象的过程,称为反序列化对象的持久化概念:把字节保存的硬
- throw抛出异常的方式比较直接:if(age < 0){throw new MyException("年龄不能为负数!&q
- 一、任务和执行策略之间的隐性耦合Executor可以将任务的提交和任务的执行策略解耦只有任务是同类型的且执行时间差别不大,才能发挥最大性能,
- 前言每次update Maven Project 的时候,看着进度条寸步难行,心里憋得十分难受,明显阻碍我学习的热情。 maven仓库默认在
- 本文实例为大家分享了SSM实现学生管理系统的具体代码,供大家参考,具体内容如下概述基于Spring + Spring MVC 的学生管理系统
- 这篇文章主要介绍了SpringBoot使用Log4j过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需
- CompletableFuture 介绍CompletableFuture是1.8引入的新特性,一些比较复杂的异步计算场景,尤其是需要串联多