良许Linux教程网 干货合集 使用蛮力法求解冒泡排序

使用蛮力法求解冒泡排序

蛮力法是一种简单直接的解决问题的方法,常常直接基于问题的描述和所涉及的定义。由于蛮力法是基于问题的定义来思考的,那么可以说它是一种几乎什么问题都能解决的一般性的方法。

image-20211225124809232

算法思想:

比较列表中相邻的元素,如果是逆序的话,就交换他们的位置。重复多次之后,最大的元素就排到了最后一个位置。第二遍操作将第二个元素排到了倒数第二个位置上,这样一直依次比较下去,直到 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>Arr[i];

   for(i=0;ifor(j=0;jif(Arr[j]>Arr[j+1])//如果逆序,就交换
           {
               temp=Arr[j];
               Arr[j]=Arr[j+1];
               Arr[j+1]=temp;
           }
       }
   }

   for(i=0;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>Arr[i];

   for(i=0;ifalse;
       for(j=0;jif(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" ";
   return 0;
}

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

以上就是良许教程网为各位朋友分享的Linu系统相关内容。想要了解更多Linux相关知识记得关注公众号“良许Linux”,或扫描下方二维码进行关注,更多干货等着你 !

img
本文由 良许Linux教程网 发布,可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。
良许

作者: 良许

良许,世界500强企业Linux开发工程师,公众号【良许Linux】的作者,全网拥有超30W粉丝。个人标签:创业者,CSDN学院讲师,副业达人,流量玩家,摄影爱好者。
上一篇
下一篇

发表评论

邮箱地址不会被公开。 必填项已用*标注

联系我们

联系我们

公众号:良许Linux

在线咨询: QQ交谈

邮箱: yychuyu@163.com

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部