1035 插入与归并(25)（25 分）

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Insertion Sort
1 2 3 5 7 8 9 4 6 0

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

Merge Sort
1 2 3 8 4 5 7 9 0 6

ps:放假期后去沈阳实习，这边天气干燥，刚来不习惯，头晕思维不清晰。。。这道题的的恶心之处在于测试用例中有排序算法迭代几次仍然相同的序列，而这道题说得并不明白，什么叫迭代一次？就算迭代过后序列不变就不是迭代了吗？而且以前写归并排序都是用递归写的，提交得时候才发现用递归写的和用非递归写的迭代序列不一样，真麻烦，考场就GG了！！！

重要的事情说3次，大家在刷题过程中如果真的想不出来可以在牛客网搜这道题，牛客网可以看测试用例！！！！

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int s[110];
int zj[110];
 int N;
void swap1(int &a,int &b){
    int temp;
    temp = a;
    a = b;
    b = temp;
}
bool isSame(int a[],int b[],int len)
{
for(int i=0;i<len;i++)
{
if(a[i]!=b[i])
   return false;
}
return true;
}
bool  insertSort(int a[],int len)
{
  int flag=0;
    for (int i = 0; i < len-1; i++)
    {
        int j = i + 1;
        for (int k = i; k >= 0; k--)
        {
            if (a[j] < a[k])
            {
                swap1(a[j], a[k]);
                j = k;
            }
        }
        if(flag==1&&!isSame(a,zj,N)){
        for (int i = 0; i < len; i++)
            {
            printf("%d", a[i]);
            if(i!=len-1)printf(" ");
        }flag=10;return true;
        }
        if(isSame(a,zj,N)&&flag!=1)
        {
        flag=1;printf("Insertion Sort\n");
        }
    }
     return false;
}
bool  mergeSort(int len,int a[])
{
    int flag=0;
    int low,high,mid;
    int size;
    for(size=1;size/2<=len-1;size*=2)
    {
        low=0;
        while(low+size<=len-1)
        {
        mid=low+size-1;
        high=mid+size;
        if(high>len-1)
        high=len-1;
        sort(a+low,a+high+1);
        low=high+1;
        }
        //for (int i = 0; i < len; i++)
        //cout<<a[i]<<" ";cout<<endl;
        if(flag==1&&!isSame(a,zj,N)){
        for (int i = 0; i < len; i++)
            {
            printf("%d", a[i]);
            if(i!=len-1)printf(" ");
        }flag=10;return true;
        }
        if(isSame(a,zj,N)&&flag!=1)
        {
        flag=1;printf("Merge Sort\n");
        }
    }
    return false;
}
int main()
{
    int b[110];
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
    scanf("%d",&s[i]);
    b[i]=s[i];
    }
     for(int i=0;i<N;i++)
    {
    scanf("%d",&zj[i]);
    }
    if(insertSort(s,N))int x=0;
    else
    mergeSort(N,b);
    return 0;
}