09-排序2 Insert or Merge (25 分)

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

1
2
3
4
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
//结尾无空行

Sample Output 1:

1
2
3
Insertion Sort
1 2 3 5 7 8 9 4 6 0
//结尾无空行

Sample Input 2:

1
2
3
4
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
//结尾无空行

Sample Output 2:

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

题目谷歌翻译：

09-排序2 Insert or Merge (25分)

根据维基百科：

插入排序迭代，每次重复消耗一个输入元素，并增长一个排序的输出列表。每次迭代，插入排序从输入数据中删除一个元素，在排序列表中找到它所属的位置，并将其插入到那里。它重复直到没有输入元素剩余。

归并排序的工作原理如下：将未排序的列表分成 N 个子列表，每个子列表包含 1 个元素（1 个元素的列表被视为已排序）。然后重复合并两个相邻的子列表以产生新的排序子列表，直到只剩下 1 个子列表为止。

现在给定整数的初始序列，以及由某种排序方法多次迭代得到的序列，您能说出我们使用的是哪种排序方法吗？

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行给出一个正整数 N (≤100)。然后在下一行，给出 N 个整数作为初始序列。最后一行包含 N 个数字的部分排序序列。假设目标序列总是升序。一行中的所有数字都用空格分隔。

输出规格：

对于每个测试用例，在第一行打印“插入排序”或“合并排序”以指示用于获取部分结果的方法。然后再运行此方法进行一次迭代，并在第二行输出结果序列。保证每个测试用例的答案都是唯一的。一行中的所有数字必须用空格隔开，行尾不能有多余的空格。

样本输入 1：

1
2
3
4
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
//结尾无空行

示例输出 1：

1
2
3
Insertion Sort
1 2 3 5 7 8 9 4 6 0
//结尾无空行

样本输入 2：

1
2
3
4
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
//结尾无空行

示例输出 2：

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<stdio.h>
#include<math.h>
#define MAX 100
int BIAO=0;
int B[MAX];
int BIJIAO(int n,int A[])
{

    for(int i=0;i<n;i++)
        if(A[i]!=B[i])
           return 0;
    return 1;
}
void Sort(int n,int A[],int B[])
{
    int i,j;

    int k;
    int tep;
    int sum=0;
    int flag=0;
    sum=BIJIAO(n,A);
    for(i=1;i<n;i++)
    {
        tep=A[i];
        for(j=i;j>0&&A[j-1]>tep;j--)
            A[j]=A[j-1];
        A[j]=tep;
        if(sum==0)
             sum=BIJIAO(n, A);
        if(sum==1)
         {
            if(flag)
               break;
            flag=1;
         }


    }
    if(sum!=1&&i==n)
        sum=BIJIAO(n,A);

    if(sum==1)
    {
        BIAO=1;

        printf("Insertion Sort\n");
        for(i=0;i<n;i++)
        {
            if(i!=0)
                printf(" ");
            printf("%d",A[i]);
        }
    }

}
void  Merge(int A[],int Tepa[],int L,int R,int RE)
{
    int LE,NE,tep;
    int i;
    LE=R-1;
    tep=L;
    NE=RE-L+1;
    while(L<=LE&&R<=RE)
        if(A[L]<=A[R])
           Tepa[tep++]=A[L++];
        else
            Tepa[tep++]=A[R++];
    while(L<=LE)
        Tepa[tep++]=A[L++];
    while(R<=RE)
         Tepa[tep++]=A[R++];
    for(i=0;i<NE;i++,RE--)
        A[RE]=Tepa[RE];
}
void Merge_pass( int A[], int TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j;

     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}

void Merge_Sort( int A[], int N )
{
     int length;
     int *TmpA;
     int flag=0;
      int sum=0;
     length = 1; /* 初始化子序列长度*/
     TmpA = malloc( N * sizeof( int ) );
     sum=BIJIAO(N,A);
     if ( TmpA != NULL ) {
          while( length < N ) {
              Merge_pass( A, TmpA, N, length );
              if(sum==0)
                  sum=BIJIAO(N,A);
              length *= 2;
              if(sum==1)
              {
                  if(flag)
                    break;
                  flag=1;
              }
              Merge_pass( TmpA, A, N, length );
              length *= 2;
              if(sum==0)
                   sum=BIJIAO(N,TmpA);
              if(sum==1)
              {
                  if(flag)
                    break;
                  flag=1;
              }
          }
          free( TmpA );
     }
     else printf( "空间不足" );
     if(sum==1)
     {
         
       printf("Merge Sort\n");
      for(int i=0;i<N;i++)
      {
         if(i!=0)
            printf(" ");
        printf("%d",A[i]);
      }
      
     }
}
int main()
{
    int i,j;
    int A[MAX],C[MAX];
    scanf("%d",&j);
    for(i=0;i<j;i++)
    {
        scanf("%d",&A[i]);
        C[i]=A[i];
    }
    for(i=0;i<j;i++)
        scanf("%d",&B[i]);

    Sort(j,A,B);
    if(BIAO==0)
       Merge_Sort(C,j);

    return 0;
}
/*6
1 3 2 6 5 4
1 2 3 5 6 4*/