话说小猿昨天在校友群里，听到有人被问到冒泡排序，然后就没有然后了....其实，冒泡算法还是很基础的，第一次出现是在大二上半学期的课本上。索性咱们今天就说说冒泡排序是啥东西，编码应该怎么实现？

冒泡排序

冒泡排序英文名叫Bubble Sort ，是一种常见的排序算法。执行过程是，每次选取两个元素，马上比较他们的大小，然后按照一定规则（例如：升序），把他们的位置进行交换，把小的元素慢慢"浮"到数列的顶端。咱们可以把它想成一壶快要烧开的水，水泡在壶底，慢慢升到水面上。

这种排序方法优点就是简单，稳定，易掌握，缺点就是过程太重复，效率不高。下面举个栗子，说明下：

我们要对{3,6,4,2,11,10,5} 这个数组进行升序排列，该怎么办呢？

3和6先比较，然后6和4比较，之后是4和2比较.....

咱们可以算下比较的次数，外侧循环要6次，而内部循环，哇，真的很多，要比较39次。

如果写成java代码，那就是：

执行这个main函数，可以得到：

这里我们可以看到，执行函数用了1毫秒的时间。

我们对这个算法进行时间复杂度计算，这个公式太复杂，写不出来，我只能用下百度的图片了。

1）若数组的初始状态是正确排序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值。

时间复杂度为 O（n）

2）若数组的初始状态是反排序的，需要进行 n-1趟排序。每趟排序要进行n-i次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

冒泡排序的最坏时间复杂度为 O（n2）（这里是n的平方）

冒泡排序总的平均时间复杂度也为 O（n2）（这里是n的平方）

到这里咱们冒泡排序法的简单讲解也就说完了。

等一下，假如有人对这么多次循环比较不满意，让你提出优化的解决办法时，那该怎么办呢？（可见城市套路深，我要回农村啊）

如果说刚才的回答是一般普通版本的话，那么下面还能说出优化的，岂不是高调版了....不解释，直接上代码

这版优化程序只用了0毫秒，因为巧妙利用change作标记。如果在本轮比较中，元素交换位置，则说明数列无序；如果没发生元素交换，说明数列已然有序，直接跳出大循环，也就是说数组越接近咱们要的顺序，用这种方法就越快。

其实还有别的优化方法啦，不过如果你能记牢这一个，就够用了。其他的办法等你们评论给写给我吧。（注：部分图是来源于网络）

真是时间过得飞快，马上到新年了，小猿祝各位看官：新年快乐，事业顺利，工资翻倍！猪年棒棒哒~~~

“千里之行，始于足下”小猿要继续前行，并且把自己看到的，好的东西分享出来，你们的阅读和关注才是小猿写文章的不懈动力，后面打算写一些有关于编程主流框架和项目管理方案的随笔，也会同步到我的博客园，请期待，记得关注小猿哦~~~