献给我自己

瞎扯

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

正文

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

Tips：部分有序 和 整体有序

设现有数组 [3, 5, 4, 2, 1, 0] ，我们现在需要对其排个序使其变成完全按值从小到大的排列的整体有序。

对于如此简短的数组，我们可一眼看出其变成整体有序时，最后一个元素必然是5，这相当于使其变成

[3, 4, 2, 1, 0, 5]

这时我们会说此数组最后一个元素已达成部分有序，此时继续为此数组排序时可以忽略最后一个元素，即部分有序的部分。是的，此时我们要处理的问题减小了一个元素的规模。

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

设现有无序数组 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 代码了！

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

欢迎上当~

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

完。