排序算法丨冒泡排序

前言

冒泡排序(Bubble Sort)，在概念上是最简单的排序算法，但效率也不高。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

排序思路

依次比较相邻的两个元素：

当一个元素大于右侧相邻元素时，交换它们的位置；
当一个元素小于或等于右侧相邻元素时，位置不变；
重复步骤1和步骤2，直至全部排序完成。

代码实现

通常来说，冒泡排序有三种写法：

第一种写法

第一种就是最原始的写法，使用双循环来进行排序：外部循环控制所有的回合，内部循环代表每一轮的冒泡处理，先进行元素比较，再进行元素交换。

public static void sort1(int array[]) {
    int tmp = 0;
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - 1 - i; j++) {
            // 左侧元素大于右侧元素，则交换
            if (array[j] > array[j + 1]) {
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
        System.out.println("第" + (i+1) + "轮：" + Arrays.toString(array));
    }
}

最外层的 for 循环每经过一轮，剩余数字中的最大值就会被移动到当前轮次的最后一位，中途也会有一些相邻的数字经过交换变得有序。总共比较次数是(n-1)+(n-2)+(n-3)+…+1。

其中，关于两个数字的交换，不使用中间变量 tmp 也可以完成

arr[j + 1] = arr[j + 1] + arr[j];
arr[j] = arr[j + 1] - arr[j];
arr[j + 1] = arr[j + 1] - arr[j];

arr[j + 1] = arr[j] - arr[j + 1];
arr[j] = arr[j] - arr[j + 1];
arr[j + 1] = arr[j + 1] + arr[j];

由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是O(N²)。但这种写法有待优化，通过输出语句可以观察每一轮的排序结果：

经过第4轮排序后，整个数列已经是有序的了；可是排序算法仍然“兢兢业业”地继续执行第5轮排序，直到第8轮。
这种情况下，如果能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。

第二种写法

第二种写法就是在第一种的基础上进行优化，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。

public static void sort2(int array[]) {
    int tmp  = 0;
    for (int i = 0; i < array.length; i++) {
        //有序标记，每一轮的初始是true
        boolean isSorted = true;
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j+ 1]) {
                tmp = array[j];
                array[j] = array[j+ 1];
                array[j+ 1] = tmp;
                //有元素交换，所以不是有序，标记变为false
                isSorted = false;
            }
        }
        if (isSorted){
            break;
        }
        System.out.println("第" + (i+1) + "轮：" + Arrays.toString(array));
    }
}

优化后结果：

第三种写法

解决“整体有序后依然排序”的问题后，其实，还存在“部分有序后依然排序”的问题。观察每一轮的排序结果，可知

第1轮排序后，数组内最大的元素“99”排在了数组的最后；
第2轮排序后，第二大的元素“88”排在了数组的倒数第二；
第3轮排序后，第三大的元素“77”排在了数组的倒数第三；
......

每完成一轮排序，数组内右侧的有序元素不断增加，形成一个有序区。但是即使右侧的元素是有序的，每一次内部循环都重复比较了。按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2......实际上，数列真正的有序区可能会大于这个长度，例如，部分有序的数组：[33, 44, 55, 66, 11, 22, 99, 88, 77]。这个数组，仅在第2轮排序，后面5个元素就已经是有序的了，因此后面的许多次元素比较是没有意义的。

如何避免这种不必要的比较呢？可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。第三种写法是在第二种写法的基础上进一步优化：

public static void sort3(int array[]) {
    int tmp = 0;
    //记录最后一次交换的位置
    int lastExchangeIndex = 0;
    //无序数列的边界，每次比较只需要比到这里为止
    int sortBorder = array.length - 1;
    for (int i = 0; i < array.length;i++) {
        //有序标记，每一轮的初始是true
        boolean isSorted = true;
        for (int j = 0; j < sortBorder; j++) {
            if (array[j] > array[j + 1]) {
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                //有元素交换，所以不是有序，标记变为false
                isSorted = false;
                //把无序数列的边界更新为最后一次交换元素的位置
                lastExchangeIndex = j;
            }
        }
        sortBorder = lastExchangeIndex;
        if (isSorted){
            break;
        }
        System.out.println("第" + (i+1) + "轮：" + Arrays.toString(array));
    }
}

sortBorder就是无序数列的边界。每一轮排序过程中，sortBorder之后的元素就完全不需要比较了，肯定是有序的，这样又提高了排序效率。

动画演示

演示动画来自于visualgo

如图所示，未排序的元素为浅蓝色，正在对比交换的元素为深绿色，已经有序的元素标记为橙黄色。

复杂度分析

一般来说，数组中有N个数据项，则第一轮排序中有（N-1）次比较，第二轮中有（N-2）次比较，如此类推，不难得出它的求和公式：（N-1）+（N-2）+（N-3）+...+1 = N *（N-1）/2。所以，算法做了约（N²/2）次比较（可以忽略-1，影响不大，尤其当 N 很大时），交换的次数一般少于比较的次数。最好的情况是数据是正序的，那么只需要比较不需要交换；最坏的情况是数据是逆序的，那么每次比较都需要交换；而在一般情况下，数据是随机的，大概只有一半左右的数据需要交换，则交换的次数为（N²/4）。
交换和比较的次数都与 N² 都成正比，由于常数项（1/2、1/4）可以忽略，那么平均时间复杂度为O(N²)。

参考

程序员小灰
 Github
data-flair
LeetCode

冒泡排序升级版就是鸡尾酒排序。