冒泡排序详解(Bubble Sort)

简介: 冒泡排序详解

一、简单释义

1、算法概念

 冒泡排序(Bubble Sort)是重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

2、算法目的

 把无序数组通过通过两两相比交换位置,最后形成一个有序数组  (文中以升序为例)

3、算法思想

 通过不断比较相邻的元素,如果左边的元素 大于 右边的元素,则进行交换,直到所有相邻元素都保持升序,则算法结束。

4、算法由来

 这个算法的名字由来是因为越小的元素会经由交换慢慢浮动到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

二、核心思想

「迭代」:类似的事情,不停地做。

「比较」:关系运算符 大于(>) 的运用。

「交换」:变量或者对象的值的互换。

三、图形展示

1、宏观展示

8216aad0a6e445589e8e9fdcab74be4d.png

2、微观展示

 以3、6、4、2、11、10、5这个数组为例,由于每一趟排序的过程都是一样的。所以下面是第一趟排序的详细比较过程

9d9b4cc8a05743ed8b78a81e4be9fd54.png

 1、第一次比较:3与6进行比较,3 < 6 所以不交换位置。得到3,6,4,2,11,10,5

790a061339bc4012ae5a92707c281062.png

 2、第二次排序:6与4比较,6 > 4,6与4交换位置,如果相邻的元素逆序就交换。得到3,4,6,2,11,10,5

4889142aa1b24cd9b22fffd8abfbea66.png

 3、第三次排序:交换完位置后两个索引又同时移动让 6 与 2比较,6 > 2,6与2交换位置。得到3,4,2,6,11,10,5

e96c28439a9e4e28a3e036d5f6296ead.png

 4、第四次排序:6与11进行比较,6 < 11 所以不交换位置。得到 3,4,2,6,11,10,5

164051d749124b2680fff00ddaf7b595.png

 5、第五次排序:11与10进行比较,11 > 10 所以进行位置交换。得到 3,4,2,6,10,11,5

0a5c56d08391455eb904df164a247341.png

 6、最后将11与5进行比较,11 > 5 所以进行位置交换。得到3,4,2,6,10,5,11

四、算法实现

1、实现思路

 将图形化展示的过程转换成对应的开发语言,本文中主要以Java语言为例来进行算法的实现。

 1. 比较相邻的元素。如果第一个比第二个大,就交换它们两个;

 2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

 3. 针对所有的元素重复以上的步骤,除了最后一个;

 4. 重复步骤1~3,直到排序完成。

 能把整个过程描述清楚实现起来才会更加容易!!!

2、代码实现

