PAT A1089

PAT A1089

考察插入排序和归并排序
插入排序完整执行 每一步都与中间序列对比，判断是哪种排序方式。

#include
#include
#include
#include
#include
using namespace std;//返回插入排序的下一步 
int n;
int isinsert(vector<int> &a,vector<int> &b){for(int i=1;i<a.size();i++){int temp=a[i],j;for(j=i-1;j>=0;j--){if(temp<a[j]){a[j+1]=a[j];}else{break;}}a[j+1]=temp;if(a==b){return i+1;}}return -1;
}void guibing(vector<int> &a,vector<int> &b){for(int i=2;i/2<=a.size();i*=2){if(a==b) {for(int j=0;j<a.size();j+=i){sort(&a[0]+j,&a[0]+min(i+j,n));}break;		}for(int j=0;j<n;j+=i){sort(&a[0]+j,&a[0]+min(i+j,n));}}printf("Merge Sort\n");for(int i=0;i<a.size();i++){printf("%d",a[i]);if(i!=n-1) printf(" ");}
}int main(){vector<int> start,mid,start1;int a;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&a);start.push_back(a);start1.push_back(a); }for(int i=0;i<n;i++){scanf("%d",&a);mid.push_back(a); }int m=isinsert(start,mid);if(m>-1){int temp=start[m],j;for(j=m-1;j>=0;j--){if(temp<start[j]){start[j+1]=start[j];}else{break;}}start[j+1]=temp;printf("Insertion Sort\n");for(int i=0;i<start.size();i++){printf("%d",start[i]);if(i!=n-1) printf(" ");}}else{guibing(start1,mid);}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！