PAT排序题

一时失言乱红尘 2022-12-03 13:24 203阅读 0赞

# 插入排序 #

bool isOutput=false;
        for(int i=1;i<n;i++) { 
            sort(backup.begin(),backup.begin()+i+1); //左闭右开区间
            if(isOutput){ 
                bool flag=false;
                for(int x:backup){ 
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<x;
                }
                return 0;
            }
            if(backup==now){ 
                puts("Insertion Sort");
                isOutput=true;
            }
        }

# 归并排序 #

bool isOutput=false;
        for(int i=2;i/2<=n;i*=2) { 
            for(int j=0;j<n;j+=i){ 
                sort(ori.begin()+j,ori.begin()+j+i);
            }
            if(isOutput){ 
                bool flag=false;
                for(int x:ori){ 
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<x;
                }
                return 0;
            }
            if(ori==now){ 
                puts("Merge Sort");
                isOutput=true;
            }
        }

# 堆排序 #

make_heap(t.begin(),t.end());
        for(int i=0;i<n;++i){ 
            pop_heap(t.begin(),t.end()-i);
            if(isOutput){ 
                bool flag=false;
                for(int x:t){ 
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<x;
                }
                return 0;
            }
            if(t==now){ 
                puts("Heap Sort");
                isOutput=true;
            }
        }

# 1098 Insertion or Heap Sort #

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int n,l,h;
    vector<int>ori,now,backup;
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        cin>>n;
        for(int t,i=0;i<n;++i){ 
            cin>>t;
            ori.push_back(t);
        }
        for(int t,i=0;i<n;++i){ 
            cin>>t;
            now.push_back(t);
        }
    
        backup=ori;
        bool isOutput=false;
        for(int i=1;i<n;i++) { 
            sort(backup.begin(),backup.begin()+i+1); //左闭右开区间
            if(isOutput){ 
                bool flag=false;
                for(int x:backup){ 
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<x;
                }
                return 0;
            }
            if(backup==now){ 
                puts("Insertion Sort");
                isOutput=true;
            }
        }
        vector<int>t;
        t=ori;
        make_heap(t.begin(),t.end());
        for(int i=0;i<n;++i){ 
            pop_heap(t.begin(),t.end()-i);
            if(isOutput){ 
                bool flag=false;
                for(int x:t){ 
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<x;
                }
                return 0;
            }
            if(t==now){ 
                puts("Heap Sort");
                isOutput=true;
            }
        }
        return 0;
    }

# 1089 Insert or Merge #

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int n,l,h;
    vector<int>ori,now,backup;
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        cin>>n;
        for(int t,i=0;i<n;++i){ 
            cin>>t;
            ori.push_back(t);
        }
        for(int t,i=0;i<n;++i){ 
            cin>>t;
            now.push_back(t);
        }
        
        /*int idx; for(idx=0;idx<n-1&&now[idx]<=now[idx+1];++idx){ } idx++; int insert=idx; for(;idx<n&&now[idx]==ori[idx];++idx){ } if(idx==n){ cout<<"Insertion Sort"<<endl; idx=insert; while (idx>0){ if(now[idx]<now[idx-1]){ swap(now[idx],now[idx-1]); } --idx; } for(int i=0;i<n;++i){ if(i!=0)cout<<" "; cout<<now[i]; } return 0; }*/
        
        
        backup=ori;
        bool isOutput=false;
        for(int i=2;i/2<=n;i*=2) { 
            for(int j=0;j<n;j+=i){ 
                sort(ori.begin()+j,ori.begin()+min(j+i,n));
            }
            if(isOutput){ 
                bool flag=false;
                for(int x:ori){ 
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<x;
                }
                return 0;
            }
            if(ori==now){ 
                puts("Merge Sort");
                isOutput=true;
            }
        }
        for(int i=1;i<n;i++) { 
            sort(backup.begin(),backup.begin()+i+1); //左闭右开区间
            if(isOutput){ 
                bool flag=false;
                for(int x:backup){ 
                    if(flag)cout<<' ';
                    else flag=true;
                    cout<<x;
                }
                return 0;
            }
            if(backup==now){ 
                puts("Insertion Sort");
                isOutput=true;
            }
        }
        return 0;
    }