Java玩转《啊哈算法》排序之冒泡排序

2024-01-30 22:20
文章标签 java 算法 排序 玩转 冒泡排序 啊哈

本文主要是介绍Java玩转《啊哈算法》排序之冒泡排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

色即是空，空即是色

文章目录

  • 楔子
  • 代码地址
  • 冒泡排序
    • 核心代码
    • 优劣
    • 可视化
    • 完整代码
      • 演示
    • 升级版
      • 代码
      • 演示
    • 实战

楔子

大家好！本人最近看了下《啊哈算法》，写的确实不错，生动形象又有趣（希望作者打波广告费 ）。

但对我来说，稍显遗憾的是，书籍代码是c语言，而不是本人常用的Java。

那就弥补遗憾，说干就干，把这本书的示例语言用java给翻译一遍！！！

于是就有了本篇博客，这篇主要是讲解冒泡排序。
在这里插入图片描述

没有买纸质书的童鞋也甭担心，电子版的下载链接已经放到下方了，自己下载去吧！！！

链接：https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwd=jmgs
提取码：jmgs

不过还是建议有条件的同学可以买下纸质书，毕竟纸质书的手感那是没得说。

代码地址

本文代码已开源：

git clone https://gitee.com/guqueyue/my-blog-demo.git

请切换到gitee分支，

然后查看aHaAlgorithm模块下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_1_Sort即可！

冒泡排序

在上篇博客中：Java玩转《啊哈算法》排序之桶排序，我们介绍了桶排序，但桶排序缺点也很明显，

空间复杂度高，也就是说非常的浪费空间，并且不能对小数进行排序。

下面让我们来介绍一种 空间复杂度很低，仅为O(n) 的排序算法，

也就是我们的冒牌排序，闪亮登场啦！！！

咳咳，口误口误，冒泡排序 冒泡排序！

在这里插入图片描述

冒泡排序，顾名思义，这种排序算法执行起来就像鱼吐泡泡一样，一个泡泡一个泡泡往上冒。

在这里插入图片描述
为什么这么说呢？ ↑↑↑ 如上图 ↑↑↑

假设我们要用冒泡排序进行降序排序（升序是同样的逻辑，但是交换的原则相反）：

  1. 我们需要从数组开头开始遍历，将数组相邻元素两两比较，如果后一个数比前一个数大(小)，则交换两个数。
    这样经过一轮交换之后，数组最后的元素就变成了最小(大)的元素。而这样的交换过程，很像是在冒泡泡。
  2. 当然，仅经过一轮相邻元素的比较交换是不行的，这样只能确定一个元素的位置。而要 确定好所有元素的位置，需要经过n-1轮这样的相邻元素的比较交换 (为什么是n-1，可以自己想下)。

当然，这里每一轮遍历都能比上一轮少比较一次，毕竟每一轮遍历都能确定好一个元素位置。

这里还涉及到一个非常简单的算法：如何交换两个数？

如果有不是很懂的，可以参考我的这篇博客：实现两个数互换的八种方法

核心代码

