冒泡排序

1. 如何分析一个排序算法？

1.1 执行效率

　　从以下3个方面来衡量：

• 最好情况、最坏情况、平均情况时间复杂度；
• 时间复杂度的系数、常数、低阶：排序的数据量比较小时考虑；
• 比较次数和交换（或移动）次数；

1.2 内存消耗

　　通过空间复杂度来衡量。针对排序算法的空间复杂度，引入原地排序的概念，原地排序算法就是指空间复杂度为O(1)的排序算法。

1.3 稳定性

　　如果待排序的序列中存在值等的元素，经过排序之后，相等元素之间原有的先后顺序不变，就说明这个排序算法时稳定的。

2. 冒泡排序

2.1 排序原理

• 每次比较相邻的两个元素，判断元素是否满足排序关系，若不满足则进行交换；
• 一次冒泡至少把一个元素移动到它应该在的位置，重复N次，就可以将元素排序完成；
• 优化：若某次冒泡过程未发生数据交换，则说明元素完全有序，不需要进行排序了；

2.2 性能分析

2.2.1 执行效率

• 最小时间复杂度：数据完全有序时，只需进行一次冒泡操作即可，时间复杂度是O(n)；
• 最大时间复杂度：数据倒序排序时，需要n次冒泡操作，时间复杂度是O(n^2)；
• 平均情况复杂度：时间复杂度是O(n^2)；

2.2.2  空间复杂度

　　每次交换仅需1个临时变量，故空间复杂度为O(1)，是原地排序算法。

2.2.3 算法稳定性

　　如果两个值相等，就不会交换位置，故是稳定排序算法。

2.3 代码实现

    public static int[] bubbleSortWithFlag(int[] a){
        // 如果只有一个元素则直接返回
        int len = a.length;
        if (len < 1)
        {
            return a;
        }
        // 开始冒泡
        for (int i = 0; i < len; i++)
        {
            // 此次循环中是否进行过交换
            boolean flag = false;
            for (int j = 0; j < len-i-1; j++)
            {
                if (a[j] > a[j+1])
                {
                    flag = true;
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
            // 若未进行交换，说明已经排序完成
            if (!flag)
            {
                break;
            }
            System.out.println("第" + i + "次排序为： " + Arrays.toString(a) );
        }
        return a;
    }