冒泡排序

基本思想

      冒泡排序是一种 交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

冒泡排序初级版

      严格意义上来说这版不是标准的冒泡排序算法，因为他不满足“两两比较 相邻 记录”的冒泡排序思想，它更应该是最简单的交换排序而已。
      它的思路是：让每一个关键字都和后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值。

    void bubbleSort(int[] array) {
        int length = array.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                if (array[i] > array[j]) {
                    swap(array, i, j);
                }
            }
        }
    }

      假设待排序的关键字序列为{9,1,5,8,3,7,4,6,2}，当i=0时，9与1交换后在第一位置的1与后面的关键字比较都小，因此它为最小值；当i=1时，第二位置先由9交换成5，再由5交换成3，由3换成2，完成了第二小的数字交换。后面的数字变换类似。

缺点：观察上图可以看出，在排序好1和2的位置后对其余的关键字排序没有什么帮助，所以这个算法的效率是非常低的。

正宗的冒泡排序

    void bubbleSort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            // 注意是j从后往前循环
            for (int j = length - 1; j >= i; j--) {
                if (array[j-1] > array[j]) {
                    swap(array, j - 1, j);
                }
            }
        }
    }

      假设待排序的关键字序列为{9,1,5,8,3,7,4,6,2}，当i=1时，变量j由8反向循环到1，逐个比较，将较小值交换到前面，直到最后找到最小值放置在了第一个位置。如图所示，当i=1、j=8时，发现6大于2-交换他们的位置，j=7时，4大于2-交换位置······直到j=2时由于1小于2所以不交换；j=1时9大于1进行交换，最终得到最小值1放置在第一个位置上。
      整个循环过程中不止将最小值放置在了第一位，还将较小值提到了前面，相较于之前的算法，这一版明显要有进步。

图中较小的数字如同气泡般慢慢浮到上面，因此命名为冒泡算法。

冒泡排序的优化

      如果待排序的字段已经是一个局部有序的序列，那么很多循环操作都是多余的。比如当待排序序列是{2,1,3,4,5,6,7,8,9}时，当i=1时交换了2和1，但是程序仍然不依不饶的将i=2到8以及每个循环中的j循环都执行了一遍，尽管没有交换数据，但是大量的比较操作还是多余了。

    void bubbleSort(int[] array) {
        int length = array.length;
        // flag用来作为标记--可以避免已经有序情况下的无意义的循环
        boolean flag = true;
        for (int i = 1; i < length && flag; i++) {
            flag = false;
            for (int j = length - 1; j >= i; j--) {
                if (array[j - 1] > array[j]) {
                    swap(array, j - 1, j);
                    flag = true;
                }
            }
        }
    }

冒泡排序的时间复杂度分析

      最好情况下，排序表本身是有序的，根据优化后的代码需要比较（n-1）次，没有数据交换，时间复杂度O(n)
      最坏情况下，排序表本身是逆序的，需要比较1+2+3+······+(n-1)次，就是n(n-1)/2次比较，并作等数量级的记录移动，时间复杂度为O(n^2)