轻松读懂数据结构系列：早操排队图解冒泡排序

一、说在前面

一直想写一些简单易懂的文章，因为平时看的很多的书籍或者文章都是看着很难受的感觉，当然，这并不是说书籍写的不好，只是说对于一些没有太多基础或者基础不是很好的来说，相对来说还是比较难以理解的。

这个系列主要是写一些简单易懂的数据结构与算法的文章，同时也是帮助自己再理解理解这方面的知识。

作为数据结构与算法的开篇，还是以排序算法作为第一部分的内容，需要注意的是，这一系列的文章并不是涉及到很多理论性质的知识，因为前面说了，主要还是希望文章是简单易懂的，希望能达到读故事的感觉。如果需要去学习理论性质的知识，可以去查看相关的数据结构与算法的书籍。

二、冒泡排序算法

作为这一系列的第一部分，主要讲解排序算法。从小到大，我们至少前20年的时间都是在学校度过了，校园生活在我看来是十分的美好的，以至于现在我都还在校园里面生活。在我们读书的阶段，是不是经常会碰到排队的时候，因为大家都熟悉这一场景，所以，我们就一排队来讲解排序算法。

冒泡算法应该是我们最熟悉不过的算法了，也是我们最熟悉不过的排队了，既然熟悉不过，那么我们今天就来排个冒泡排序的队列吧。

今天早上，老师叫我们去操场上做早操，做早操之前呢，需要排队，排队都有一个排法，不是吗？那么，老师今天就要求我们按照身高由低到高依次排好。

于是，我们早上很快就一起到了操场上，总共有5个人到了操场，刚刚去的时候，队列肯定是散的对吧，这时候的队列是下面这样子的：第0个位置站的小明，第1个位置站的小海，第2个位置站的小刘，第3个位置站的小李，第5个位置站的小爱。

于是老师（假设老师是一个程序员哈，皮一下）要求我们按照冒泡排序的方法排好队：挨个的比较身高，如果比下一个位置上的同学高，就换一下位置。

好了，同学们听到老师的指示之后呢，同学们就开始动身了。

第0个位置上的小明同学和第1个位置上的小海同学相互比了一下身高，发现第1个位置上的小海同学（1.80m）比第0个位置上的小海同学（1.60m）高，于是就保持不动，所以第一次排队后，队列还是保持不变的。

接下来，第1个位置上的小海同学还想和第2个位置上的小刘同学比一下身高，发现第1个位置上的小海同学比第2个位置上的小刘同学高，所以，他们互换一下位置。

于是，队列成了下面的样子，小海和小刘换了一下位置。

之后，第2个位置上的小海同学，又和第3个位置上的小李同学比了一下身高，发现，第2个位置上的小海同学还是比第3个位置上的小李同学高，所以他们还是需要交换一下位置的。

这时候，队列变成了下面的样子，小海和小李互换。

接下来第3个位置上的小海同学和第4个位置上的小爱同学进行了身高的比较，发现第3个位置上的小海同学还是比第4个位置上的小爱同学高，所以又需要换一下。

交换后，变成了这样子：

结果我们发现，通过这种排序方法，最高的小海从第2个位置上跑到了最后一个位置

好了，现在最高的小海的位置已经确定了，我们就不管他了，我们又从第0个位置上的同学开始，第0个位置的小明同学和第1个位置的小刘同学比较身高，发现小明的身高比小刘的矮，所以队列维持不变。

接下来，第1个位置上的小刘和第2个位置上的小李比较，发现，小刘比小李高，所以需要交换位置

交换后，变成了下面的队列

然后，第2个位置上的小刘和相邻的第3个位置上的小爱比较身高，发现小爱比小刘高，所以不交换位置

最后一个位置的小海因为第一轮已经知道他最高了，所以不与他比较了，因此，这轮排完之后，我们发现，整个序列已经是有序的了，我们看一下队列的变化。

从这排队的过程中，我们是不是发现了冒泡排序的思想：

第一遍，第一个位置上的同学开始，挨个的比较身高，如果第0个位置的同学比第1个位置的同学高，就交换位置，否则，不换位置，然后，第1个位置与第2个位置的同学比一下身高，如果第1个位置的同学高比第2个位置的同学高，交换位置，否则不换，以此类推，最高的同学将会到最后一个位置上。

第二遍，还是从第一个位置上的同学开始，第1个同学和第2个同学比较，如果第一个同学比第二个同学高，交换位置，否则不变，然后，第2个位置上的同学和第3个位置的同学比较，如果第2个位置的同学高，则交换位置，否则不换。这一遍，因为第一遍已经找出来最高的同学在最后一个位置，所以最后一个位置不用比较了。

直到队列全部排好为止。

到这里，我想你应该明白了冒泡排序的思想了。

接下来，我们看一下代码的实现（这里我们使用Java代码实现）。

public static void bubbleSort(int[] arr) {
        //如果数组为空，或者元素为1，直接返回。
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int e = 0; e < arr.length - 1; e++) {//每次最大元素就像气泡一样"浮"到数组的最后
            for (int i = 0; i < n-1-e; i++) {//n-1-e:-1是因为元素从0下表开始，-e是因为可以减去已排到最后的几个元素，可以减少比较次数。
                if (arr[i] > arr[i + 1]) {//如果大于下一个位置
                    swap(arr, i, i + 1);//交换位置
                }
            }
        }
    }

    /**
     * 交换元素位置
     * @param arr
     * @param i
     * @param j
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

性能分析

最差时间复杂度：O(n^2)
最优时间复杂度：如果已经是有序的,可以把最优时间复杂度降低到O(n)
平均时间复杂度：O(n^2)
所需辅助空间：O(1)
稳定性：稳定
稳定性说明：排序稳定不稳定，就是看每次排序的过程中，是否会改变整个序列的位置。

文章有不当之处，欢迎指正，如果喜欢微信阅读，你也可以关注我的微信公众号：好好学java，获取优质学习资源。