经典排序算法之冒泡排序

冒泡排序（Bubble Sort）是最经典也是最简单的排序算法之一。

原理：比较相邻的两个元素，将值大的元素交换到右边(降序则相反).

步骤：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序过程动态图

先看java代码实现：

运行结果：

过程演示：待排序数组：{5, 4, 7, 1, 6, 2}，升序排序

---------------------------------------

第一次循环：

第一次比较5和4，5>4，交换位置：{4，5，7，1，6，2}

第二次比较5和7，5

第三次比较7和1，7>1，交换位置：{4，5，1，7，6，2}

第四次比较7和6，7>6，交换位置：{4，5，1，6，7，2}

第五次比较7和2，7>2，交换位置：{4，5，1，6，2，7}

第一次循环完成结果：{4，5，1，6，2，7}

----------------------------------------

第二次循环：

第一次比较4和5，4

第二次比较5和1，5>1，交换位置：{4，1，5，6，2，7}

第三次比较5和6，5

第四次比较6和2，6>2，交换位置：{4，1，5，2，6，7}

第五次比较6和7，6

第二次循环完成结果：{4，1，5，2，6，7}

----------------------------------------

第三次循环：

第一次比较4和1，4>1，交换位置：{1，4，5，2，6，7}

第二次比较4和5，4

第三次比较5和2，5>2，交换位置：{1，4，2，5，6，7}

第四次比较5和6，5

第五次比较6和7，6

第三次循环完成结果：{1，4，2，5，6，7}

----------------------------------------

第四次循环：

第一次比较1和4，1

第二次比较4和2，4>2，交换位置：{1，2，4，5，6，7}

第三次比较4和5，4

第四次比较5和6，5

第五次比较6和7，6

第三次循环完成结果：{1，2，4，5，6，7}

----------------------------------------

第五次循环：

第一次比较1和2，1

第二次比较2和4，2

第三次比较4和5，4

第四次比较5和6，5

第五次比较6和7，6

第三次循环完成结果：{1，2，4，5，6，7}

相信看完上面的演示过程，你对冒泡排序过程及原理有了完全的理解，但是细心的朋友应该会发现其实在第四次循环就已经得到了最终的结果，这么来看第五次循环完全是多余的，于是就有冒泡排序的改进版本：

当某一轮循环当中没有交换位置的操作，说明已经排好序了，就没必要再循环了，break退出循环即可。

运行结果仍然一致：

复杂度分析：

时间复杂度：若给定的数组刚好是排好序的数组，采用改进后的冒泡排序算法，只需循环一次就行了，此时是最优时间复杂度：O(n)，若给定的是倒序，此时是最差时间复杂度：O(n2) ，因此综合平均时间复杂度为：O(n2)

空间复杂度：因为每次只需开辟一个temp的空间，因此空间复杂度是：O(1)

好了，冒泡排序就介绍到这里，冒泡排序是最经典以及最容易理解的排序。