/**
 * @BelongsProject: demo
 * @BelongsPackage: com.wzl.Algorithm.BubbleSort
 * @Author: Wuzilong
 * @Description: 冒泡排序
 * @CreateTime: 2023-05-01 11:18
 * @Version: 1.0
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] numArray={3,6,4,2,11,10,5};
        //冒泡排序的时间复杂度为O(n*n)
        int temp = 0;//临时变量
        for (int j = 0; j < numArray.length - 1; j++) {
            for (int i = 0; i < numArray.length-1 -j ; i++) {
                if (numArray[i] > numArray[i+1]){
                    //三角交换
                    temp = numArray[i];
                    numArray[i] = numArray[i+1];
                    numArray[i+1] = temp;
                }
            }
            System.out.println("第"+(j+1)+"趟"+Arrays.toString(numArray));
        }
    }
}

3、运行结果

6fa5a9edec084b4787993fc930f5a0c5.png

4、代码优化

会存在数组在中间的某一趟中就已经是有序的了,减少后面的无效比较

/**
 * @BelongsProject: demo
 * @BelongsPackage: com.wzl.Algorithm.BubbleSort
 * @Author: Wuzilong
 * @Description: 冒泡排序优化
 * @CreateTime: 2023-05-01 11:18
 * @Version: 1.0
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] numArray={3,6,4,2,11,10,5};
        int temp = 0;//临时变量
        boolean flag = false;//用于优化冒泡排序,判断是否进行过交换
        for (int j = 0; j < numArray.length - 1; j++) {
            for (int i = 0; i < numArray.length-1 -j ; i++) {
                if (numArray[i] > numArray[i+1]){
                    //三角交换
                    temp = numArray[i];
                    numArray[i] = numArray[i+1];
                    numArray[i+1] = temp;
                    flag = true;
                }
            }
            System.out.println("第"+(j+1)+"趟"+Arrays.toString(numArray));
            //如果没有进入三角交换则证明数组已经有序,直接退出循环即可
            //如果进入了三角交换,把flag赋值为false,来判断下一次循环是否进入三角交换
            if (flag == false){
                break;
            }else {
                flag = false;
            }
        }
    }
}

5、运行结果

8c4888464ec44754aa3a18f697269c91.png

五、算法描述

1、问题描述

 给定一个 n 个元素的数组,数组下标从 0 开始,采用冒泡排序将数组按照升序排列。

2、算法过程

整个算法过程分为以下几步:

 1) 循环迭代变量 i = 0 → n − 1 i = 0 \to n-1i=0→n−1;

 2) 每次迭代,令 j = i ,循环执行比较 a [ j ]和 a [ j + 1 ] ,如果产生 a [ j ] > a [ j + 1 ] 则交换两者的值。然后执行 j = j + 1 ,这时候对 j 进行判断,如果 j ≥ n − 1 ,则回到 1),否则继续执行 2)。

3、算法总结

 冒泡排序虽然时间复杂度比较高,但是它的实现简单 ,代码易于理解。在实际应用中,冒泡排序常常被用作教学和理论分析的基础算法, 或者用于数据量较小 的排序任务。对于数据量较大的排序任务,我们通常会选择更高效的排序算法来完成。

六、算法分析

1、时间复杂度

 最好的时间复杂度是O(n):是开始就已经有序了,那么就可以不用交换元素了,只需要1次冒泡。

 最坏的时间复杂度为O(n^2):也就是开始的时候元素是逆序的,那么每一次排序都要交换两个元素。

2、空间复杂度

 冒泡排序只需要常数级别的额外空间来存储临时变量,因此空间复杂度为 O(1)。

3、算法稳定性

 冒泡排序是一种稳定的排序算法,因为在比较相邻的元素时,只有在它们的顺序不正确时才会交换它们,因此相同元素的顺序不会被改变。


相关文章
|
C++ 索引 Python
Lua中self 、自索引及其面向对象应用代码示例
Lua中self 、自索引及其面向对象应用代码示例
|
人工智能
assert()函数(断言函数)
assert()函数(断言函数)
319 0
assert()函数(断言函数)
|
网络协议 API 微服务
在阿里云Kubernetes上运行SpringCloud示例PiggyMetrics
本文介绍了如何在阿里云Kubernetes容器服务上运行PiggyMetrics示例应用,展示了如何利用Kubernetes部署和管理一个SpringCloud典型应用的过程。
8800 0
|
NoSQL 安全 MongoDB
【MongoDB 专栏】MongoDB 的安全性考虑与实践
【5月更文挑战第11天】在数字化时代,MongoDB的数据安全至关重要。面临网络攻击、内部威胁、数据泄露和未授权访问等风险,我们需要重视MongoDB的安全性。关键措施包括身份验证和授权、数据加密、网络安全、备份和恢复、安全审计及正确配置。实践中应启用身份验证,配置访问控制,加密敏感数据,加强网络安全,并定期备份和审计。保持软件更新,结合业务需求制定安全策略,以确保数据的保密性、完整性和可用性。
524 0
【MongoDB 专栏】MongoDB 的安全性考虑与实践
|
算法 Java Go
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
【经典算法】LeetCode 67. 二进制求和(Java/C/Python3/Golang实现含注释说明,Easy)
368 2
|
消息中间件 调度 Android开发
Android经典面试题之View的post方法和Handler的post方法有什么区别?
本文对比了Android开发中`View.post`与`Handler.post`的使用。`View.post`将任务加入视图关联的消息队列,在视图布局后执行,适合视图操作。`Handler.post`更通用,可调度至特定Handler的线程,不仅限于视图任务。选择方法取决于具体需求和上下文。
279 0
|
监控 Java
Java一分钟之-NIO:非阻塞IO操作
【5月更文挑战第14天】Java的NIO(New IO)解决了传统BIO在高并发下的低效问题,通过非阻塞方式提高性能。NIO涉及复杂的选择器和缓冲区管理,易出现线程、内存和中断处理的误区。要避免这些问题,可以使用如Netty的NIO库,谨慎设计并发策略,并建立标准异常处理。示例展示了简单NIO服务器,接收连接并发送欢迎消息。理解NIO工作原理和最佳实践,有助于构建高效网络应用。
277 2
sourcetree设置忽略文件
sourcetree设置忽略文件
590 0
|
网络协议 算法 数据库
第一章OSPF协议详解
第一章OSPF协议详解
494 0
|
网络协议 算法 Linux
TCP 协议-三次握手抓包分析&查看状态
TCP 协议-三次握手抓包分析&查看状态
788 0