PAT-A1098

#include<stdio.h> #include<algorithm> using namespace std; int n, orign[111]={0}, orign1[111]={0}, result[111]={0}; bool cmp(int a[], int b[]){ for(int i=1;i<=n;i++){ if(a[i]!=b[i])return false; } return true; } void show(int a[]){ for(int i=1;i<=n;i++){ printf("%d",a[i]); if(i<n)printf(" "); } printf("\n"); } bool InsertSort(){ bool flag=false; for(int i=2;i<=n;i++){ if(i!=2 && cmp(orign,result) )flag=true; sort(orign+1,orign+i+1); if(flag)return true; } return false; } void downAdjust(int low, int high){ int i=low,j=i*2; while(j<=high){ if(j+1<=high&&orign1[j]<orign1[j+1])j=j+1; if(orign1[i]<orign1[j]){ swap(orign1[i],orign1[j]); i=j; j=i*2; } else break; } } void HeapSort(){ int i; bool flag=false; for(i=n/2;i>=1;i--){/ downAdjust(i,n);//建堆 } for(i=n;i>=1;i--){ if(i!=n && cmp(orign1,result) ){flag=true;} swap(orign1[i],orign1[1]); downAdjust(1,i-1); if(flag){show(orign1);return ;} } } int main(){ int i; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&orign[i]); orign1[i]=orign[i]; } for(i=1;i<=n;i++){ scanf("%d",&result[i]); } if( InsertSort( ) ){ printf("Insertion Sort\n");show(orign);} else { printf("Heap Sort\n"); HeapSort(); } return 0; }