冒泡排序算法详细剖析

首先我们要知道一个前提知识 ，冒泡排序 属于 交换排序 的一种。

那么什么是交换排序？

答：根据序列中两个关键字的大小的比较结果来决定是否交换这两个记录在序列中的位置。

冒泡排序的思想： 1.当我们拿到一个混乱无序的序列的时候，我们可以从前往后依次两两比较相邻元素的值。这里我们假定想要序列从小到大排列。那么每次对比 a[i-1] 与 a[i]，若a[i-1] > a[i] 。那么我们就交换这两个元素的位置。

原序列：2 5 4 3 1
对比 2 < 5  不做处理
对比 5 > 4 交换，此时序列：2 4 5 3 1
对比 5 > 3 交换，此时序列：2 4 3 5 1
对比 5 > 1 交换，此时序列：2 4 3 1 5
一轮对比结束，最大元素已经排列到最后，即正确位置。

2.经过一轮的对比，我们是不是把序列中最大的元素放到了最后呢？答案是肯定的！我们形象的理解，就是跟鱼儿吐泡泡一样，慢慢浮出水面，泡泡越来越大。

3.那么我们思考是不是多进行几次就可以实现有序了？emmm,你可能会说：最后一个是有序的，那么我们只需要对前n-1个元素进行处理。对！仔细思考其实我们每一轮都会使得一个元素有序，所以每一轮我们要处理的序列长度都会减一。

4.那么我们一共需要进行几轮呢？

还拿上面的这个序列来说明
原序列：2 5 4 3 1
第一轮结束：2 4 3 1 5 要处理序列变为：2 4 3 1
第二轮结束：2 3 1 4   要处理的序列为：2 3 1
第三轮结束: 2 1 3     要处理序列变为：2 1
第四轮结束：1 2       此时所有序列为 1 2 3 4 5 有序

所以我们可以很直观的得出：我们一共需要n-1轮。而这个n-1轮是最坏的情况。大家可以动手试试 1 5 4 3 2 这个序列，他在第三轮的时候就已经完全有序了。

那么算法思路有了，写code也很简单了

void maopao_sort(int a[],int n){//我们传入数组a[]和元素个数n
     for(int i=0;i<n-1;i++){//一共最多进行n-1轮对比
          for(int j=0;j<n-1-i;j++){//每一轮我们需要对比的序列长度减一   
          if(a[j] > a[j+1]) swap(a[j],a[j+1]);//交换
          }
     }
}

因为最多进行n-1轮，所以我们还可以加一个flag来判断当前是否发生交换从而减少循环量。这里不在赘述。

时间复杂度分析: 最坏循环 n-1 轮，每轮需要进行对比 n - i次。进行求和有 ： n(n-1)/2。所以为一种O（n*n）的复杂度。

稳定性分析:因为i > j 且 a[i] = a[j]，不会发生交换，所以为一种稳定的排序算法。