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玩转《啊哈算法》排序之冒泡排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---