PAT Basic 1035. 插入与归并
1. 题目描述：
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
2. 输入格式：
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
3. 输出格式：
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。
4. 输入样例：
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 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
5. 输出样例：
Insertion Sort
1 2 3 5 7 8 9 4 6 0
Merge Sort
1 2 3 8 4 5 7 9 0 6
6. 性能要求：
Code Size Limit
16 KB
Time Limit
200 ms
Memory Limit
64 MB
思路：
题目要求根据原始序列和中间序列判断排序算法，这里我一开始统计从头开始的最长升序序列的元素个数，然后对比最长升序序列之后的元素是否与原始序列都相同，若都相同则为插入排序，否则为归并排序。
若为插入排序则对最长升序序列再加一个元素做排序即可，若为归并排序则需要统计当前的归并步数，因为归并排序两两组合，所以当前的步数为\(2^n(n=1,\dots,m)\)。从\(n=1\)开始遍历，最后对\(n+1\)步的每一组进行排序。
这里我的解法是利用题目描述取巧的做法，正规的做法可以参考大佬题解：PAT-Basic-1035. 插入与归并 – Lnyan's Blog (llonely.com)
My Code:
#include <stdio.h>
#include <stdlib.h>
void bubbleSort(int *array, int num);
int upOrder(int *array, int num); // retrun 1: ture, 0: flase
int main(void)
{
int num = 0;
int *pInt = NULL, *pInt2 = NULL;
int i = 0;
int currentStep = 0;
int flag = 0; // 0: Insertion Sort, 1: Merge Sort
int j = 0;
scanf("%d", &num);
pInt = (int *)malloc(sizeof(int) * num);
pInt2 = (int *)malloc(sizeof(int) * num);
if(!pInt || !pInt2) return -1; // check malloc return normal
for(i=0; i<num; i++)
{
scanf("%d", pInt+i);
}
for(i=0; i<num; i++)
{
scanf("%d", pInt2+i);
}
for(i=0; i<num; i++) // find currentStep
{
currentStep++;
if(pInt2[i] > pInt2[i+1])
{
break;
}
}
for(i=currentStep; i<num; i++) // testpoint6 reject, here assume Insertion Sort, for Merge Sort, currentStep is incorrect.
{
if(pInt[i] != pInt2[i])
{
flag = 1;
break;
}
}
if(flag) //Merge Sort
{
currentStep = 2; // least equal 2
for(i=4; i < num; i*=2) // for Merge Sort, find correct currentStep
{
currentStep = i;
for(j=0; (j+i)<num; j+=i)
{
if(!upOrder(pInt2+j, i))
{
currentStep = i/2;
break;
}
}
if(currentStep != i)
break;
}
printf("Merge Sort\n");
for(i=0; (i+currentStep*2)<=num; i+=currentStep*2)
{
bubbleSort(pInt2+i, currentStep*2);
}
if(i<num)
{
bubbleSort(pInt2+i, num-i);
}
for(i=0; i<num; i++) //output sequence
{
if(i==0)
printf("%d", pInt2[i]);
else
printf(" %d", pInt2[i]);
}
}
else //Insertion Sort
{
printf("Insertion Sort\n");
bubbleSort(pInt2, currentStep+1);
for(i=0; i<num; i++) //output sequence
{
if(i==0)
printf("%d", pInt2[i]);
else
printf(" %d", pInt2[i]);
}
}
free(pInt);
free(pInt2);
return 0;
}
void bubbleSort(int *array, int num) // num is number of array's element
{
int i=0, j=0;
int flag = 0; // sort already flag
int temp = 0;
for(i=num-1; i>0; i--)
{
flag = 0;
for(j=0; j<i; j++)
{
if(array[j]>array[j+1])
{
flag = 1;
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
if(!flag)
break;
}
return;
}
int upOrder(int *array, int num) // retrun 1: ture, 0: flase
{
int i = 0;
for(i=0; i < num-1; i++)
{
if(array[i]>array[i+1])
return 0;
}
return 1;
}