逻辑之美_冒泡排序

瞎扯是文章中可以略过不读的部分，当然你若欣赏我的文笔那另说;-) 过了好久，终于决定动笔写写算法了！是的如果你对文章标题感到困惑的话，其实就是写算法的。动笔写前，我想着给文章起个牛逼点的标题，思来想去，技术文章起太标题党的标题怕是不妥。但也不能太平淡吧！估计太张扬太平淡的标题都会把读者劝退。我初次想好的标题打出来是：算法之冒泡排序，看着太过无趣！多想想，所谓算法，不就是用来描述逻辑的嘛，我想着可以用文字把逻辑的美描述出来（吹了个大牛逼！），联想到吴军写的那本《数学之美》，标题到手！算法可以聊的东西太多了，我们从最初级的排序算法——冒泡排序说起。

正文

冒泡排序应该是所有排序算法里面最容易实现的。其实现思路总结起来很简单，我们以初级数据结构 数组 为例说明（感谢数组）：多次遍历一个整数数组，每次都从头开始将数组元素两两比较（因为需要两两比较所以你需要设置两个指针，用于数组元素两两比较，也用于元素值两两交换），如果第二个元素的值大于第一个元素的值就交换两元素的值。不难见得，每遍历完一次，数组中都会多出一个元素变得 部分有序 （每遍历完一次，遍历区间的最后一个数即为本次遍历的最大数，遍历区间是递减的，啥是遍历区间后面会解释到），冒泡排序其实就是个从 部分有序 到 整体有序 的一个过程（我们在本文假设数组的整体有序是指数组严格按照从小到大排列，既数组中前一个元素的值肯定不大于它后面一个元素的值，别的有序方式本文所述内容同样适用，大家发散下思维即可），嗯这么一说好像是种 减而治之 的策略，事实确实如此。我前面说的好像太书面！其实冒泡这个名字起的就很形象，你看我们每遍历一次数组，就要把当前遍历区间内的最大数放到最后面（先让最大的水泡冒出来），让最大数冒个泡~直至大水泡冒完，我们的数组达到整体有序！不难见得，我们最多只需要等于数组长度的比较次数就能完全将数组排好序。

我们先来具象化捋一遍冒泡排序的逻辑：

设现有无序数组 a = [4, 5, 2, 3, 1, 0]
    其有序状态应为 a = [0, 1, 2, 3, 4, 5]
    我们对其做下冒泡排序，具象展示如下：
数组下标：a[0]  a[1]  a[2]  a[3]  a[4]  a[5]
初始值： 4    5    2    3    1    0
第一次冒泡遍历过程：
                 4   5   2   3   1   0 (a[0] < a[1] -> 不交换值)
                 ↑   ↑ （←我们可爱的小指针）

                 4   5   2   3   1   0 (a[1] > a[2] -> 交换值)
                     ↑   ↑

                 4   2   5   3   1   0 (a[2] > a[3] -> 交换值)
                         ↑   ↑

                 4   2   3   5   1   0 (a[3] > a[4] -> 交换值)
                             ↑   ↑

                 4   2   3   1   5   0 (a[4] > a[5] -> 交换值)
                                 ↑   ↑

第一次冒泡遍历结果：4   2   3   1   0   5 (本趟遍历区间为整个数组，
                                      -- 最大的泡泡已位于本趟遍历区间最后面，
                                         既本数组最后一个元素已部分有序
                                         下次遍历区间将不包括已部分有序的部分，后同)

第二次冒泡遍历结果：2   3   1   0   4   5 (数组最后两个元素已部分有序)
                                  ------
第三次冒泡遍历结果：2   1   0   3   4   5 (数组最后三个元素已部分有序)
                              ----------
第四次冒泡遍历结果：1   0   2   3   4   5 (数组最后四个元素已部分有序)
                          --------------
第五次冒泡遍历结果：0   1   2   3   4   5 (数组最后五个元素已部分有序)
                      ------------------
第六次冒泡遍历结果：0   1   2   3   4   5 (待遍历区间就只剩一个元素了，
                  ----------------------- 还遍历个鸡儿！
                                          它肯定就是当前数组中值最小的元素，
                                          数组已整体有序)
复制代码

OK 逻辑分析完毕我们开始撸代码，先完全按照上面的分析来个易读的递归版本，用 Java 语言编写：

/**
     * @see: 冒泡排序的递归实现
     * @param array: 待排序数组，我们采用原地排序
     * @param orderRange: 数组当前已部分有序的元素个数，初始调用值应为0
     */
    public static void sortBubble(int[] array, int orderRange){
        //递归结束条件
        if (orderRange >= array.length - 1){
            return;
        }
        //指针边界,思考为啥要减2，想改成1改下下面循环的判断条件即可，注意边界肯定还要减去已部分有序的元素个数
        int bound = array.length - 2 - orderRange;
        //这样一次循环遍历就完成一次冒泡
        for (int i = 0; i <= bound; i ++){
            //判断是否需要交换两个元素的值
            if (array[i] > array[i + 1]){
                //不同下标数值交换
                int mid = array[i];
                array[i] = array[i + 1];
                array[i + 1] = mid;
            }
        }
        //递归开始下次冒泡
        sortBubble(array, orderRange + 1);
    }
