排序算法：冒泡排序

前言

对于Java程序员来说，一般对于算法没有什么要求，但是有一个算法除外——排序算法。排序算法不仅在日常开发中经常用到，还是面试中几乎必问的题目，并且通常是以“手写代码”的形式出现，因此掌握好排序算法是对每一个程序员的最基本要求。

谈到排序算法，第一个浮现在我们脑中的一定是“冒泡排序”。“冒泡排序”由于较简单的过程，得到大多数程序员的“厚爱”，本文将简单的介绍排序算法的整个过程。

基本思想

冒泡排序算法的运作如下：

1.    比较两个相邻的数，如果前面的数大于后面的数，则将这两个数交换位置。第一次遍历后，最大的数会被放到数组的最后位置，即array[length - 1]。

2.    第二次遍历时跳过最后一个元素，因为该元素通过第一次遍历已经确定是最大值。

3.    持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

例子

下面通过一个例子来看看冒泡排序是怎么工作的。红色的数为正在比较的数，原数组如下。

第一次循环：

1.首先比较array[0]和arary[1]，即19和15；因为19 > 15，因此交换两个数的位置，交换完的数组如下。

比较和交换对应的代码如下：

if (array[j] > array[j + 1]) {
    int temp = array[j];
    array[j] = array[j + 1];
    array[j + 1] = temp;
}

2.接着比较array[1]和array[2]，即19和37；因为19 < 37，因此两个数的位置不变，如下。

3.最后比较array[2]和array[3]，即37和12；因为37 > 12，因此交换两个数的位置，交换完的数组如下。

至此第一次循环结束，由于是相邻两数比较，可以看到第一次循环我们只需要进行3次比较，即：(arary.length - 1) 次。

第二次循环：

1.首先比较array[0]和arary[1]，即15和19；因为15 < 19，因此两个数的位置不变，如下。

2.接着比较array[1]和array[2]，即19和12；因为19 > 12，因此交换两个数的位置，交换完的数组如下。

3.由于array[3]经过第一次循环后，必然大于前面所有的数，因此不再进行比较，则第二次循环结束。

在第二次循环中，由于已经结束的循环次数为1，因此有1个数已经确定位置无需再比较，因此我们比较的次数只有2次，比较次数可以抽象成以下公式：

array.length - 1 - (已经结束的循环次数)

第三次循环：

1.首先比较array[0]和arary[1]，即15和12；因为15 > 12，因此交换两个数的位置，交换完的数组如下。

2.由于array[2]经过第二次循环后，必然大于前面所有的数，因此不再进行比较，则第三次循环结束。

第四次循环：

在经过第三次循环后，array[1]~array[3]均回到属于他们的正确位置，因此此时array[0]必然也在属于它的正确位置，因此无需进行第四次循环。

完整过程

最后我们通过以下动图来看冒泡排序的整个过程，图中浅蓝色的柱子为还未在正确位置的数，绿色的两个柱子为正在比较的数，橘黄色的柱子为已经在正确位置的数。

整合

通过上文例子无需进行第四次循环可以知道，循环的次数为：数组元素的个数 - 1，则循环次数可以表示成如下：

for (int i = 0; i < array.length - 1; i++)

在上文例子的第二次循环中，我们将每次循环的比较次数抽象成以下公式：

array.length - 1 - (已经结束的循环次数)

用具体的例子展示，每次循环需要比较的次数如下：

第一次循环：array.length - 1 - 0
第二次循环：array.length - 1 - 1
第三次循环：array.length - 1 - 2
...

通过上面的两个公式可以观察到，“已经结束的循环次数” 刚好可以使用上面的最外层循环的变量 i 进行代替，即每次循环的比较次数可以用如下公式：

for (int j = 0; j < array.length - i - 1; j++)

结合两个公式的代码，还有上面的比较和交换代码，冒泡排序整理成代码如下：

public static void bubbleSort(int[] array) {
    if (array == null || array.length == 0) {
        return;
    }
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

时间复杂度

在通常情况下。冒泡排序的比较次数 = (n - 1) + (n - 2) + ... + 2 + 1，即：n * (n - 1) / 2，所以冒泡排序的时间复杂度为：O(n^2)。

使用场景

由于冒泡排序的时间复杂度为：O(n^2)。因此，在进行量比较大的排序时，最好不要采用冒泡排序。经过简单的测试，在1000个数字以内的排序，用冒泡排序是可以接受的。1000个随机数使用冒泡排序耗时一般在5毫秒以内，但是当数字个数达到10000个时，耗时会达到100+毫秒，简直是灾难。

最优情况

 对排序算法熟悉的人应该知道，冒泡排序最优情况的时间复杂度是：O(n)，怎么得出来的了？通过上文的代码是无法达到O(n)的，需要对上文的代码进行一点点的优化，优化后的代码如下。

public class BubbleSort {
    public static void bubbleSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        for (int i = 0; i < array.length - 1; i++) {
            // 当次循环是否发生元素交换
            boolean isSwap = false;
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    isSwap = true;
                }
            }
            // 如果当次循环没有发生元素交换, 则数组已经排好序
            if (!isSwap) {
                return;
            }
        }
    }
}

如果array数组本来就是有序的，则第一次循环结束后由于没有元素交换，会直接return，此时的时间复杂度即为：O(n)。