当前位置: 首页 > news >正文

java-冒泡排序 1

## Java中的冒泡排序

### 1. 冒泡排序的基本概念

冒泡排序(Bubble Sort)是一种简单且直观的排序算法。它通过重复地遍历待排序的列表,比较相邻的元素并交换它们的位置,使较大的元素逐步从列表的一端移动到另一端,就像气泡在水中上升一样。冒泡排序的核心思想是逐步将最大的元素“冒泡”到列表的末尾。

### 2. 冒泡排序的工作原理

冒泡排序通过多次遍历列表,每次遍历将相邻的两个元素进行比较,如果顺序错误就交换它们。每次完整的遍历后,最大的元素会被移动到列表的末尾。这个过程会重复进行,直到整个列表有序为止。

#### 2.1 示例

假设有一个待排序的数组`[5, 3, 8, 4, 2]`,冒泡排序的过程如下:

- 初始状态:[5, 3, 8, 4, 2]
- 第一次遍历:
  - 比较5和3,交换,数组变为:[3, 5, 8, 4, 2]
  - 比较5和8,不交换,数组不变:[3, 5, 8, 4, 2]
  - 比较8和4,交换,数组变为:[3, 5, 4, 8, 2]
  - 比较8和2,交换,数组变为:[3, 5, 4, 2, 8]
- 第二次遍历:
  - 比较3和5,不交换,数组不变:[3, 5, 4, 2, 8]
  - 比较5和4,交换,数组变为:[3, 4, 5, 2, 8]
  - 比较5和2,交换,数组变为:[3, 4, 2, 5, 8]
  - 比较5和8,不交换,数组不变:[3, 4, 2, 5, 8]
- 第三次遍历:
  - 比较3和4,不交换,数组不变:[3, 4, 2, 5, 8]
  - 比较4和2,交换,数组变为:[3, 2, 4, 5, 8]
  - 比较4和5,不交换,数组不变:[3, 2, 4, 5, 8]
  - 比较5和8,不交换,数组不变:[3, 2, 4, 5, 8]
- 第四次遍历:
  - 比较3和2,交换,数组变为:[2, 3, 4, 5, 8]
  - 比较3和4,不交换,数组不变:[2, 3, 4, 5, 8]
  - 比较4和5,不交换,数组不变:[2, 3, 4, 5, 8]
  - 比较5和8,不交换,数组不变:[2, 3, 4, 5, 8]

经过四次遍历后,数组已经有序:[2, 3, 4, 5, 8]。

### 3. 冒泡排序的实现

在Java中实现冒泡排序非常简单,可以通过嵌套的`for`循环来实现。

#### 3.1 基本实现

```java
public class BubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换array[j]和array[j + 1]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2};
        bubbleSort(array);
        System.out.println("Sorted array:");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}
```

在这个实现中,外层循环控制遍历的次数,内层循环用于比较和交换相邻的元素。每次内层循环结束后,最大的元素被移动到列表的末尾。

### 4. 优化冒泡排序

冒泡排序的效率不高,尤其是在处理较大数据集时。可以通过一些优化来提高其性能。

#### 4.1 提前终止

如果在某次遍历中没有发生任何交换,说明数组已经有序,可以提前终止排序。

```java
public class OptimizedBubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换array[j]和array[j + 1]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            // 如果没有交换发生,提前终止
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2};
        bubbleSort(array);
        System.out.println("Sorted array:");
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
}
```

### 5. 冒泡排序的时间复杂度

冒泡排序的时间复杂度取决于输入数据的初始顺序。

- 最好情况:当数组已经有序时,只需要进行一次遍历即可终止,时间复杂度为O(n)。
- 最坏情况:当数组完全逆序时,需要进行n-1次遍历,时间复杂度为O(n^2)。
- 平均情况:时间复杂度为O(n^2)。

冒泡排序的空间复杂度为O(1),因为它只需要常数级别的额外空间用于交换元素。

### 6. 冒泡排序的稳定性

冒泡排序是一个稳定的排序算法,即如果两个元素相等,它们在排序后的相对顺序不会改变。这是因为冒泡排序在交换元素时,只会交换相邻的元素,不会跨过其他相等的元素。

### 7. 冒泡排序的适用场景

由于冒泡排序的时间复杂度较高,它通常不适用于大型数据集的排序。然而,冒泡排序的实现非常简单,因此在某些简单或特定的场景下仍然可以使用,例如:

