排序算法图解（一）：冒泡排序与冒泡排序的优化

以你之姓@ 2023-09-23 13:39 84阅读 0赞

### 文章目录 ###

*  1 冒泡排序简介
 *  2 图解算法
 *  3 冒泡排序代码实现
 *  4 冒泡排序算法的优化
 *  写在最后

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

# 1 冒泡排序简介 #

冒泡排序（Bubble Sorting）即：通过对待排序的序列从前往后，依次比较相邻元素的值，若发现逆序则交换位置，使较大的元素逐渐移动到后部，就像水底的气泡一样逐渐从水面冒出来，这就是冒泡名称的由来。  
![在这里插入图片描述][a48879847f5844129d1267369c885e00.png_pic_center]

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

# 2 图解算法 #

**以将序列\{3, 9, -1, 10, -20\}从小到大排序为例！**  
基本思想就是，在每一趟排序实现将最大的数移到序列的最后端！这主要通过比较相邻两个元素实现，**当相邻的两个元素逆序的时候，我们就交换它们。**

**第1趟排序：**  
第1趟排序共比较了4次，**将最大的数10冒泡到了序列的尾部。**  
![在这里插入图片描述][1017f38e7da9408c8a0dabd4872d0994.png]

**第2趟排序：**  
由于第一趟排序已经将最大是数10给冒泡到了最末端，因此在本次排序中，不需要再比较最后一个元素，故共比较了3次，**将子序列（前四个元素）中最大的数9（整个序列中倒数第二大的数）冒泡到了子序列的尾端（原序列的倒数第二个位置）。**

![在这里插入图片描述][28221914cc884034990f502da10fc258.png]

**第3趟排序：**  
在第三趟排序时，同理，倒数两个元素位置已经确定，即第一、第二大的数已经排好位置，只需要再将倒数第三大的数确认即可。故比较2次，实现倒数第三大的数3的位置确定。  
![在这里插入图片描述][de3b509afb534f389d524eb5896fe924.png]

**第4趟排序：**  
在第四趟排序时，只有第一、第二个元素的位置还不确定，只需要比较一次，若逆序，则交换即可。到此，排序算法完成，原序列已经排序成为一个递增的序列！  
![在这里插入图片描述][509134afe9c94d8ba6f99b8e88db03c9.png]

**小结**

*  一共进行了数组大小-1次趟排序，即外层循环arr.length-1次；
 *  每趟排序进行了逐趟减小次数的比较，即内层循环arr.length-i-1次，i从0依次增加。

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

# 3 冒泡排序代码实现 #

参考代码如下，为了便于观察结果，在循环中添加了相应的输出语句：

import java.util.Arrays;
    
    /**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 冒泡排序
     */
    public class BubbleSort {
        
    
        public static void main(String[] args) {
        
            int[] array = {
        3, 9, -1, 10, -20};
            //排序前
            System.out.println("排序前:" + Arrays.toString(array));
    
            //冒泡排序
            for (int i = 0; i < array.length - 1; i++) {
        
                System.out.println("第" + (i+1) + "趟排序开始!");
                for (int j = 0; j < array.length - i - 1; j++) {
        
                    //如果前面的数比后面的数大，则交换
                    if(array[j] > array[j+1]){
        
                        //交换
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                    System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
                }
                System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
                System.out.println("================================================");
            }
    
            //输出排序后的结果
            System.out.println("排序后:" + Arrays.toString(array));
        }
    }

实现结果：  
![在这里插入图片描述][491405fccace42ceb124817dc9ca2282.png]

# 4 冒泡排序算法的优化 #

举个例子，将待排序的序列改为：\{5，1，2，3，4\}，用以上算法来处理，观察一下结果：  
![在这里插入图片描述][509766c2d24c46ca926a162d155764ce.png]  
可以发现，**当第一趟排序结束的时候，序列已经排序完成：** 即将5冒泡到了最后，序列实现了从小到大排序。**但是原冒泡排序算法，还是义无反顾的进行了数组大小-1趟排序（我可真是大冤种！）**

因此，我们需要尝试对算法进行优化！  
发现：在冒泡排序的过程中，各个元素都在不断的接近自己的位置，**如果下一趟比较中没有进行过任何交换，则说明序列已经有序，** 则排序算法已经可以返回结果。因此，**考虑在排序算法过程中添加一个标志flag判断元素是否进行过交换，以减少不必要的冤种行为！**

**优化代码如下：**

import java.util.Arrays;
    
    /**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 冒泡排序优化
     */
    public class BubbleSort {
        
    
        public static void main(String[] args) {
        
            int[] array = {
        5, 1, 2, 3, 4};
            //排序前
            System.out.println("排序前:" + Arrays.toString(array));
    
            boolean flag = false; //用于标记是否进行了交换，true则说明进行了交换，false表示无
    
            //冒泡排序
            for (int i = 0; i < array.length - 1; i++) {
        
                System.out.println("第" + (i+1) + "趟排序开始!");
                for (int j = 0; j < array.length - i - 1; j++) {
        
                    //如果前面的数比后面的数大，则交换
                    if(array[j] > array[j+1]){
        
                        //交换
                        flag = true; //标记进行了交换
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                    System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
                }
                System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
                System.out.println("================================================");
                if (!flag){
        
                    //如果没有进行交换则直接退出，说明排序已经完成
                    break;
                }else {
        
                    //回退
                    flag = false;
                }
            }
    
            //输出排序后的结果
            System.out.println("排序后:" + Arrays.toString(array));
        }
    }

四趟排序，优化成了只需要两趟排序！又是一个不可多得的小技巧！在算法程序题中，flag的设置是一种常用的编程思想，常常用于回溯算法中，小伙伴们要学会举一反三~  
![在这里插入图片描述][76c2346faf2a42e390fc000111927bb1.png]

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

# 写在最后 #

**本文被 [Java数据结构][Java] 收录[点击订阅专栏][Java]** ， 持续更新中。  
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！

![在这里插入图片描述][7e0ff0501697426a84cd0a1f4eecfdc1.gif_pic_center]

[a48879847f5844129d1267369c885e00.png_pic_center]: https://img-blog.csdnimg.cn/a48879847f5844129d1267369c885e00.png#pic_center
[1017f38e7da9408c8a0dabd4872d0994.png]: https://img-blog.csdnimg.cn/1017f38e7da9408c8a0dabd4872d0994.png
[28221914cc884034990f502da10fc258.png]: https://img-blog.csdnimg.cn/28221914cc884034990f502da10fc258.png
[de3b509afb534f389d524eb5896fe924.png]: https://img-blog.csdnimg.cn/de3b509afb534f389d524eb5896fe924.png
[509134afe9c94d8ba6f99b8e88db03c9.png]: https://img-blog.csdnimg.cn/509134afe9c94d8ba6f99b8e88db03c9.png
[491405fccace42ceb124817dc9ca2282.png]: https://img-blog.csdnimg.cn/491405fccace42ceb124817dc9ca2282.png
[509766c2d24c46ca926a162d155764ce.png]: https://img-blog.csdnimg.cn/509766c2d24c46ca926a162d155764ce.png
[76c2346faf2a42e390fc000111927bb1.png]: https://img-blog.csdnimg.cn/76c2346faf2a42e390fc000111927bb1.png
[Java]: https://blog.csdn.net/m0_60353039/category_12062687.html
[7e0ff0501697426a84cd0a1f4eecfdc1.gif_pic_center]: https://img-blog.csdnimg.cn/7e0ff0501697426a84cd0a1f4eecfdc1.gif#pic_center