一起学习,一起进步!
分类: LINUX
2017-12-05 21:56:59
冒泡排序是蛮力法的另一个经典体现。
算法思想:比较列表中相邻的元素,如果是逆序的话,就交换他们的位置。重复多次之后,最大的元素就排到了最后一个位置。第二遍操作将第二个元素排到了倒数第二个位置上,这样一直依次比较下去,直到 n-1 遍之后,就排好了整个列表。
#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;i Arr[j+1])//如果逆序,就交换 { temp=Arr[j]; Arr[j]=Arr[j+1]; Arr[j+1]=temp; } } } for(i=0;i 算法分析:输入的规模完全由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;i Arr[j+1])//如果逆序,就交换 { temp=Arr[j]; Arr[j]=Arr[j+1]; Arr[j+1]=temp; change=true; } } if(!change)//没有发生交换,则不用继续比较了。 { break; } } for(i=0;i 但是在最差情况下,时间复杂度还是Θ(n2).