插入排序选择排序算法.doc

《插入排序选择排序算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、选择排序：#includevoidmain(){constintn=5;intk,b,i,j,g=0;inta[6];cout<<"请输入5个整数"<>a[f];for(i=1;i<=(n-1);i++){k=i;for(j=i+1;j<=n;j++){if(a[j]

2、t<<"比较次数="<voidmain(){constintn=5;inti,j,x,g=0;inta[6];cout<<"请输入5个整数"<>a[f];for(i=2;i<=n;i++){x=a[i];j=i-1;while(j>0&&a[j]>x){a[j+1]=a[j];j=j-1;g++;}a[j+

3、1]=x;}cout<<"5个整数非降序输出"<usingnamespacestd;intg=0;inta[]={0,12,7,6,75,92,56,6,79,87};voidMer

4、ge(intlow,intmid,inthigh){intb[sizeof(a)/sizeof(a[0])];for(inti=1;i<10;i++)b[i]=a[i];ints=low,t=mid+1,k=low;while(s<=mid&&t<=high){if(a[s]<=a[t]){b[k]=a[s];s=s+1;g++;}else{b[k]=a[t];t=t+1;g++;}k=k+1;}if(s==mid+1)for(intp=k;p<=high;p++)b[p]=a[t++];elsefor(intp=k;p<=high;p++)b[p]=a[s++];for(i

5、=1;i<10;i++)a[i]=b[i];}intmain(){intt=1,s=1,n=9;while(t

6、,56,6,79,87}比较次数为g=24三者时间复杂度比较：选择排序算法和插入排序算法的复杂度都是是O(n^2)，比较次数是n（n-1）/2,bottomupsort算法比较最大次数为nlogn–n+1,假设对n=128个元素排序，每次比较时间为10^(-6)s则前两种算法比时间为10^(-6)(128.127)/2=0.008s,bottomupsort算法最大比较时间10^(-6)（128X7-128+1）=0.0008s,bottomupsort算法的时间比较短