本文将对排序算法中的冒泡排序进行讲解。
1 冒泡排序
今天介绍另外一种排序算法，冒泡排序。它的基本思想是，对相邻的元素进行两两比较，顺序相反则交换，这样，每趟会将最小（或最大）的元素浮到数组最后面，最终达到整体有序。
冒泡排序也是较为直观的一种排序算法，以整体升序为例，我们先看看每一趟具体发生了什么：
image
我们可以看到，每一趟过程中，从左到右，相邻的位置进行比较，如果不符合升序，就将其位置对调。直到最后一个元素为止，此时最后一个元素是数组中最大的元素。冒泡排序每一趟能够把未排序部分中的最大值移动到最后面，这个过程像冒泡一样，因此这个排序也称为冒泡排序。
2 代码解析
image
14行：循环n-1次，因为每一趟能够排好一个元素的位置，总共n个元素，最后一趟自动排好，因此需要n-1趟。
15行：定义一个变量flag，初始化为0。
16-21行：内层循环，代表遍历未排序好的数，比如第0趟，j小于4，最远到达a[3]，会和a[4]比较交换。第1趟，j小于3，最远遍历到a[2]，和a[3]比较交换。每一趟都会减少最右边一个元素，因为它已经排好序了。
17-20行：如果当前位置比下一位置大，说明是降序，应该调整为升序，两个位置的值交换。这里把交换数组两个元素的值封装成了函数。另外，如果出现交换的情况，会让flag变量赋值为1。
22-24行：如果flag变量在这一趟没有交换过，说明已经是排好序的状态，不需要再进行后面的排序了，直接跳出整个循环就好了；
最终每一趟的结果如下：
image
注意到第三趟的时候已经是排序好了，因此flag变量一直为0，代表整体已经升序。这所以这一趟遍历完之后就直接跳出循环了，不会再有第四趟。
3 效率分析
最坏情况下，待排序数组是一个逆序数组，如[10,8,7,6,5]，每次都要把前面的元素冒泡到最后面，时间复杂度为O(n^2)。
