优化冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

冒泡排序算法的原理如下：

假设给定的数组为：[1, 4, 3, 5, 2]，按照冒泡排序的原理第一次循环的比较过程如下： 图中红色为比较后不交换，绿色为比较后交换，这样第1次循环比较后的结果为：[1, 3, 4, 2, 5, 6] 同理第2次循环比较后的结果为：[1, 3, 2, 4, 5, 6] 第3次循环比较后的结果为：[1, 2, 3, 4, 5, 6] 这样就完成了冒泡排序的整个过程 代码实现如下：

运行结果：

最终的排序结果没问题，但是运行过程我们发现一个问题，第三次循环就已经将数组排序完成了，但还是继续进行了第四次和第五次循环，这样不好，既浪费系统资源而且会使整个算法的执行效率下降，我们来优化一下这个算法：

执行结果：

我们发现，执行过程少了一次循环，虽然看起来还是多了一次循环，但是这种方式最多只会多一次循环，优化的方式也很简单，我们通过判断本次循环是否发生过交换来确定是否继续下一次循环，排序结束后，不会发生交换动作，也就不会再有下一次循环。

如果需要排序的数组原来就是顺序的，那么只需要一次循环即可完成排序，这时，所需的元素比较次数 C C C和元素移动次数 M M M均达到最小值： C m i n = n − 1 C{min} = n - 1 Cmin=n−1， M m i n = 0 M{min} = 0 Mmin=0 所以，冒泡排序最好的时间复杂度为 O ( n ) O(n) O(n)。

如果需要排序的数组是反序的，需要进行 n − 1 n - 1 n−1次循环排序。每次循环排序要进行 n − i n - i n−i次元素的比较 ( 1 ≤ i ≤ n − 1 ) (1 ≤ i ≤ n-1) (1≤i≤n−1)，且每次比较都必须移动元素三次（交换操作三步）来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值： C m a x = n ( n − 1 ) 2 = O ( n 2 ) C{max} = \frac{n(n-1)}{2} = O(n^2) Cmax=2n(n−1)​=O(n2) M m a x = n ( n − 1 ) 4 = O ( n 2 ) M{max} = \frac{n(n-1)}{4} = O(n^2) Mmax=4n(n−1)​=O(n2) 冒泡排序的最坏时间复杂度为 O ( n 2 ) O(n^2) O(n2)。 综上，因此冒泡排序总的平均时间复杂度为 O ( n 2 ) O(n^2) O(n2)。

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。