排序算法（八）冒泡排序

  冒泡排序（Bubble-Sort）是一种最基础的交换排序。冒泡排序的原理：从第一个数开始，依次往后比较，相邻的元素两两比较，根据大小来交换元素的位置，如果前面的数比后面的数大就交换，否则不作处理。这就类似烧开水时，壶底的水泡往上冒的过程。

图解过程

以数组：5, 9, 2, 4, 7为例，按从小到大的方式排序，冒泡排序的过程如下：
第一次循环：多次交换后，将9上浮到最顶处。

第一次循环
第二次循环：多次交换后，将7上浮到最顶处。
第二次循环
可以发现每次循环后，再次循环的次数在递减，因为每次循环后，数目最大的数都被排到最上面的位置，因此接下来接没必要再去比较最顶端的数字了。
代码实现

int[] numbers = {5, 9, 2, 4, 7}; 
for (int i = 0; i < numbers.length; i++) {
    for (int j = 0; j < numbers.length - 1 - i; j++) {
        if (numbers[j] > numbers[j+1]) {
            int temp = numbers[j];
            numbers[j] = numbers[j+1];
            numbers[j+1] = temp;
        }
    }
}

在第三次循环的时候，我们可以发现，数组已经成为有序序列了，无需再继续进行比较操作，

第三次循环
因此可以对冒泡排序进行优化。优化思想为：如果该次循环没有发生一次数的交换，就说明数组已经排好序了，那么后面的循环比较就可以停止了。
代码如下

public int[] sort() {
    int[] numbers = {5, 9, 2, 4, 7};
    // 设置标志。为true表示在一次循环中有进行交换操作，false则相反
    boolean isExchange = true;
    for (int i = 0; i < numbers.length; i++) {
        // 如果未交换，则跳出循环
        if (!isExchange) break;
        // 每次循环前将其置为 false
        isExchange = false;
        for (int j = 0; j < numbers.length - 1 - i; j++) {
            if (numbers[j] > numbers[j+1]) {
                // 正在进行交换操作，将其置为true
                isExchange = true;
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
            }
        }
    }
    return numbers;
}

然而我们还可以发现，例如当数组：4, 2, 1, 7, 8, 9，一开始循环时，后面三位数已经排好序了，那么我们在循环的时候也就无需去对他们进行对比，解决方法如下

public int[] sort() {
    int[] numbers = {4, 2, 1, 7, 8, 9};
    // 设置标志。为true表示在一次循环中有进行交换操作，false则相反
    boolean isExchange = true;
    // 记录最后一次循环的位置
    int lastExchange = 0;
    // 循环的界限初始化为 numbers.length - 1
    int sortBorder = numbers.length - 1;
    for (int i = 0; i < numbers.length; i++) {
        // 如果未交换，则跳出循环
        if (!isExchange) break;
        // 每次循环前将其置为 false
        isExchange = false;
        for (int j = 0; j < sortBorder; j++) {
            if (numbers[j] > numbers[j+1]) {
                // 正在进行交换操作，将其置为true
                isExchange = true;
                // 记录位置
                lastExchange = j;
                int temp = numbers[j];
                numbers[j] = numbers[j+1];
                numbers[j+1] = temp;
            }
        }
        // 设置循环界限
        sortBorder = lastExchange;
    }
    return numbers;
}

时间复杂度

• 冒泡排序最好的时间复杂度为O(n)，平均时间复杂度为O(n^2)。
• 冒泡排序为稳定排序算法。