- 学习和教学:冒泡排序是许多初学者学习排序算法的入门算法。
- 小型数据集:对于非常小的数据集,冒泡排序的性能尚可。
- 数据近乎有序:如果数据集大部分已经有序,冒泡排序的优化版本可以高效地完成排序。

### 8. 冒泡排序的可视化

为了更好地理解冒泡排序的工作原理,可以将排序过程进行可视化。以下是一个简单的示例,展示了如何通过打印每次遍历后的数组状态来可视化排序过程。

```java
public class VisualBubbleSort {
    public static void bubbleSort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    // 交换array[j]和array[j + 1]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
            // 打印当前状态
            printArray(array);
        }
    }

    public static void printArray(int[] array) {
        for (int i : array) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2};
        bubbleSort(array);
        System.out.println("Sorted array:");
        printArray(array);
    }
}
```

在这个示例中,每次内层循环结束后,数组的当前状态会被打印出来,帮助我们直观地观察排序过程。

相关文章:

java-冒泡排序 1

## Java中的冒泡排序 ### 1. 冒泡排序的基本概念 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单且直观的排序算法。它通过重复地遍历待排序的列表&#xff0c;比较相邻的元素并交换它们的位置&#xff0c;使较大的元素逐步从列表的一端移动到另一端&#xff0c;就像…...

【STM32】USART串口通讯

1.USART简介 STM32芯片具有多个USART外设用于串口通讯&#xff0c;它是 Universal Synchronous Asynchronous Receiver and Transmitter的缩写&#xff0c; 即通用同步异步收发器可以灵活地与外部设备进行全双工数据交换。有别于USART&#xff0c; 它还有具有UART外设(Univers…...

Qt6中如何将QList转为QSet?

QSet是一个具有唯一值的哈希集合。比较少用。比较有用的是QSet里面的intersect查找两个集合中不同元素&#xff0c;并合并。 转换过程比较简单&#xff0c;第一种是直接用迭代器。 QSet<int> set(list.begin(), list.end()); 第二种就是逐一遍历赋值&#xff1a; QLi…...

aspectj:AOP编程备忘录-切面定义的注意事项

AOP编程时定义切面时需要注意的事 Around 以Around注解拦截构造方法(Constructor)时切面定义只能用call方式而不能是execution&#xff0c;否则 ProceedingJoinPoint.proceed()返回的是null&#xff0c;得不到构造的实例。 execution execution切入点要修改对象内部&#x…...

大数据面试题之Hive(1)

目录 说下为什么要使用Hive?Hive的优缺点?Hive的作用是什么? 说下Hive是什么?跟数据仓库区别? Hive架构 Hive内部表和外部表的区别? 为什么内部表的删除&#xff0c;就会将数据全部删除&#xff0c;而外部表只删除表结构?为什么用外部表更好? Hive建表语句?创建表…...

【Git】分布式版本控制工具

一、简介 二、目标 Git分布式版本控制工具 一、简介 Git是一种分布式版本控制系统&#xff0c;用于跟踪和管理源代码的变化。它由林纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;于2005年开发&#xff0c;并迅速成为最流行的版本控制工具之一。以下是关于Git的一些关键…...

排序之插入排序----直接插入排序和希尔排序(1)

个人主页&#xff1a;C忠实粉丝 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 C忠实粉丝 原创 排序之插入排序----直接插入排序和希尔排序(1) 收录于专栏【数据结构初阶】 本专栏旨在分享学习数据结构学习的一点学习笔记&#xff0c;欢迎大家在评论区交流讨…...

快速创建条形热力图

Excel中的条件格式可以有效的凸显数据特征&#xff0c;如下图中B列所示。 现在需要使用图表展现热力条形图&#xff0c;如下图所示。由于颜色有多个过渡色&#xff0c;因此手工逐个设置数据条的颜色&#xff0c;基本上是不可能完成的任务&#xff0c;使用VBA代码可以快速创建这…...

go switch 与 interface

