# 冒泡排序算法的原理和实现

冒泡排序（Bubble Sort）是排序算法里面比较简单的一个排序。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序不对则进行交换，并一直重复这样的走访操作，直到没有要交换的数据元素为止。

冒泡排序的原理

为了更深入地理解冒泡排序的操作步骤，我们现在看一下冒泡排序的原理。

首先我们肯定有一个数组，里面存放着待排序的元素列表，我们如果需要把比较大的元素排在前面，把小的元素排在后面，那么需要从尾到头开始下面的比较操作：

1. 从尾部开始比较相邻的两个元素，如果尾部的元素比前面的大，就交换两个元素的位置。

2. 往前对每个相邻的元素都做这样的比较、交换操作，这样到数组头部时，第 1 个元素会成为最大的元素。

3. 重新从尾部开始第 1、2 步的操作，除了在这之前头部已经排好的元素。

4. 继续对越来越少的数据进行比较、交换操作，直到没有可比较的数据为止，排序完成。

注意，看完了这里的操作步骤，我们可以想一下，如果从头到尾进行操作是否可以？当然不可以，不过这样可以完成从小到大的排序。

假如我们要把 12、35、99、18、76 这 5 个数从大到小进行排序，那么数越大，越需要把它放在前面。冒泡排序的思想就是在每次遍历一遍未排序的数列之后，将一个数据元素浮上去（也就是排好了一个数据）。

我们从后开始遍历，首先比较 18 和 76，发现 76 比 18 大，就把两个数交换顺序，得到 12、35、99、76、18；接着比较 76 和 99，发现 76 比 99 小，所以不用交换顺序；接着比较 99 和 35，发现 99 比 35 大，交换顺序；接着比较 99 和 12，发现 99 比 12 大，交换顺序。最终第 1 趟排序的结果变成了 99、12、35、76、18，排序的过程如图 1 所示。

图 1 第 1 趟冒泡排序的过程示例

经过第 1 趟排序，我们已经找到了最大的元素，接下来的第 2 趟排序就只对剩下的 4 个元素排序。第 2 趟排序的过程示例如图 2 所示。

图 2 第 2 趟冒泡排序的过程示例

经过第 2 趟排序，结果为 99、76、12、35、18。接下来应该进行第 3 趟排序了，剩下的元素不多，比较次数也在减少。

第3趟排序的结果应该是 99、76、35、12、18，接下来第 4 趟排序的结果是 99、76、35、18、12，经过 4 趟排序之后，只剩一个 12 需要排序了，这时已经没有可比较的元素了，所以排序完成。

这个算法让我想起了小时候在操场排队跑步，老师总是说：“高的站前面，低的站后面”。我们一开始并不一定会站到准确的位置上，接着老师又说：“你比前面的高，和前面的换换，还高，再和前面换换”，就这样找到了自己的位置。

通过这个例子，你是否已经完全掌握了排序算法的精髓呢？

冒泡排序的实现

通过对冒泡排序原理的学习，我们应该能够很容易地写出实现代码了。首先我们需要从后往前遍历待排序数组，然后重复这个步骤，继续遍历剩下的待排序的数列，这样我们就需要一个双重循环去完成这个算法。

public class BubbleSort {
    private int[] array;
   
    public BubbleSort(int[] array) {
        this.array = array;
    }

    /**
     * 从小到大
     */
    public void sort() {
        int length = array.length;
        if (length > 0) {
            for (int i = 1; i < length; i++) {
                for (int j = 0; j < length - i; j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
    }
   
    /**
     * 从大到小
     */
    public void sort2() {
        int length = array.length;
        if (length > 0) {
            for (int i = length - 1; i > 0; i--) {
                for (int j = length - 1; j > length - 1 - i ; j--) {
                    if (array[j] > array[j - 1]) {
                        int temp = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = temp;
                    }
                }
            }
        }
    }
   
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

}

下面是冒泡排序的测试代码。

public class SortTest {
    public static void main(String[] args) {

        testBubbleSort();
    }
   
    /**
     * 冒泡排序
     */
    private static void testBubbleSort() {
        int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1};
        BubbleSort bubbleSort = new BubbleSort(array);
        bubbleSort.sort2();
        bubbleSort.print();
    }
}

冒泡排序的特点及性能

通过冒泡排序的算法思想，我们发现冒泡排序算法在每轮排序中会使一个元素排到一端，也就是最终需要 n-1 轮这样的排序（n 为待排序的数列的长度），而在每轮排序中都需要对相邻的两个元素进行比较，在最坏的情况下，每次比较之后都需要交换位置，所以这里的时间复杂度是 O(n2)。其实冒泡排序在最好的情况下，时间复杂度可以达到 O(n)，这当然是在待排序的数列有序的情况下。在待排序的数列本身就是我们想要的排序结果时，时间复杂度的确是 O(n)，因为只需要一轮排序并且不用交换。但是实际上这种情况很少，所以冒泡排序的平均时间复杂度是 O(n2)。

对于空间复杂度来说，冒泡排序用到的额外的存储空间只有一个，那就是用于交换位置的临时变量，其他所有操作都是在原有待排序列上处理的，所以空间复杂度为 O(1)。

冒泡排序是稳定的，因为在比较过程中，只有后一个元素比前面的元素大时才会对它们交换位置并向上冒出，对于同样大小的元素，是不需要交换位置的，所以对于同样大小的元素来说，相对位置是不会改变的。

冒泡排序算法的时间复杂度其实比较高。从 1956 年开始就有人研究冒泡排序算法，后续也有很多人对这个算法进行改进，但结果都很一般，正如 1974 年的图灵奖获得者所说的：“冒泡排序除了它迷人的名字和引起的某些有趣的理论问题，似乎没有什么值得推荐的。”

冒泡排序的适用场景

对于冒泡排序，我们应该对它的思想进行理解，作为排序算法学习的引导，让我们的思维更加开阔。

虽然冒泡排序在我们的实际工作中并不会用到，其他排序算法多多少少比冒泡排序算法的性能更高，但是我们还是要掌握冒泡排序的思想及实现，并且在面试时还是有可能会用到。