用蛮力法解决冒泡排序

秒速五厘米 2022-06-04 05:44 189阅读 0赞

**冒泡排序**是**蛮力法**的另一个经典体现。

**算法思想：**比较列表中相邻的元素，如果是逆序的话，就交换他们的位置。重复多次之后，最大的元素就排到了最后一个位置。第二遍操作将第二个元素排到了倒数第二个位置上，这样一直依次比较下去，直到  n-1  遍之后，就排好了整个列表。

**下面是我的代码实现：C++**

#include 
    using namespace std;
    int main()
    {
        int i,j,temp,N;
        cin>>N;
        int *Arr=new int[N];
        for(i=0;i<N;i++) cin>>Arr[i];
     
        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)//依次比较 { if(Arr[j]>Arr[j+1])//如果逆序，就交换
                {
                    temp=Arr[j];
                    Arr[j]=Arr[j+1];
                    Arr[j+1]=temp;
                }
            }
        }
     
        for(i=0;i<N;i++)//输出
            cout<<Arr[i]<<" ";
        return 0;
    }

算法分析：输入的规模完全由N决定，基本操作是比较：Arr\[j\]>Arr\[j+1\]，时间复杂度C(n)=Θ(n2).

但是键的交换次数是取决于特定的输入，最差的情况是与我们要求的排序相反的，这时候键的交换次数=键的比较次数=Θ(n2).

但是在有的输入情况下，如果在对列表比较一遍之后，没有交换元素的位置，那么这个列表已经有序了，我们就可以停止该算法了。具体改进版本如下：

#include 
    using namespace std;
    int main()
    {
        int i,j,temp,N;
        bool change=false;
        cin>>N;
        int *Arr=new int[N];
        for(i=0;i<N;i++) cin>>Arr[i];
     
        for(i=0;i<N;i++)
        {
            change=false;
            for(j=0;j<N;j++)//依次比较 { if(Arr[j]>Arr[j+1])//如果逆序，就交换
                {
                    temp=Arr[j];
                    Arr[j]=Arr[j+1];
                    Arr[j+1]=temp;
                    change=true;
                }
            }
            if(!change)//没有发生交换，则不用继续比较了。
            {
                break;
            }
        }
     
        for(i=0;i<N;i++)//输出
            cout<<Arr[i]<<" ";
        return 0;
    }

但是在最差情况下，时间复杂度还是Θ(n2).