共计 1011 个字符,预计需要花费 3 分钟才能阅读完成。
冒泡排序 是蛮力法 的另一个经典体现。
算法思想:比较列表中相邻的元素,如果是逆序的话,就交换他们的位置。重复多次之后,最大的元素就排到了最后一个位置。第二遍操作将第二个元素排到了倒数第二个位置上,这样一直依次比较下去,直到 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).
正文完
星哥说事-微信公众号
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)