go switch 与 interface 前言 前言 github.com/google/cel-go/common/types/ref type Val interface {// ConvertToNative converts the Value to a native Go struct according to the// reflected type description, or error if the conversion is not feasible.ConvertTo…...

BaseMapper 接口介绍

基于 mybatis-mapper/provider 核心部分实现的基础的增删改查操作&#xff0c;提供了一个核心的 io.mybatis.mapper.BaseMapper 接口和一个 预定义 的 io.mybatis.mapper.Mapper 接口&#xff0c;BaseMapper 接口定义如下&#xff1a; /*** 基础 Mapper 方法&#xff0c;可以在…...

HAL-Cubemax定时器使用记录

title: HAL-Cubemax定时器使用记录 tags: STM32HalCubemax 文章目录 HAL-Cubemax定时器使用记录分享一种思路1.创建一个ms(毫秒)级延时中断2.创建计数的变量3.在需要延时的函数中对变量阈值进行判断4.验证实例--完整使用记录代码 问题往期内容基础库HAL cubemax VSCODE GCC …...

同时使用磁吸充电器和Lightning时,iPhone充电速度会变快吗?

在智能手机的世界里&#xff0c;续航能力一直是用户关注的焦点。苹果公司以其创新的MagSafe技术和传统的Lightning接口&#xff0c;为iPhone用户提供了多样化的充电解决方案。 然而&#xff0c;当这两种技术同时使用时&#xff0c;它们能否带来更快的充电速度&#xff1f;本文…...

零成本搭建个人图床服务器

前言 图床服务器是一种用于存储和管理图片的服务器&#xff0c;可以给我们提供将图片上传后能外部访问浏览的服务。这样我们在写文章时插入的说明图片&#xff0c;就可以集中放到图床里&#xff0c;既方便多平台文章发布&#xff0c;又能统一管理和备份。 当然下面通过在 Git…...

SpringBoot 搭建sftp服务 实现远程上传和下载文件

maven依赖&#xff1a; <dependency><groupId>com.jcraft</groupId><artifactId>jsch</artifactId><version>0.1.55</version> </dependency>application.yml sftp:protocol: sftphost: port: 22username: rootpassword: sp…...

IDEA中使用leetcode 刷题

目录 1.IDEA下载leetcode插件 2.侧边点开插件 3.打开网页版登录找到cookie复制 4.回到IDEA登录 5.刷题 6.共勉 1.IDEA下载leetcode插件 2.侧边点开插件 3.打开网页版登录找到cookie复制 4.回到IDEA登录 5.刷题 6.共勉 算法题来了不畏惧&#xff0c; 挑战前行是成长的舞台…...

华为海思CPU解读

安全可靠CPU测评结果&#xff08;华为海思篇&#xff09; 中国信息安全测评中心于2024年5月20日发布安全可靠测评结果公告&#xff08;2024年第1号&#xff09;&#xff0c;公布依据《安全可靠测评工作指南&#xff08;试行&#xff09;》的测评结果&#xff0c;自发布起有效期…...

中介子方程三十三

XXFXXuXXWXXuXXdXXrXXαXXuXpXXdXXpXuXXαXXrXXdXXuXWXπXXWXeXyXeXbXπXpXXNXXqXeXXrXXαXXuXpXXdXXpXuXXαXXrXXeXqXXNXXpXπXbXeXyXeXWXXπXWXuXXdXXrXXαXXuXpXXdXXpXuXXαXXrXXdXXuXXWXXuXXFXXEXXyXXEXXrXXαXXuXpXXdXXpXuXXαXXrXXEXXyXXαXiXXαXiXrXkXtXyXXpXVXXdXuXWX…...

今年哪两个行业可能有贝塔?

银行和综合板块存在比较明显的行业贝塔&#xff0c;背后原因是&#xff1a;银行板块中&#xff0c;最小的几家银行市值也不小&#xff1b;综合板块中&#xff0c;最大的几家市值也不大。 一、今年哪两个行业可能有贝塔&#xff1f; 我们一直强调今年市场呈现出【行业弱beta、风…...

嵌入式软件开发工具使用介绍

软件开发工具 辅助开发工具 硬件工具与仪器设备 逻辑分析仪使用 串口数据解码分析 示波器使用 1.示波器简介 TBS 1052B&#xff08;Tektronix&#xff09;系列数字存储示波器在紧凑的设计中提供了经济的性能。 由于多种标配功能&#xff0c; 包括 USB 连接、34 种自动测量、…...

【TB作品】MSP430G2553,单片机,口袋板, 交通灯控制系统

题8 交通灯控制系统 十字路口交通灯由红、绿两色LED显示器&#xff08;两位8段LED显示器&#xff09;组成&#xff0c;LED显示器显示切换倒计时&#xff0c;以秒为单位&#xff0c;每秒更新一次&#xff1b;为确保安全&#xff0c;绿LED计数到0转红&#xff0c;经5秒延时&#…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...