数据结构与算法-排序（一）冒泡排序

摘要

冒泡排序相对来说，多少都有些了解，就是多循环几轮，每一轮找出最大值放在尾部，直到数组中的元素有序为止。

在这基础上，探讨一下有没有高阶的方法，比如1.提前结束循环，或者2.循环中提前终止，进行下一个循环。这个是要探讨的重点

算法这部分用的编辑语言是 JAVA，编译工具是 Eclipse，JAVA 与 Swift 有些不同，逻辑是相通的，咱的核心就是看逻辑，尽量不要把自己局限在某一种代码语言中。

逻辑

将序列中的元素按照一定的比较规则每每相邻的元素比较并交换。直到序列完全有序为止。

流程

这里是将一个序列处理成从小到大的有序序列：

1. 从头开始比较每一对相邻元素，如果第一个比第二个大，就交换它们的位置。最后一个元素就是最大的元素。
2. 忽略上一步中找到的最大元素，继续 1 中的操作，直到全部元素有序为止。

实现

循环从尾部开始循环，进行相邻元素比较和交换。让每一轮获得的最大元素放到尾部，下次循环避开最大元素坐标

    for (int end = array.length-1; end > 0; end--) {
        for (int begin = 1; begin <= end; begin++) {
            if (cmp(begin, begin-1) < 0) {
                swap(begin, begin-1);
            }
        }
    }

技巧

Q：为什么大循环从尾部开始？

A：示例中是将每一轮大的值放在尾部，为了下次循环避开尾部，所以从尾部开始。

Q：可以更加高效吗？

A：可以从两个方面来提高它的效率

• 某一次循环中已经完全有序，则可以终止。
• 序列尾部已经达到局部有序，那么就可以不再遍历这部分

这两种可以通过设置标示实现。具体可以看进阶部分

进阶（含两个）

如果序列已经完全有序，可以提前终止循环。

在每一次循环中设置 isSorted（已经有序） 标示，如果在遍历中发生了交换，就设置为 false，在遍历结束后判断这个标示，如果是 true 就证明整个序列已经有序，退出循环。

    for (int end = array.length - 1; end > 0; end--) {
        boolean isSorted = true;
        for (int begin = 1; begin <= end; begin++) {
            if (cmp(begin, begin-1) < 0) {
                swap(begin, begin-1);
                isSorted = false;
            }
        }
        if (isSorted) break;
    }

如果序列尾部已经局部有序，可以记录最后一次交换的位置，减少交换的次数

sortedIndex 是在遍历完成后，记录了最后发生交换的位置，从这个位置到序列的尾部，没有发生交换，即这部分的元素是有序的，下次遍历就不用再遍历这部分了。

    for (int end = array.length - 1; end > 0; end--) {
        // sortedIndex 的初始值在数组完全有序的时候有用
        int sortedIndex = 1; // sortedIndex 的值可以是其他值，-1 或者其他。目的是达到有序的时候就不需要再进行下面的代码
        for (int begin = 1; begin <= end; begin++) {
            if (cmp(begin, begin-1) < 0) {
                swap(begin, begin-1);
                sortedIndex = begin;
            }
        }
        end = sortedIndex;
    }

时间和空间复杂度

• 最好、平均时间复杂度：O(n^2)
• 最坏时间复杂度：O(n)
• 空间复杂度：O(1)