白话解析冒泡排序优化

ゝ一世哀愁。 2023-05-29 02:28 86阅读 0赞

冒泡排序就是每2个相邻的数据进行比较后，按照升降序进行交换，每次排序至少会让一个最大或最小的元素（默认从左至右排序，升序为最大元素，降序为最小元素）移动至队尾，重复N次后，完成此次排序。

假设我们用 **2,5,1,3,4,6 **这个整型数组进行排序。

我们首先看下**优化前**的冒泡排序:

public static int[] bubbleSort(int a[]){
            int n=a.length;
            for(int i=0;i<n;i++){
                for(int j=0;j<n-i-1;j++){
                    if(a[j]>a[j+1]){
                        int tmp=a[j];
                        a[j]=a[j+1];
                        a[j+1]=tmp;
                    }
                }
           
            }
            return a;
        }

排序过程 :

#                                 初始            2,5,1,3,4,6                                   第一次        2,1,3,4,5,6                                   第二次        1,2,3,4,5,6                                   第三次        1,2,3,4,5,6                                   第四次        1,2,3,4,5,6                                   第五次        1,2,3,4,5,6                                   第六次        1,2,3,4,5,6 #

#   **结论：** #

我们可以看到这个原始的冒泡排序，排序次数为**6**次。在第二次之后数组已经是有序的，其中第三、四、五、六次排序都是多余的。

**优化后:**

public static int[] bubbleSort(int a[]){
            int n=a.length;
            for(int i=0;i<n;i++){
                boolean flag=true;
                for(int j=0;j<n-i-1;j++){
                    if(a[j]>a[j+1]){
                        int tmp=a[j];
                        a[j]=a[j+1];
                        a[j+1]=tmp;
                        flag=false;
                    }
                }
                if(flag)break;
            }
            return a;
        }

**排序过程 : **

#                                 初始            2,5,1,3,4,6                                   第一次        2,1,3,4,5,6                                   第二次        1,2,3,4,5,6 #

#  优化解析： #

主要优化为我们加了 flag 布尔变量，在以 j 为局部变量的内层循环中，如果某次排序时没有发生数据交换，那么我们认为此整型数组已经达到完全有序。

为什么是这样呢：

我们看上面优化的代码，在第 3 次后就没有发生数据交换了。此时, 由于 **i=2** **n=6 **,  内层循环为: **for(int j=0; j<3;j++)**  会将前3个元素**1,2,3**，分别与相邻的元素 **2,3,4 **比较：发现均是有序，无需发生数据交换，则前4个元素一定是完全有序的，而后2个元素已经是冒泡后最大的2个数据，所以 **当某次排序时没有发生数据交换，那么我们认为此整型数组已经达到完全有序。**

#   **结论：** #

我们可以看到这个优化后的冒泡排序，排序次数为**2**次。而优化前排序次数为 6 次，减少4次的排序时间。细心观察我们会发现减少的次数与数组的 **有序度 **相关。

那么**什么是有序度：顾名思义就是初始数组的有序（升序或降序）对的个数**，我们以 上述的 **2,5,1,3,4,6** 数组为例，默认为从左至右的升序，也就是只要前面的元素小于后面的元素即算一个有序对，它有序度为 **11**，有兴趣的同学可以将有序元素对发至评论中。

也就是有序度越高，优化后的排序次数就会越少。

**扩展与发散：**

**   **  事实上根据有序度来优化排序的这种思想，在JDK中早就有了就是 Arrays.sort() 的  **DualPivotQuicksort.sort()** 方法，它是 Collections.sort() 集合排序时的排序方法,中文名为 **双轴基准快速排序**，下面这段代码就是采用的这种思想:

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70][]

上述的代码表示：当数组的有序度非常高时，会采用[归并算法][Link 1]使数组有序，而归并算法就是专门针对有序的数组来排序的。

**总结：**

**      当我们在初识算法的时候可以使用一组具体的数据代入，然后对代码逐行的分析，直至完全理解后。再去思考能否用更优的方式去解决这个问题，以更优的方式解决后，继续去思考能否将这种优化方式代入到其他的算法中，最后去总结复盘。**

**      当我们遇到任何问题都采用上述的思考方式周而复始的思考一遍之后，我们的思维深度会逐步增加，解决问题的能力会越来越强，代码bug才会越来越少，薪资则会越来越高。**

**通俗点说：不要急，耐心点，谁不是从hello world开始的呢**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019110116160552.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1JveWFsX2xy,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/Royal_lr/article/details/102957074