冒泡排序

一、冒泡排序

 冒泡排序是一种交换排序，它的基本思想是：两两比较相邻的记录，如果反序则交换，直到没有反序为止。冒泡的实现在细节上有多种变化，这里主要学习3种冒泡实现。

 下面是冒泡排序的原理图

冒泡排序的实现代码如下

public class BubbleSort {

    public static int[] bubbleSort(int[] array) {
        int temp;// 用于两元素交换时的临时存储
        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]) {
                    // 交换
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
        bubbleSort(array);
        
        for (int element : array) {
            System.out.print(element + " ");
        }
    }
}

分析效率：

任何情况，都需要进行次比较。所以总的时间复杂度为O(n²)

二、冒泡排序(改进)

当序列已经有序或者部分有序时，使用前面的冒泡算法仍要继续进行比较，虽然没有发生交换，但是大量的比较还是多余了，效率太低下。

改进办法是：可以设置一个标志位来监控是否需要继续进行比较。对于任意一趟外层循环，当内层循环没有发生元素交换，说明此时序列已经有序了，就停止比较。

/**
 * 冒泡排序的改进
 * 
 * 改进后：
 * 最好情况：O(n)
 * 最坏情况：O(n^2)
 * 总的时间复杂度：O(n^2)
 * 
 * 
 * 【a】flag初值为true。
 * 【b】每次进入外层循环后，将flag设为false
 * 【c】对于一趟外层循环，整个内层循环如果没发生交换，说明已经有序，flag的值仍为false，不会变为true。
 * 【d】下次循环时，由于flag为false，不再执行循环
 * 
 * @author lp
 *
 */
public class BubbleSort_Performance {

    public static int[] bubbleSort(int[] array) {
        // 标志
        boolean flag = true;// 【a】
        for (int i = 0; i < array.length - 1 && flag; i++) {//【d】
            flag = false;// 【b】
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    // 如果有数据交换，则flag设为true
                    flag = true;// 【c】
                }
            }
        }
        return array;
    }

    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }

    public static void main(String[] args) {
        int[] array = { 49, 38, 65, 97, 76, 13, 27, 49, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };

        bubbleSort(array);

        for (int element : array) {
            System.out.print(element + " ");
        }
    }
}

分析效率：

最好情况(优化)：初始序列为正序排列，则只需要进行一趟排序，排序过程中进行n-1次比较，且不移动记录。时间复杂度不再是O(n²)了，而是O(n)

最坏情况(不变)：初始序列为逆序序列，则需要进行n-1趟排序，需要进行次比较，并作等数量级的元素移动。时间复杂度为O(n²)

因此，总的时间复杂度为O(n²)

平均时间复杂度：(注意这里的推导思路)

对于包含n个数据的数组，这n个数据就有n!种排列方式。不同的排列方式，冒泡排序执行的时间肯定是不同的。如果用传统的概率论方法定量分析平均时间复杂度，涉及的数学推理和计算就会很复杂。这里还有一种思路，通过“有序度”和“逆序度”这两个概念来进行分析。

有序度：是数组中具有有序关系的元素对的个数。 
逆序度：定义正好跟有序度相反（默认从小到大为有序）。
满有序度=有序度+逆序度。
我们排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了。

假如，要排序的数组的初始状态是4，5，6，3，2，1 ，其中，有序元素对有(4，5) (4，6)(5，6)，所以有序度是3。
n=6，所以排序完成之后终态的满有序度为n*(n-1)/2=15。
冒泡排序包含两个操作原子，比较和交换。每交换一次，有序度就加1。
不管算法怎么改进，交换次数总是确定的，即为逆序度，也就是n*(n-1)/2–初始有序度。
此例中就是15–3=12，要进行12次交换操作。

对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？
最坏情况下，初始状态的有序度是0，所以要进行n*(n-1)/2次交换。
最好情况下，初始状态的有序度是n*(n-1)/2，就不需要进行交换。
【我们可以取个中间值n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。】
换句话说，平均情况下，需要n*(n-1)/4次交换操作，比较操作肯定要比交换操作多，而复杂度的上限是O(n2)，所以平均情况下的时间复杂度就是O(n2)。

【【这个平均时间复杂度推导过程其实并不严格，但是很多时候很实用，毕竟概率论的定量分析太复杂，不太好用】】。等我们讲到快排的时候，我还会再次用这种“不严
格”的方法来分析平均时间复杂度。

参考：《数据结构与算法之美》