根据维基百科的定义： 插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。 归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。 现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？ 输入格式： 输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。 输出格式： 首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。 输入样例 1：
10 3 1 2 8 7 5 9 4 6 0 1 2 3 7 8 5 9 4 6 0
输出样例 1：
Insertion Sort 1 2 3 5 7 8 9 4 6 0
输入样例 2：
10 3 1 2 8 7 5 9 4 0 6 1 3 2 8 5 7 4 9 0 6
输出样例 2：
Merge Sort 1 2 3 8 4 5 7 9 0 6
#include<stdio.h>
#include<stdlib.h>
#define FIND 1
#define UNFIND 0
void InsertionSort(int arr
[], int n
, int value
)
{
int i
, j
;
for (i
= 0; i
< n
; i
++)
{
if (value
< arr
[i
]) break;
}
for (j
= n
; j
> i
; j
--)
{
arr
[j
] = arr
[j
- 1];
}
arr
[i
] = value
;
}
void MergeSort(int arr
[], int n
, int N
)
{
int i
, j
, k
, tmp
;
for (k
= 0; k
< N
/ (2 * n
); k
++)
{
for (i
= 0; i
< 2 * n
; i
++)
{
for (j
= i
+ 1; j
< 2 * n
; j
++)
{
if (arr
[i
+ 2 * k
* n
] > arr
[j
+ 2 * k
* n
])
{
tmp
= arr
[i
+ 2 * k
* n
];
arr
[i
+ 2 * k
* n
] = arr
[j
+ 2 * k
* n
];
arr
[j
+ 2 * k
* n
] = tmp
;
}
}
}
}
for (i
= 0; N
/ (2 * n
) == 0 && i
< N
; i
++)
{
for (j
= i
+ 1; j
< N
; j
++)
{
if (arr
[j
] < arr
[i
])
{
tmp
= arr
[j
];
arr
[j
] = arr
[i
];
arr
[i
] = tmp
;
}
}
}
}
void PrintArr(int arr
[], int n
)
{
int i
;
for (i
= 0; i
< n
; i
++)
{
printf("%d", arr
[i
]);
if (i
!= n
- 1)
{
putchar(' ');
}
}
putchar('\n');
}
int main()
{
int i
, j
, k
, N
, flag
= UNFIND
;
int init
[100], init1
[100], processed
[100];
scanf("%d", &N
);
for (i
= 0; i
< N
; i
++)
{
scanf("%d", &init
[i
]);
init1
[i
] = init
[i
];
}
for (i
= 0; i
< N
; i
++)
{
scanf("%d", &processed
[i
]);
}
for (i
= 1; i
< N
; i
++)
{
if (processed
[i
] < processed
[i
- 1]) break;
}
for (j
= i
; j
< N
; j
++)
{
if (processed
[j
] != init
[j
]) break;
}
if (j
== N
)
{
printf("Insertion Sort\n");
InsertionSort(processed
, i
, processed
[i
]);
PrintArr(processed
, N
);
}
else
{
k
= 1;
printf("Merge Sort\n");
while (flag
== UNFIND
)
{
flag
= FIND
;
for (i
= 0; i
< N
; i
++)
{
if (init
[i
] != processed
[i
])
{
flag
= UNFIND
;
break;
}
}
for (i
= 0; i
< N
; i
= i
+ 2 * k
)
{
MergeSort(init
, k
, N
);
}
k
*= 2;
if (flag
== FIND
)
{
PrintArr(init
, N
);
}
}
}
system("pause");
return 0;
}
