算法总结-冒泡排序

算法定义

冒泡排序是交换排序的一种，是一种较简单的排序算法。根据百科的定义，它重复地走访要排序的元素列，依次比较两个相邻的元素，如果顺序错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端，就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故命名为“冒泡排序”。

算法原理

冒泡排序算法的原理如下：

1、比较相邻的一对元素，如果第一个元素比第二个元素大，那么交换这对元素。

2、对所有相邻的元素重复做步骤1，从第一对元素到没有确定的最后一对元素，这步做完，确定当前剩下元素的最大元素。

3、对越来越少的剩下元素重复做步骤1和步骤2，直到确定所有当前剩下元素的最大元素。

冒泡排序动图

代码实现

按照上面的思路，初步的代码如下：

public class Main {

    // 冒泡排序(交换排序)，时间复杂度O(n^2)，空间复杂度O(1)
    public static void bubbleSort(int[] arr) {
        // 需要进行排序的趟数刚好为数组arr的长度减1，每一趟排序找出当前的最大数，挪到对应的位置
        for (int i = 0; i < arr.length - 1; ++i) {
            // 每一趟排序时，不断比较当前元素和下一个元素谁大，把大的元素往后挪
            for (int j = 0; j < arr.length - 1 - i; ++j) {
                if (arr[j] > arr[j + 1]) {
                    // 若当前元素大于下一个元素，交换两个元素
                    arr[j] ^= arr[j + 1];
                    arr[j + 1] ^= arr[j];
                    arr[j] ^= arr[j + 1];
                }
            }
        }
    }

}

但是上面代码的时间复杂度固定是O(n ^ 2)，如果数组本来已经有序了，再进行元素交换就是多余了，或者元素交换的趟数走到半路时数组就变得有序了，后面再进行元素交换也是多余的，所以上面的代码是有缺陷的，需要改进。

假设数组的长度为n。

最好情况：数组是有序的，那么不用进行元素交换，在第一层for循环i = 0时，进行一次第二层for循环，第二层for循环结束后，判断出数组是有序的，结束。此过程只走1趟，但没有进行元素交换，而每1趟花费的时间是n的数量级，所以最好情况的时间复杂度是O(n)。

最坏情况：数组是倒序的，那么需要进行n - 1趟的元素交换，而每1趟元素交换花费的时间是n的数量级，所以最坏情况时间复杂度是O(n ^ 2)。

平均情况：平均情况的趟数可以表示为n - 1 - k，k是常数，每1趟元素交换花费的时间同样也是n的数量级，那么平均情况花费的时间为(n - 1 - k) * n，平均时间复杂度 = 总花费的时间 / 所有情况的数量。因为不同情况表现为走的趟数不同，所以所有情况的数量等于n的数量级，总花费的时间 = 平均情况花费的时间 * 所有情况的数量，即(n - 1 - k) * n * n，平均时间复杂度 = 总花费的时间 / 所有情况的数量 = (n - 1 - k) * n * n / n = (n - 1 - k) * n，因为k是常数，所以(n - 1 - k) * n实际为n ^ 2的数量级，所以平均时间复杂度是O(n ^ 2)。

根据上述的分析，改进后的代码如下：

public class Main {

    // 冒泡排序改进(交换排序)，平均时间复杂度O(n^2)，最好时间复杂度O(n)，最坏时间复杂度O(n^2)，空间复杂度O(1)
    public static void bubbleSort2(int[] arr) {
        // 需要进行排序的趟数刚好为数组arr的长度减1，每一趟排序找出当前的最大数，挪到对应的位置
        for (int i = 0; i < arr.length - 1; ++i) {
            // 判断数组是否已经有序
            boolean flag = true;

            // 每一趟排序时，不断比较当前元素和下一个元素谁大，把大的元素往后挪
            for (int j = 0; j < arr.length - 1 - i; ++j) {
                if (arr[j] > arr[j + 1]) {
                    // 若当前元素大于下一个元素，交换两个元素
                    arr[j] ^= arr[j + 1];
                    arr[j + 1] ^= arr[j];
                    arr[j] ^= arr[j + 1];
                    // 出现交换，那么数组还不是有序
                    flag = false;
                }
            }

            if (flag) {
                // 若数组已经有序，结束循环
                break;
            }
        }
    }

}

算法效率

冒泡排序是稳定的排序算法，最好情况是数组有序，不需要交换元素，只走1趟，时间复杂度为O(n)；最坏情况是数组倒序，每趟都要元素交换，走n - 1趟元素交换，时间复杂度为O(n ^ 2)；平均情况，根据上述的计算，时间复杂度为O(n ^ 2)；元素交换时，若采用引入中间变量的方法，那么中间变量占一个空间，上述的代码采用位运算的方法进行元素交换，无需引入中间变量，无论采用哪种方法，空间复杂度为O(1)。

平均时间复杂度：O(n ^ 2)

最好时间复杂度：O(n)

最坏时间复杂度：O(n ^ 2)

空间复杂度：O(1)

参考资料

冒泡排序动图来自：冒泡排序

原文链接

原文链接：算法总结-冒泡排序