冒泡排序重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

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

关于冒泡排序时间复杂性，大家都知道最坏情况下为O（n^2）为什么最好情况下为O（n），很多人有疑问，下面我们就来分析一下：

首先大家看看下面两种冒泡排序的方法：

方法一：

//冒泡排序  

template <class T>  

void Bubble(T a[],int n)  

{  

    //把数组a[0:n-1]中最大的元素冒泡移到右边  

    for(int i=n-1;i>0;--i)  

        for(int j=0;j<i;++j)  

           if(a[j]>a[j+1])  

              Swap(a[j],a[j+1]);     

}  

方法二：

//及时终止的冒泡排序  

template <class T>  

void BubbleSort(T a[],int n)  

{  

   //及时终止的冒泡排序  

    bool swapped=FALSE;  

    for(int i=n-1;i>0&&!swapped;--i)  

    {    

       swapped=true;  

       for(int j=0;j<i;++j)  

       if(a[j]>a[j+1])  

        {  

            Swap(a[j],a[j+1]);  

            swapped=false;  

         }  

    }  

}  

首先，用模板是一个很好的习惯，这个是毋庸置疑的，面试的时候也是一样！

对于方法一来说，我们可以看出，无论是最好情况（即本身就是按序排列的）还是最坏情况，都会执行两个for循环，直到条件不成立为止，因此两者情况下时间复杂度都是O（n^2）。

而对于方法二来说就不一样了，如果是最好情况（即本身就是按序排列的），那么永远不会执行if条件语句，从而终止符号swapped不会再变为false，因此外层for循环只执行一次，里面for循环完整执行n次，总的时间复杂度就变成了O（n）。

这里空间复杂度（辅助存储）为O（1），因为Swap里面用到了一个局部变量，如下：

template<class T>

void Swap(T& a,T& b)

{

     T temp = a;

     a = b;

     b = temp;

}

如果要求不能使用额外的存储空间怎么办？一个局部变量都不能添加怎么办？那么我们只能用异或运算了，如下：

template<class T>

void Swap(T& a,T& b)

{

    a = a^b;

    b = a^b;

    a = a^b;

}