Carson带你学数据结构：图文详解冒泡排序 & 优化

梦里梦外; 2022-12-14 13:47 200阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

# 前言 #

本文主要讲解排序算法中最简单的冒泡排序算法，希望你们会喜欢。

--------------------

# 目录 #

![示意图][37dcd8f8b2241d830b93b3a6d1d1ef48.png]

--------------------

# 1. 简介 #

属于 内排序算法中 的 **交换排序类别**

--------------------

# 2. 算法思想 #

1.  自下而上对 相邻的2个数依次 比较 & 调整
2.  若 反序 则交换，直到 无反序的记录 为止。

> 较大的数往下沉，较小的数类似气泡一样往上冒，故称：冒泡排序

--------------------

# 3. 算法示意图 #

整个过程就跟冒泡一样，最小值一直往上“冒泡”，具体如下：

a. 2与6对比：因2<6，所以交换位置

![示意图][326612686d5e372a7a5e287ad7153871.png]

b. 2与4对比：因2<4，所以交换位置

![示意图][62b3aa61e8b2691b58304731c7c8cdbd.png]

c. 2与7对比：因2<7，所以交换位置  
![示意图][330911a62820c096e6b2bda6c2305753.png]

以此类推，最终将序列中最小值放到了首位（冒上来了）

![示意图][9e50d1fec64e05650270bf83cae60654.png]

--------------------

# 4. 算法实现 #

### 4.1 具体代码 ###

具体请看注释

public class BubbleSort {
    
        /**
         * 基本的 冒泡排序
         */
        public static void bubbleSort(int[] srcArray) {
            int i,j; // 用于存放数组下标
            int temp = 0; // 用于交换数值时临时存放值
    
            for(i=0;i<srcArray.length-1;i++){
                // j 从后往前循环
                for(j=srcArray.length-2;j>=i;j--){
                    // 若前者＞后者，则交换位置
                    if(srcArray[j]>srcArray[j+1]){
                        temp=srcArray[j];
                        srcArray[j]=srcArray[j+1];
                        srcArray[j+1]=temp;
                    }
                }
            }
    
            // 输出排序后的序列
            for(int a =0;a<srcArray.length;a++)
                System.out.println(srcArray[a]);
        }
    
        /**
         * 执行 冒泡排序
         */
        public static void main(String[] args) {
    
            // 定义待排序数列
            int[] src = new int[]{9, 1, 5, 8, 3, 7, 4, 2, 6};
            // 输出结果
            bubbleSort(src);
        }
    }

### 4.2 算法示意图 ###

1.  当 i =0时，算法示意图如下：

![示意图][b00a06a158f9c408f87830491862407d.png]

1.  当 i =1时，算法示意图如下：

![示意图][90d9d4a175e3ded7652cd67db8f654c5.png]

1.  i = 2、3、4依次类推…

### 4.3 最终测试结果 ###

1
    2
    3
    4
    5
    6
    7
    8
    9

*  `Demo`地址  
    [Carson\_Ho的Github地址：冒泡排序][Carson_Ho_Github]

--------------------

# 5. 算法优化 #

*  简介

![示意图][85cc7f11608488626b294d9e509eb5e5.png]

*  具体实现

public class BubbleSort {
        /**
         * 优化的 冒泡排序
         */
        public static void bubbleSortOpti(int[] srcArray) {
    
            int i,j; // 用于存放数组下标
            int temp = 0; // 用于交换数值时临时存放值
    
            // 标记位
            // flag = true：代表存在数据交换，即序列仍需排序，需继续循环
            // flag = false：代表不存在数据交换，即序列不需排序，已经是有序序列了，可停止循环
            Boolean flag = true;
            // 若flag = false时退出循环
            for(i=0;i<srcArray.length-1 && flag;i++){
    
                flag = false; // 初始化为false
    
                // j 从后往前循环
                for(j=srcArray.length-2;j>=i;j--){
                    // 若前者＞后者，则交换位置
                    if(srcArray[j]>srcArray[j+1]){
                        temp=srcArray[j];
                        srcArray[j]=srcArray[j+1];
                        srcArray[j+1]=temp;
                        flag = true; // 若有数据交换，则说明序列仍未无序
                    }
                }
            }
    
            // 输出排序后的序列
            for(int a =0;a<srcArray.length;a++)
                System.out.println(srcArray[a]);
        }
    
        /**
         * 执行 优化后的冒泡排序
         */
        public static void main(String[] args) {
            // 定义待排序数列
            int[] src = new int[]{2, 1, 3, 4, 5, 6, 7, 8, 9};
            // 输出结果
            bubbleSortOpti(src);
        }
    }

--------------------

# 6. 性能分析 #

以下将分析算法的性能：时间复杂度、空间复杂度、稳定性  
![示意图][411a08e7ed696f6a59874ad868a9596f.png]

--------------------

# 7. 总结 #

*  本文主要讲解了 排序算法中 的冒泡排序
 *  下面我将继续讲解 **数据结构**，有兴趣可以继续关注[Carson\_Ho的安卓开发笔记][Carson_Ho]

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: /images/20221123/ddd9d8fe9d8c46feadb3f5969883ffa9.png
[37dcd8f8b2241d830b93b3a6d1d1ef48.png]: /images/20221123/c7c02b92eb4c4efd98c69dba5f8e2ef4.png
[326612686d5e372a7a5e287ad7153871.png]: /images/20221123/488650c33eea4da59439ac30fb2b0507.png
[62b3aa61e8b2691b58304731c7c8cdbd.png]: /images/20221123/7f00a8f7f9ec41c8894b88d4f71cff13.png
[330911a62820c096e6b2bda6c2305753.png]: /images/20221123/f5a42b10d503414b8b1622d09dba2b2a.png
[9e50d1fec64e05650270bf83cae60654.png]: /images/20221123/d7c2a24d57024af98871f4f111be4b25.png
[b00a06a158f9c408f87830491862407d.png]: /images/20221123/655b017c23cd4dcfbce4e2533529efc7.png
[90d9d4a175e3ded7652cd67db8f654c5.png]: /images/20221123/89bf06387ace44e3a0479161ded811ae.png
[Carson_Ho_Github]: https://github.com/Carson-Ho/AlgorithmLearning
[85cc7f11608488626b294d9e509eb5e5.png]: /images/20221123/8b9d6cb3814a4b59bf681fa66d737142.png
[411a08e7ed696f6a59874ad868a9596f.png]: /images/20221123/660f95b5e8be4a03a1f343ba18522ebb.png
[Carson_Ho]: https://blog.csdn.net/carson_ho