《恋上数据结构与算法》排序（一）：冒泡排序

妖狐艹你老母 2022-12-29 09:07 157阅读 0赞

# 一、经典十大排序算法 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

## 冒泡排序（Bubble Sort） ##

*  冒泡排序（Bubble Sort）的基本思想是：通过对待排序数组从头到尾遍历（从索引较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从数组头部移向尾部，就象水底下的气泡一样逐渐向上冒。

### 1、算法步骤 ###

*  `从头开始比较每一对相邻元素`，如果第一个比第二个大，就交换它们的位置。
 *  **执行完一轮后，最末尾那个元素就是最大元素。**
 *  忽略上一步中曾经找到的最大元素，重复执行步骤一，直到全部元素有序。

![请添加图片描述][20201222230501864.gif]

### 2、代码实现 ###

public static void bubbleSort1(Integer[] array) { 
        // 这里end > 0为终止条件, 只有end>0,也就是说,end为1的时候,它还可以和它前面的进行比较.
        // end为0的时候, 它前面就没有元素了
        for (int end = array.length - 1; end > 0; end--) { 		// 一共比较多少趟
            for (int begin = 1; begin <= end; begin++) { 		// 每一趟中的最大元素
                if (array[begin - 1] > array[begin]) { 
                    int temp = array[begin - 1];
                    array[begin - 1] = array[begin];
                    array[begin] = temp;
                }
            }
        }
    }

*  `关于end的范围`  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

### 3、代码优化 ###

#### 1、 第一种优化 ####

*  如果`序列已经完全有序`，可以`提前终止冒泡排序。`  
    ![img][]
 *  增加一个`boolean`值，**`用于判断每一次循环后`是否有`数据交换(交换元素)`**，如果没有，则退出排序。说明数组元素是有序的
 *  `如果数据不是完全有序，此优化会因添加成员变量而导致计算时间更长。`

// 针对下面的方式做优化(当给的数组本来就是有序的,此时就需要优化,不用一一比较了)
    public static void bubbleSort2(Integer[] array) { 
        for (int end = array.length - 1; end > 0; end--) { 
            // 这个变量写在这里,是为了判断每一趟排序操作是否将序列变为完全有序.
            // 因为有可能在某一趟之后, 数组的元素就变为完全有序了
            boolean sorted = false; // 是否排过序
            for (int begin = 1; begin <= end; begin++) { 
                // 如果不进入下面的判断,表示本轮循环肯定是有序的
                if (array[begin - 1] > array[begin]) { 
                    int temp = array[begin - 1];
                    array[begin - 1] = array[begin];
                    array[begin] = temp;
                    sorted = true;  // 排过序
                }
            }
            if (!sorted) break;
        }
    }

##### 2、 第二种优化 #####

*  如果`序列尾部`已经`局部有序`，可以`记录最后一次交换的位置，减少比较次数。`
 *  11元素后面的, 都不比较了

![img][img 1]

*  记录`上一次循环最后一次交换`的位置，将其`作为下一次循环的截止位置`。

public static void bubbleSort3(Integer[] array) { 
        for (int end = array.length - 1; end > 0; end--) { 
            // sortedIndex=1,是针对完全有序的情况: 因为完全有序下,就不会走到下面的if判断. 所以初始值给1. 最后end=1,一轮扫描就结束了
            int sortedIndex = 1; // 从哪个索引开始,后面的都已经排好序了
            for (int begin = 1; begin <= end; begin++) { 
                // 如果不进入下面的判断,表示本轮循环肯定是有序的
                if (array[begin - 1] > array[begin]) { 
                    int temp = array[begin - 1];
                    array[begin - 1] = array[begin];
                    array[begin] = temp;
                    // 记录最后一次交换的位置
                    sortedIndex = begin;
                }
            }
            // 将最后一次交换的位置,给end, 作为下次循环的终点
            end = sortedIndex;
        }
    }

*  平均时间复杂度`O(n^2)`
 *  最好时间复杂度`O(n)`
 *  空间复杂度`O(1)`

#### 4、排序算法的稳定性（Stability） ####

*  如果`相等的2个元素`，`在排序前后的相对位置保持不变`，那么这是`稳定`的排序算法。
    
     *  排序前：`5，1，3a，4，7，3b`
     *  稳定的排序：`1，3a，3b，4，5，7`
     *  不稳定的排序：`1，3b，3a，4，5，7`
 *  冒泡排序是`稳定排序`算法。
    
    > 因为: 冒泡排序过程中, `两个相同的元素根本就不会比较`, 只有`左边的元素 > 右边的元素`才会进行交换排序。所以冒泡排序是稳定的排序。  
    > ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

#### 5、原地算法（In-place Algorithm） ####

*  不依赖额外的资源或依赖少数的额外资源，仅依靠输出来覆盖输入。
 *  空间复杂度为`O(1)`的都可以认为是原地算法。
 *  非原地算法，称为`Not-in-place`或者`Out-of-place`。
 *  冒泡排序属于`In-place`。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/ad3b05e3326349c286b8a839a2c54f95.png
[20201222230501864.gif]: /images/20221120/971705c1fd08468f88f81d3c12d5821e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20221120/81cb39214364481a828919532e5b7d37.png
[img]: /images/20221120/ab64f93ed4024b88934f414fc2bbcc04.png
[img 1]: /images/20221120/ae5b74882e1d4e198d02240b360ce8a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20221120/b959a67bcad345f391ec970810e0a576.png