首页 > 代码库 > 冒泡排序时间复杂性的分析

冒泡排序时间复杂性的分析

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

冒泡排序算法的运作如下:(从后往前)
1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
3、针对所有的元素重复以上的步骤,除了最后一个。
4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。[

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

关于冒泡排序时间复杂性,大家都知道最坏情况下为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;

}