冒泡排序——《图解算法》

清疚 2022-05-16 14:35 173阅读 0赞

冒泡排序分**从大到小**和**从小到大**两种排序方式。它们的唯一区别就是两个数交换的条件不同，从大到小排序是前面的数比后面的小的时候交换，而从小到大排序是前面的数比后面的数大的时候交换。我这里只说 从小到大的排序方式。

**冒泡排序的原理**：从第一个数开始，依次往后比较，如果前面的数比后面的数大就**交换**，否则不作处理。这就类似烧开水时，壶底的水泡往上冒的过程。

### 一、 图解分析 ###

现以数组\[8,7,6,4,5\]为例，我们通过将这个数组按**从小到大**的方式排序，来说明冒泡排序的过程。

**第一次循环**：此次循环的多次比较交换，使最大的数字8冒到最上面。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pjbF9sb3ZlX3d4_size_16_color_FFFFFF_t_70]

**第二次循环**：此次循环中的多次比较和交换，使7往上冒，最终排到倒数第二个位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pjbF9sb3ZlX3d4_size_16_color_FFFFFF_t_70 1]

你会发现，这次循环比前面少一次循环比较。

这是因为第一次循环时已经把最大的8排到最上面的位置了，这次排序肯定不会去占用最上面的位置的，所以此时比较次数可以比前面少一次。

**第三次循环**：同理，此时6会往上冒。比较次数同理又会比前面少一次。  
![在这里插入图片描述][20181101093020370.png]

此时看着最后的结果已经是从小到大了，这是因为在原始数组中，5就在4的上面。

但实际我们不知道5是在4的上面，我们就得继续完成最后一次循环比较。

**第四次循环**： 5已经排在4的上面了，比较后不交换。  
![在这里插入图片描述][20181101093125443.png]

### 二、代码实现 ###

总结前面的图解，数组长度设为n。外层共循环了n-1次，外层循环增加一次，对应内层循环就 减少一次。  
外层循环为：for (int i = 0; i < arr.length-1; i++)  
内层循环为：for (int j = 0; j < arr.length - 1 - i; j++)

int[] arr = {8, 7, 6, 4, 5};
            
            for (int i = 0; i < arr.length-1; i++) {
            
                for (int j = 0; j < arr.length - 1 - i; j++) {
                
                    if (arr[j] > arr[j + 1]) {
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                    
                }
                
            }

需要注意的是，在里层的for循环里，j的取值范围是arr.lenght - 1 - i。

### 三、冒泡排序算法的优化 ###

具体的优化得看具体的情况

**1. 减少外层循环次数的优化**

如有数组\[8,7,6,1,2,3,4,5\]，当我们将8、7、6三个数都排在后面后，其实就不需要继续循环比较了。

那我们如何知道的面不再需要比较了呢？答案就是如果该次循环没有发生一次数的交换，就说明数组已经排好序了，那么后面的循环比较就可以停止了。

代码如下：

int[] arr = {8, 7, 6, 1, 2, 3, 4, 5};
    		
            // flag: 在一次循环中是否发生过数据交换。true：表示发生过交换，false：表示未发生过交换
            boolean flag = true;
            
            for (int i = 0; i < arr.length - 1; i++) {
                // 如果未发生交换，则break
                if (!flag) {
                    break;
                }
                flag = false; // 每次循环都先置为false，即认为不会发生交换
                for (int j = 0; j < arr.length - i - 1; j++) {
                    if (arr[j] > arr[j + 1]) {
                        flag = true;// 发生了交换
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
                System.out.println(i);
            }

从输出结果看，外层循环只循环了4次，而不会是7次。

**2. 减少内层循环次数的优化**

如有数组\[2, 4, 3, 1, 5, 6, 7, 8, 9\]，你会发现，从5开始都是不用比较和循环了。所以我们要想办法减少后面的循环和比较。

我们可以发现，当我们把4交换到5前面后，后面的每次循环里都不再发生交换。即，如果我们将第一次出现该次不再交换数据时的位置下标找到，然后把这个值作为内层循环j的上限值。这样内层循环就会减少一些循环。所以内层循环的 j 的上限值是动态值。

代码如下：

int[] arr = {4, 2, 3, 1, 5, 6, 7, 8, 9};
            
            // flag: 在一次循环中是否发生过数据交换。true：表示发生过交换，false：表示未发生过交换
            boolean flag = true;
            
            // 上一次内层循环上界值，在第一次循环时与arr.length-1-i相等，即：arr.length-1。也就是说默认是最后一个
            int k = arr.length - 1;
            
            for (int i = 0; i < arr.length - 1; i++) {
                // 如果未发生交换，则break
                if (!flag) {
                    break;
                }
                
                 // 每次循环都先置为false，即认为不会发生交换
                flag = false;
                
                // 记录上一次内层循环时最后一次交换的位置
                int last = 0;
                
                for (int j = 0; j < k; j++) {
                    if (arr[j] > arr[j + 1]) {
                        // 发生了交换
                        flag = true;
                        // 记录每次交换的位置
                        last = j;
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    } 
                }
                // 让下一次循环的上界值变成此次循环的最后一次交换的位置
                k = last; 
            }

k为动态值有个好处，即随时动态调整上一次最后交换的位置。这样做的好处是，当遇到数组中有紧挨着的数是连续的时候就会在下一次循环时省略它们的比较。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pjbF9sb3ZlX3d4_size_16_color_FFFFFF_t_70]: /images/20220503/2f87c8f231614d5c8bd1c60bf4382f83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pjbF9sb3ZlX3d4_size_16_color_FFFFFF_t_70 1]: /images/20220503/7f5df1dcfd3a4900b60d3d12448ae723.png
[20181101093020370.png]: /images/20220503/98573aa34f2c40bb896ec3a4140f75b9.png
[20181101093125443.png]: /images/20220503/5aa701d496774dc99194e0bc16099839.png