关于算法:算法总结冒泡排序

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

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

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)

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

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

关于算法:算法总结冒泡排序

算法定义

算法原理

代码实现

算法效率

参考资料

原文链接