复制代码

附 Kotlin 实现版本（作者最近痴迷于 Kotlin！读者可自行略过）：

``

/**
     * @see: 冒泡排序的递归实现
     * @param array: 待排序数组，我们采用原地排序
     * @param orderRange: 数组当前已部分有序的元素个数，初始调用值应为0
     */
    fun sortBubble(array: IntArray, orderRange: Int) {
        //递归结束条件
        if (orderRange >= array.size - 1) {
            return
        }
        //指针边界,思考为啥要减2，想改成1改下下面循环的判断条件即可，注意边界肯定还要减去已部分有序的元素个数
        val bound = array.size - 2 - orderRange
        //这样一次循环遍历就完成一次冒泡
        for (i in 0..bound) {
            //判断是否需要交换两个元素的值
            if (array[i] > array[i + 1]) {
                //不同下标数值交换
                val mid = array[i]
                array[i] = array[i + 1]
                array[i + 1] = mid
            }
        }
        //递归开始下次冒泡
        sortBubble(array, orderRange + 1)
    }
复制代码

这样实现的代码看着比较啰嗦，却十分易读，易于理解。到这里，你应该已经完全 get 到冒泡排序其算法是怎么回事了~

我们在实际生产环境中写排序算法肯定不能用递归，在 Java 中递归的函数调用栈太深会致开销甚大，上面主要是为便于理解来的初级版本，我们来优化成非递归版本，即双层嵌套版本：

/**
     * @see: 冒泡排序的非递归实现
     * @param array: 待排序数组，我们采用原地排序
     */
    public static void sortBubble(int[] array){
        for (int bound = array.length - 1; bound > 0; bound --){
            //这样一次循环遍历就完成一次冒泡，使得数组部分有序
            for (int i = 0; i < bound; i ++){
                //判断是否需要交换两个元素的值
                if (array[i] > array[i + 1]){
                    //不同下标数值交换
                    int mid = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = mid;
                }
            }
        }
    }
复制代码

附 Kotlin 实现版本：

/**
     * @see: 冒泡排序的非递归实现
     * @param array: 待排序数组，我们采用原地排序
     */
    fun sortBubble(array: IntArray) {
        for (bound in array.size - 1 downTo 1) {
            //这样一次循环遍历就完成一次冒泡，使得数组部分有序
            for (i in 0 until bound) {
                //判断是否需要交换两个元素的值
                if (array[i] > array[i + 1]) {
                    //不同下标数值交换
                    val mid = array[i]
                    array[i] = array[i + 1]
                    array[i + 1] = mid
                }
            }
        }
    }
复制代码

当然，你若对位运算有所了解，其实交换两个变量的值是可以不需要中间变量的：

/**
     * @see: 冒泡排序的非递归实现
     * @param array: 待排序数组，我们采用原地排序
     */
    public static void sortBubble1(int[] array){
        for (int bound = array.length - 1; bound > 0; bound --){
            //这样一次循环遍历就完成一次冒泡，使得数组部分有序
            for (int i = 0; i < bound; i ++){
                //判断是否需要交换两个元素的值
                if (array[i] > array[i + 1]){
                    //不同下标数值交换，省去中间变量
                    array[i] ^= array[i + 1];
                    array[i + 1] ^= array[i];
                    array[i] ^= array[i + 1];
                }
            }
        }
    }
复制代码

附 Kotlin 实现版本：

/**
     * @see: 冒泡排序的非递归实现
     * @param array: 待排序数组，我们采用原地排序
     */
    fun sortBubble1(array: IntArray) {
        for (bound in array.size - 1 downTo 1) {
            //这样一次循环遍历就完成一次冒泡，使得数组部分有序
            for (i in 0 until bound) {
                //判断是否需要交换两个元素的值
                if (array[i] > array[i + 1]) {
                    //不同下标数值交换，省去中间变量
                    array[i] = array[i] xor array[i + 1]
                    array[i + 1] = array[i + 1] xor array[i]
                    array[i] = array[i] xor array[i + 1]
                }
            }
        }
    }
复制代码

OK 代码我们就撸到这里，总结一下冒泡排序算法。估计看到双层嵌套循环你就能猜到冒泡排序算法的平均 时间复杂度为：O(n^2)

事实确实如此，至于更具体的数值比较次数和交换次数分析，留给读者。

除去原数组本身所需要的存储空间外，冒泡排序算法实现所需额外辅助 空间为：O(1)

尾巴

以上代码我本来都还想附上 C++ 版本的！当时在学校我 C++ 学的还挺不错的，可工作后主力用 Java，C++基本上忘光了！

计划后期补上！

后续文章考虑不贴 Koltin 代码了！

看完你可能觉得文章标题挺唬人的！不就是聊聊最基础的算法嘛，吹什么逻辑之美，哈哈我乐意~

冒泡排序是所有排序算法里面最简单的，下篇我们聊聊同样很简单的选择排序

完。