这里代码主要有两个循环，以及循环内有一个比较交换的逻辑。

  • 循环内代码是一个对相邻元素进行比较，判断是否需要交换两个数的逻辑。
  • 内层循环表示从第二个元素开始遍历每一个数，每次都少遍历一个元素。
  • 外层循环表示需要对相邻元素进行比较交换的次数，为n-1次。
    /*** @Description 冒泡排序* @Param [scoreArr：需要排序的数组]* @return void**/private static void bubbleSort(int[] scoreArr) {int n = scoreArr.length;for (int i = 0; i < n - 1; i++) { // 需要比较 n-1 次for (int j = 1; j < n-i; j++) { // 从第二个数遍历，一直遍历到 n-1-i 个数if (scoreArr[j] > scoreArr[j-1]) { // 如果 第j个数 比 第j-1个数 大，则互换两个数int t = scoreArr[j]; scoreArr[j] = scoreArr[j-1]; scoreArr[j-1] = t;}}}}

优劣

  • 空间复杂度低，为O(n)。属于一种原地排序算法了，不需要占用额外空间。
  • 时间复杂度高，为O(n ^ 2)。这也意味着大数据量的情况下，算法执行速率会不太理想。

可视化

在这里插入图片描述
经过上文的图文讲解以及代码实战，再看到这么清晰直观的动图有没有一种豁然开朗的感觉？

完整代码

package com.guqueyue.aHaAlgorithm.chapter_1_Sort;import java.util.Arrays;
import java.util.Scanner;/*** @Author: guqueyue* @Description: 冒泡排序 - 排序分数数组* @Date: 2024/1/8**/
public class BubbleSort {public static void main(String[] args) {int[] scoreArr = getScoreArr(); // 获取分数数组System.out.println("输入的数组为：" + Arrays.toString(scoreArr));bubbleSort(scoreArr); // 冒泡排序System.out.println("排序后的数组为： " + Arrays.toString(scoreArr));}/*** @Description 冒泡排序* @Param [scoreArr：需要排序的数组]* @return void**/private static void bubbleSort(int[] scoreArr) {int n = scoreArr.length;for (int i = 0; i < n - 1; i++) { // 需要比较 n-1 次for (int j = 1; j < n-i; j++) { // 从第二个数遍历，一直遍历到 n-1-i 个数if (scoreArr[j] > scoreArr[j-1]) { // 如果 第j个数 比 第j-1个数 大，则互换两个数int t = scoreArr[j]; scoreArr[j] = scoreArr[j-1]; scoreArr[j-1] = t;}}}}/*** @Description 获取分数数组* @Param []* @return int[]**/private static int[] getScoreArr() {Scanner scanner = new Scanner(System.in);System.out.print("请输入数组长度：");int n = scanner.nextInt();System.out.printf("请输入%d个数，然后按回车: ", n);int[] scoreArr = new int[n];for (int i = 0; i < n; i++) {scoreArr[i] = scanner.nextInt();}return scoreArr;}
}

演示

运行程序，控制台输入，可得：
在这里插入图片描述
成功降序排序！

升级版

正如作者所说，上文只是一个算法的简单演示，似乎没有什么实际用途。

为了让读者感受的足够真切，那么我们下面将对一定数量的学生通过分数进行排名，然后输出他们的姓名

代码

首先创建一个学生对象，用于存储学生的分数和姓名：

package com.guqueyue.aHaAlgorithm.entity;import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;/*** @Author: guqueyue* @Description: 学生类* @Date: 2024/1/9**/
//lombok插件的注解
@Data // 若未使用lombok插件，请自行生成getter、setter以及toString方法
@NoArgsConstructor // 若未使用lombok插件，请自行生成无参构造方法
@AllArgsConstructor // 若未使用lombok插件，请自行生成有参构造方法
public class Student {private String name; // 姓名private Integer score; // 分数
}

其次，开干：

package com.guqueyue.aHaAlgorithm.chapter_1_Sort;import com.guqueyue.aHaAlgorithm.entity.Student;import java.util.Arrays;
import java.util.Scanner;/*** @Author: guqueyue* @Description: 冒泡排序 - 按照分数排序学生数组* @Date: 2024/1/9**/
public class BubbleSort2 {public static void main(String[] args) {Student[] scoreArr = getStudentArr(); // 获取学生数组
//        System.out.println("输入的数组为：" + Arrays.toString(scoreArr));bubbleSort(scoreArr); // 冒泡排序
//        System.out.println("排序后的数组为： " + Arrays.toString(scoreArr));System.out.print("学生排名为： ");for (Student student : scoreArr) {System.out.print(student.getName() + "(" + student.getScore() + ") ");}System.out.println();}/*** @Description 冒泡排序* @Param [scoreArr]* @return void**/private static void bubbleSort(Student[] scoreArr) {Student student;int n = scoreArr.length;for (int i = 0; i < n - 1; i++) { // 需要比较 n-1 次for (int j = 1; j < n-i; j++) { // 每次需要遍历到 n-1-i, 因为外层每遍历一次就会有一个数已经排序后放在最后面if (scoreArr[j].getScore() > scoreArr[j-1].getScore()) { // 如 第j个学生 分数 比 第 j-1个学生 更高，则交换两个学生对象student = scoreArr[j];scoreArr[j] = scoreArr[j-1];scoreArr[j-1] = student;}}}}/*** @Description 获取学生数组* @Param []* @return com.guqueyue.aHaAlgorithm.entity.Student[]**/private static Student[] getStudentArr() {Scanner scanner = new Scanner(System.in);System.out.print("请输入学生数量：");int n = scanner.nextInt();Student[] students = new Student[n];for (int i = 0; i < n; i++) {System.out.printf("请输入第%d个学生的姓名和分数，以空格隔开，再回车：", i+1);// 创建学生对象，再放入姓名和分数Student student = new Student();student.setName(scanner.next());student.setScore(scanner.nextInt());// 将创建好的学生对象放入数组students[i] = student;}return students;}
}

演示

运行代码，控制台输入可得：
在这里插入图片描述
这里为了直观显示，这里在姓名后面的括号里面打印了分数。

实战

如果理解了的话，那么发一道力扣的题目链接当课后习题吧：

912. 排序数组

在这里插入图片描述

当然，你用冒泡排序做这题的话，只能对一半，因为冒泡排序耗时太长！

在这里插入图片描述

不过，你如果看了我的上一篇博客的话，用桶排序倒是能做出来： Java玩转《啊哈算法》排序之桶排序

在这里插入图片描述

虽然通过了，但是空间复杂度太高了，一点也不优雅！
在这里插入图片描述

那么到底有没有一种算法？做到既耗时少，又占用内存少，鱼和熊掌兼得？

我们下期博客再说！

在这里插入图片描述

这篇关于Java玩转《啊哈算法》排序之冒泡排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/661735。

相关文章

Java中流式并行操作parallelStream的原理和使用方法

Java中流式并行操作parallelStream的原理和使用方法

《Java中流式并行操作parallelStream的原理和使用方法》本文详细介绍了Java中的并行流（parallelStream）的原理、正确使用方法以及在实际业务中的应用案例,并指出在使用并行流... 目录Java中流式并行操作parallelStream0. 问题的产生1. 什么是parallelS
阅读更多...
Java中Redisson 的原理深度解析

Java中Redisson 的原理深度解析

《Java中Redisson的原理深度解析》Redisson是一个高性能的Redis客户端,它通过将Redis数据结构映射为Java对象和分布式对象,实现了在Java应用中方便地使用Redis,本文... 目录前言一、核心设计理念二、核心架构与通信层1. 基于 Netty 的异步非阻塞通信2. 编解码器三、
阅读更多...
SpringBoot基于注解实现数据库字段回填的完整方案

SpringBoot基于注解实现数据库字段回填的完整方案

《SpringBoot基于注解实现数据库字段回填的完整方案》这篇文章主要为大家详细介绍了SpringBoot如何基于注解实现数据库字段回填的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解... 目录数据库表pom.XMLRelationFieldRelationFieldMapping基础的一些代
阅读更多...
一篇文章彻底搞懂macOS如何决定java环境

一篇文章彻底搞懂macOS如何决定java环境

《一篇文章彻底搞懂macOS如何决定java环境》MacOS作为一个功能强大的操作系统,为开发者提供了丰富的开发工具和框架,下面：本文主要介绍macOS如何决定java环境的相关资料,文中通过代码... 目录方法一：使用 which命令方法二：使用 Java_home工具（Apple 官方推荐）那问题来了，
阅读更多...
Java HashMap的底层实现原理深度解析

Java HashMap的底层实现原理深度解析

《JavaHashMap的底层实现原理深度解析》HashMap基于数组+链表+红黑树结构,通过哈希算法和扩容机制优化性能,负载因子与树化阈值平衡效率,是Java开发必备的高效数据结构,本文给大家介绍... 目录一、概述：HashMap的宏观结构二、核心数据结构解析1. 数组（桶数组）2. 链表节点（Node
阅读更多...
Java AOP面向切面编程的概念和实现方式

Java AOP面向切面编程的概念和实现方式

《JavaAOP面向切面编程的概念和实现方式》AOP是面向切面编程,通过动态代理将横切关注点（如日志、事务）与核心业务逻辑分离,提升代码复用性和可维护性,本文给大家介绍JavaAOP面向切面编程的概... 目录一、AOP 是什么？二、AOP 的核心概念与实现方式核心概念实现方式三、Spring AOP 的关
阅读更多...
详解SpringBoot+Ehcache使用示例

详解SpringBoot+Ehcache使用示例

《详解SpringBoot+Ehcache使用示例》本文介绍了SpringBoot中配置Ehcache、自定义get/set方式,并实际使用缓存的过程,文中通过示例代码介绍的非常详细,对大家的学习或者... 目录摘要概念内存与磁盘持久化存储：配置灵活性：编码示例引入依赖：配置ehcache.XML文件：配置
阅读更多...
Java 虚拟线程的创建与使用深度解析

Java 虚拟线程的创建与使用深度解析

《Java虚拟线程的创建与使用深度解析》虚拟线程是Java19中以预览特性形式引入,Java21起正式发布的轻量级线程,本文给大家介绍Java虚拟线程的创建与使用,感兴趣的朋友一起看看吧... 目录一、虚拟线程简介1.1 什么是虚拟线程？1.2 为什么需要虚拟线程？二、虚拟线程与平台线程对比代码对比示例：三
阅读更多...
Java中的.close()举例详解

Java中的.close()举例详解

《Java中的.close()举例详解》.close()方法只适用于通过window.open()打开的弹出窗口,对于浏览器的主窗口,如果没有得到用户允许是不能关闭的,：本文主要介绍Java中的.... 目录当你遇到以下三种情况时，一定要记得使用 .close()：用法作用举例如何判断代码中的 input
阅读更多...
深入理解Mysql OnlineDDL的算法

深入理解Mysql OnlineDDL的算法

《深入理解MysqlOnlineDDL的算法》本文主要介绍了讲解MysqlOnlineDDL的算法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小... 目录一、Online DDL 是什么？二、Online DDL 的三种主要算法2.1COPY（复制法）
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2