排序(4) 冒泡排序

冒泡排序算法多次遍历数组，在每次遍历中连续比较相邻的元素，如果元素没有按照顺序排列，则互换他们的值。 博客中先给出了朴素版本，再给出了优化了每一轮内循环结束点（减少遍历轮次）的needNextPass版本和isSorted版本，还有进一步优化判断边界的sortBorder版本，sortBorder版本为最优化版本。

冒泡排序

原理

冒泡排序算法需要遍历几次数组。在每次遍历中，比较连续相邻的元素。如果某一堆元素是降序，则互换他们的值；否则，保持不变。
由于较小的值像“气泡”一样逐渐浮向顶部，而较大的值沉向底部，由此得名冒泡排序（bubble sort）或下沉排序（sinking sort）。

冒泡排序的名字很形象，实际实现是相邻两节点进行比较，大的向后移一个，经过第一轮两两比较和移动，最大的元素移动到了最后，第二轮次大的位于倒数第二个，依次进行。这是最基本的冒泡排序，还可以进行一些优化。

优化一： 如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个isSorted做标记，默认为true，如果发生交互则置为false，每轮结束时检测isSorted，如果为false则继续，如果为true则返回。

优化二： 某一轮结束位置为j，但是这一轮的最后一次交换发生在lastExchangedIndex的位置，则lastExchangedIndex到j之间是排好序的，下一轮的结束点就不必是j–了，而直接到lastExchangedIndex即可。

算法描述

第一次遍历后，最后一个元素称为数组中的最大数。第二次遍历后，倒数第二个元素成为数组中的第二大数。整个过程持续到所有元素都已排好序。
第k次遍历时，不需要考虑最后k-1个元素，因为它们已经排好序了。

朴素版本伪代码描述：

朴素版本伪代码

for (int k = 1; k < arr.length; k++) {
    for (int i = 0; i < arr.length - k; i++) {
        if (arr[i] > arr[i + 1])
            swap arr[i] with arr[i + 1];
    }
}

注意到如果在某次遍历中没有发生交换，那么就不必进行下一次遍历，因为所有的元素已经排好序了。可以用下面的伪代码描述needNextPass版本：
如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个needNextPass做标记，默认为false，如果发生交互则置为true，每轮结束时检测needNextPass，如果为true则继续，如果为false则返回。

needNextPass版本伪代码

boolean needNextPass = true;
for (int k = 1; k < arr.length && needNextPass; k++) {
    // 数组可能已经排好序，不需要再进入下次循环
    needNextPass = false;
    // 第k次遍历
    for (int i = 0; i < arr.length - k; i++) {
        if (arr[i] > arr[i + 1]) {
            swap arr[i] with arr[i + 1];
            needNextPass = true;
        }
    }
}

冒泡排序朴素版本

代码非常简单，使用双循环来进行排序。外部循环控制所有的回合，内部循环代表每一轮冒泡处理，先进行元素比较，再进行元素交换。这种写法不会拿到offer的。

java实现朴素版本

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int tmp = 0;

        for (int i = 0; i < arr.length; i++) {
            // 内部循环代表每一轮冒泡处理
            for (j = 0; j < arr.length - i - 1; j++) {
                if (arr[j + 1] < arr[j]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

    public  static void main(String[] args) {
        int[] array = new int[] { 5, 8, 6, 3, 9, 2, 1, 7 };
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

很明显可以看出，自从经过第六轮排序，整个数列已然是有序的了。可是我们的排序算法仍然“兢兢业业”地继续执行第七轮、第八轮。
这种情况下，如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。

冒泡排序优化一

第一步优化，可以使用needNextPass版本或者isSorted版本。这两个版本的含义，从两个flag的字面就能理解其作用。本质上是一样的。

needNextPass版本代码

如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，那么就不必进行下一次遍历，因为所有的元素都已排好序，算法结束。

可以使用一个needNextPass做标记，默认为false，如果发生交换则置为true，每轮结束时检测needNextPass，如果为true则继续，如果为false则返回。

needNextPass版本

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        boolean needNextPass = true;

        for (int i = 1; i < arr.length && needNextPass; i++) {
            needNextPass = false;

            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    //  改变标志位
                    needNextPass = true;
                }                
            }
        }
    }

    public static void main(String[] args) {
        int[] list = { 2, 32, 3, 34, 45, 8, 89, 20, 23, -1, -2 };
        bubbleSort(list);
        for (int i : list)
            System.out.print(i + " ");
        System.out.println();
    }
}

