[数据结构与算法]1035 插入与归并 (25 分)

思路：先判断是否是插入排序，否则就是归并排序（题目结果唯一）。
判断是否是插入排序方法：
1.从目标找出后一个元素比前一个元素小的节点（这个节点就是未排序的节点）。
2.从未排序的节点开始与相同下标的原来的数组比较，如果出现元素不一致的现象，就不是插入排序。
插入排序下一趟方法：
1.数组第0个元素开始到第一个未排序节点进行排序（可以用sort函数）.
2.后面的元素原样输出即可。
归并排序一趟方法：
1.先定义一个变量c，用来存每次要排的元素个数，由于第一次归并排序是单个元素与相邻元素排序，所以一次要排的元素为 2个。
2.按每c个元素进行排序。
3.将末尾不足c个的元素进行排序，这样一趟归并排序就好了。（注意，第二趟归并的变量c要乘以2，因为0个元素与第1个元素已经有序，第2个与第3个有序，那么第二趟就是对两个相邻的排好序的数组进行排序，可以直接用sort对[0,4)进行排序，以此类推）。
代码如下：

#include<bits/stdc++.h>

using namespace std;
int source[105],target[105];
int n;
int c=2;//每次进行归并的元素个数
//一趟归并排序
void one_merge(){
    //根据c个元素分为cnt段
    int cnt=n/c;
    int idx=0;
    //为每段进行排序
    for(int i=1;i<=cnt;i++){
        sort(source+idx,source+(c*i));
        idx=c*i;
    }
    //jiang最后不满的几个元素排序
    if(idx<n) sort(source+idx,source+n);
    c*=2;
}
//判断原数组与目标数组是否相等
bool judge_arr(){
    for(int i=0;i<n;i++){
        if(source[i]!=target[i]){
            return false;
        }
    }
    return true;
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>source[i];
    for(int i=0;i<n;i++) cin>>target[i];
    int j=1;
    while(target[j]>=target[j-1])j++;
    int temp=j;//用来记录插入排序到的位置
    for(;j<n;j++){
        if(target[j]!=source[j]){
            break;
        }
    }
    if(j==n){//插入排序
        cout<<"Insertion Sort"<<endl;
        if(temp<n){
            int t=target[temp];
            for(j=temp-1;j>=0;j--){
                if(target[j]>t){
                    target[j+1]=target[j];
                }else break;
            }
            target[j+1]=t;
        }
        for(int i=0;i<n-1;i++)cout<<target[i]<<" ";
        cout<<target[n-1];
    }else{//归并排序
        cout<<"Merge Sort"<<endl;
        while(!judge_arr())
            one_merge();
        one_merge();
        for(int i=0;i<n-1;i++)cout<<source[i]<<" ";
        cout<<source[n-1];
    }
    return 0;
}