小海聊数据结构系列之早操排队图解冒泡排序
小海聊数据结构系列之早操排队图解冒泡排序
一、说在前面
一直想写一些简单易懂的文章，因为平时看的很多的书籍或者文章都是看着很难受的感觉，当然，这并不是说书籍写的不好，只是说对于一些没有太多基础或者基础不是很好的来说，相对来说还是比较难以理解的。
这个系列主要是写一些简单易懂的数据结构与算法的文章，同时也是帮助自己再理解理解这方面的知识。
作为数据结构与算法的开篇，还是以排序算法作为第一部分的内容，需要注意的是，这一系列的文章并不是涉及到很多理论性质的知识，因为前面说了，主要还是希望文章是简单易懂的，希望能达到读故事的感觉。如果需要去学习理论性质的知识，可以去查看相关的数据结构与算法的书籍。
二、冒泡排序算法
作为这一系列的第一部分，主要讲解排序算法。从小到大，我们至少前20年的时间都是在学校度过了，校园生活在我看来是十分的美好的，以至于现在我都还在校园里面生活。在我们读书的阶段，是不是经常会碰到排队的时候，因为大家都熟悉这一场景，所以，我们就一排队来讲解排序算法。
冒泡算法应该是我们最熟悉不过的算法了，也是我们最熟悉不过的排队了，既然熟悉不过，那么我们今天就来排个冒泡排序的队列吧。
今天早上，老师叫我们去操场上做早操，做早操之前呢，需要排队，排队都有一个排法，不是吗？那么，老师今天就要求我们按照身高由低到高依次排好。
于是，我们早上很快就一起到了操场上，总共有5个人到了操场，刚刚去的时候，队列肯定是散的对吧，这时候的队列是下面这样子的：第0个位置站的小明，第1个位置站的小海，第2个位置站的小刘，第3个位置站的小李，第5个位置站的小爱。
图片.png
于是老师（假设老师是一个程序员哈，皮一下）要求我们按照冒泡排序的方法排好队：挨个的比较身高，如果比下一个位置上的同学高，就换一下位置。
好了，同学们听到老师的指示之后呢，同学们就开始动身了。
第0个位置上的小明同学和第1个位置上的小海同学相互比了一下身高，发现第1个位置上的小海同学（1.80m）比第0个位置上的小海同学（1.60m）高，于是就保持不动，所以第一次排队后，队列还是保持不变的。
接下来，第1个位置上的小海同学还想和第2个位置上的小刘同学比一下身高，发现第1个位置上的小海同学比第2个位置上的小刘同学高，所以，他们互换一下位置。
互换位置
于是，队列成了下面的样子，小海和小刘换了一下位置。
小海和小刘交换后
之后，第2个位置上的小海同学，又和第3个位置上的小李同学比了一下身高，发现，第2个位置上的小海同学还是比第3个位置上的小李同学高，所以他们还是需要交换一下位置的。
小海和小李互换
这时候，队列变成了下面的样子，小海和小李互换。
小海和小李互换
接下来第3个位置上的小海同学和第4个位置上的小爱同学进行了身高的比较，发现第3个位置上的小海同学还是比第4个位置上的小爱同学高，所以又需要换一下。
图片.png
交换后，变成了这样子：
图片.png
结果我们发现，通过这种排序方法，最高的小海从第2个位置上跑到了最后一个位置
好了，现在最高的小海的位置已经确定了，我们就不管他了，我们又从第0个位置上的同学开始，第0个位置的小明同学和第1个位置的小刘同学比较身高，发现小明的身高比小刘的矮，所以队列维持不变。
接下来，第1个位置上的小刘和第2个位置上的小李比较，发现，小刘比小李高，所以需要交换位置
交换后，变成了下面的队列
然后，第2个位置上的小刘和相邻的第3个位置上的小爱比较身高，发现小爱比小刘高，所以不交换位置
最后一个位置的小海因为第一轮已经知道他最高了，所以不与他比较了，因此，这轮排完之后，我们发现，整个序列已经是有序的了，我们看一下队列的变化。
图片.png
图片.png
从这排队的过程中，我们是不是发现了冒泡排序的思想：
第一遍，第一个位置上的同学开始，挨个的比较身高，如果第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) 稳定性：稳定 稳定性说明：排序稳定不稳定，就是看每次排序的过程中，是否会改变整个序列的位置。
最后，不知道大家对这样的文章理解数据结构与算法的知识是否有帮助，如果有什么建议，欢迎大家留言给出你的建议，写这样一篇文章花了2个小时，希望能够对大家更好的理解数据结构有些帮助！