isSorted版本代码

这一版代码做了小小的改动，利用布尔变量isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。

如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个isSorted做标记，默认为true，如果发生交换则置为false，每轮结束时检测isSorted，如果为false则继续，如果为true则返回。

isSorted版本

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int tmp = 0;

        for (int i = 0; i < arr.length; i++) {
            boolean isSorted = true;

            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;

                    isSorted = false;
                }
            }

            if (isSorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] list = { 2, 32, 3, 34, 45, 8, 89, 20, 23, -1, -2 };
        bubbleSort(list);
        for (int i : list)
            System.out.print(i + " ");
        System.out.println();
    }
}

sortBorder版本(结合优化一和优化二)

具体分析

为了说明问题，用下面的数列为例（在纸上演示一下）：
{3, 4, 2, 1, 5, 6, 7, 8}
这个数组的特点是前半部分{3, 4, 2, 1}无序，后半部分{5, 6, 7, 8}有序，并且后半部分的元素已经是数列最大值。

按照冒泡排序的思路来排序：

第一轮：

• 元素3和4比较，发现3小于4，所以位置不变；
• 元素4和2比较，发现4大于2，所以4和2交换；
• 元素4和1比较，发现4大于1，所以4和1交换。

此时数列：{3, 2, 1, 4, 5, 6, 7, 8}

但是接下来：

• 元素4和5比较，发现4小于5，所以位置不变；
• 元素5和6比较，发现5小于6，所以位置不变；
• 元素6和7比较，发现6小于7，所以位置不变；
• 元素7和8比较，发现7小于8，所以位置不变。

第一轮结束，数列有序区包含一个元素： 8
{3, 2, 1, 4, 5, 6, 7, 8}

第二轮：

• 元素3和2比较，发现3大于2，所以3和2交换；
• 元素3和1比较，发现3大于1，所以3和1交换。

此时数列：{2, 1, 3, 4, 5, 6, 7, 8}

但是接下来

• 元素3和4比较，发现3小于4，所以位置不变；
• 元素4和5比较，发现4小于5，所以位置不变；
• 元素5和6比较，发现5小于6，所以位置不变；
• 元素6和7比较，发现6小于7，所以位置不变；
• 元素7和8比较，发现7小于8，所以位置不变。

第二轮结束，数列有序区包含一个元素： 7, 8
{2, 1, 3, 4, 5, 6, 7, 8}

由上面两轮分析，发现问题：右面的许多元素已经是有序了，可是每一轮还是白白比较了许多次。这正是冒泡排序当中另一个需要优化的点。

接下来的讨论，在代码实现部分进行。

完全优化版本代码

这个问题的关键点在哪里呢？关键在于对数列有序区的界定。

按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2,……

实际上，数列真正的有序区可能会大于这个长度，比如例子中仅仅第二轮，后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。

如何避免这种情况呢？我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

sortBorder版本（完美版本）

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int tmp = 0;
        //记录最后一次交换的位置
        int lastExchangedIndex = 0;
        //无序数列的边界，每次比较只需要比到这里为止        
        int sortBorder = arr.length - 1;  

        for (int i = 0; i < arr.length; i++) {
            //有序标记，每一轮的初始是true
            boolean isSorted = true;    

            for (int j = 0; j < sortBorder; j++) {
                if (arr[j] > arr[j + 1]) {
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    //有元素交换，所以不是有序，标记变为false
                    isSorted = false;

                    //把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangedIndex = j;
                }
            }
            sortBorder = lastExchangedIndex;

            if (isSorted) {
                break;
            }
        }
    }

    public  static void main(String[] args) {
        int[] array = new int[] { 5, 8, 6, 3, 9, 2, 1, 7 };
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }
}

这一版代码中，sortBorder就是无序数列的边界。每一轮排序过程中，sortBorder之后的元素就完全不需要比较了，肯定是有序的。

算法复杂度和稳定性

其实这样的实现，仍然不是最优，有一种排序算法叫做 鸡尾酒排序，是基于冒泡排序的一种升级。具体见博客鸡尾酒排序。

算法复杂度：
时间复杂度（平均）： O(n^2)
时间复杂度（最坏）： O(n^2)
时间复杂度（最好）： O(n)

空间复杂度： O(1)

冒泡排序把小元素往前调或者把大元素往后调，在相邻的两个元素间比较和交换。
如果两个元素相等且相邻，它们不会进行交换；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换。

所以相同元素的前后顺序并没有改变，冒泡排序是一种 稳定排序算法。

---