数据结构PTA7.1.2 插入排序还是归并排序？（两种解法）
每
日
一
题
一壶酒一包烟 一个bug调一天
1. 题目
背景
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 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
2. 解法一
思路
首先看到题目，最容易想到的就是，分别写出插入排序算法，以及归并排序算法，然后算法每排序一次，就进行检查，检查排序后的数组是否与目标数组完全一致，中间设置一个标志变量 flag，一旦检查到一致，就输出 “Insertion Sort” 或者 “Merge Sort”，并之后再进行一次排序，然后输出排序结果。
如果直到数组排序完成，发现排序后的数组与目标数组仍然不一致，则没有任何输出。
因为题目中说明 “保证每组测试的结果是唯一的”，所以在程序中可以先进行 Insertion Sort 检查，如果检查发现是 Insertion Sort，那么可以不执行 Merge Sort 检查。
注意 Merge Sort 检查算法必须用非递归算法实现。
程序优点：正确性显而易见，算法容易理解。程序缺点：每检查一次就要进行遍历检查，大大增加程序的时间复杂度。
实现
C 语言代码
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void Swap(int *a, int *b)
{
int tmp = *a; *a = *b; *b = tmp;
}
bool IsEqual(int *P, int *PMid, int N)
{
for(int i=0; i<N; i++)
{
if(P[i] != PMid[i])
return false;
}
return true;
}
void PrintResult(int *P, int N)
{
for(int i=0; i<N; i++)
{
if(i==0)
printf("%d", P[i]);
if(i!=0)
printf(" %d", P[i]);
}
}
int InsertSortTest(int *P, int *PMid, int N)
{
int i,j;
int flag = 0;
for(i=1; i<N; i++)
{
int tmp = P[i];
for(j=i-1; j>=0; j--)
{
P[j+1] = P[j];
if(P[j]<=tmp)
break;
}
Swap(&P[j+1], &tmp);
if(IsEqual(P, PMid, N))
{
printf("Insertion Sort\n");
flag = 1;
continue;
}
if(flag==1)
{
PrintResult(P, N);
return 1;
}
}
return 0;
}
void Merge(int *P, int *tmpP, int L, int R, int RightEnd)
{
int LeftEnd = R-1;
int tmp = L;
int ElementN = RightEnd-L+1;
while(L<=LeftEnd && R<=RightEnd)
{
if(P[L]>P[R])
tmpP[tmp++] = P[R++];
else
tmpP[tmp++] = P[L++];
}
while(L<=LeftEnd) tmpP[tmp++] = P[L++];
while(R<=RightEnd) tmpP[tmp++] = P[R++]; //build the whole tmp[]
for(int i=0; i<ElementN; i++,RightEnd--) //copy to P[]
P[RightEnd] = tmpP[RightEnd];
}
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 )
Merge( A, TmpA, i, i+length, N-1);
else
for ( j = i; j < N; j++ )
TmpA[j] = A[j];
}
int MergeSortTest(int A[], int *PMid, int N )
{
int length;
int *TmpA;
int flag = 0;
length = 1;
TmpA = malloc( N * sizeof( int) );
if ( TmpA != NULL ) {
while( length < N ) {
Merge_pass( A, TmpA, N, length );
length *= 2;
if(IsEqual(A, PMid, N))
{
printf("Merge Sort\n");
flag = 1;
continue;
}
if(flag==1)
{
PrintResult(A, N);
return 1;
}
}
free( TmpA );
}
return 0;
}
int main()
{
int N;
scanf("%d", &N);
int *P1 = (int *)malloc(N*sizeof(int));
int *P2 = (int *)malloc(N*sizeof(int));
int *PMid = (int *)malloc(N*sizeof(int));
for(int i=0; i<N; i++)
{
scanf("%d", &P1[i]);
}
for(int i=0; i<N; i++)
P2[i] = P1[i];
for(int i=0; i<N; i++)
{
scanf("%d", &PMid[i]);
}
if(!InsertSortTest(P1, PMid, N))
MergeSortTest(P2, PMid, N);
free(P1);
free(P2);
free(PMid);
return 0;
}
3. 解法二
思路
抓住插入排序和归并排序的特点：插入排序的前一部分是有序的，后一部分是无序的，无序部分与初始给定的数组是一致的。如:
初始序列:3 1 2 8 7 5 9 4 6 0中间序列:1 2 3 7 8 5 9 4 6 0
中间序列前五个满足递增，后五个无序但与初始序列完全一致，因此这是插入排序的中间过程。
根据上述特点，可以写一个 IsInsertion 函数，判断中间序列为插入排序 or 归并排序（题目规定，非插入，即归并）判断出
是插入排序后，只需要往后进行一步即可，IsInsertion 函数可以返回需要进行插入排序的元素指针，即数组下标如果发现
是归并排序，需要判断归并排序所进行的长度，如：初始序列:3 1 2 8 7 5 9 4 0 6中间序列:1 3 2 8 5 7 4 9 0 6
显然，这个长度是 2，下一步就是四个元素一段，进行归并。
判断长度可以这样进行：
若 a [2i-1]<a [2i]，对所有的奇数 i 都成立，那么这个长度至少是 2×2.
若 a [4i-1]<a [4i]，对所有的奇数 i 都成立，那么这个长度至少是 4×2.一旦发现 a [mi-1]>a [mi]，对某个的奇数 i 成立，那么这个序列的归并长度是 m；
那么下一步进行长度为 m 的归并排序，然后输出即可。
为什么要强调是奇数i？
举个例子初始序列：4 2 1 3 13 14 12 11 8 9 7 6 10 5中间序列：1 2 3 4 11 12 13 14 6 7 8 9 5 10
首先观察，可知中间序列处于归并排序的长度为 4 的阶段，因为 9>5。因为如果是连续的 i，那么
如果 i 是奇数，那么当 m 取 2 的时候，a [2i-1]<a [2i] 是否成立这件事情是在检查每段长度为 4 的正中间的两个元素之间的大小关系，一旦 a [2i-1]<a [2i] 不成立，就意味着长度为 4 的这一段内，并不是非单减，这也就意味着归并长度不是 4 而是 2；同理，对于 m 取 4 的情况，它是检查长度为 8 的段内非单减情况，一旦检查通过，则归并长度至少为 8，一旦没通过，则归并长度为 4.
同样地，这里的归并排序只能用非递归实现。
实现
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void PrintResult(int *P, int N)
{
for(int i=0; i<N; i++)
{
if(i==0)
printf("%d", P[i]);
if(i!=0)
printf(" %d", P[i]);
}
}
int IsInsertion(int *P, int *PMid, int N)
{
int i;
for(i=0; i<N-1; i++)
{
if(PMid[i]>PMid[i+1])
break;
}
for(int j=i+1; j<N; j++)
{
if(P[j]!=PMid[j])
return 0;
}
//finishing the sort is impossible, beacause the InsertionSort is the same as MergeSort in this situation
return i;
}
void NextInsertion(int *PMid, int k, int N)
{
printf("Insertion Sort\n");
int i;
int tmp = PMid[k+1];
for(i=k+1; i>0 && PMid[i-1]>tmp ; i--)
PMid[i] = PMid[i-1];
PMid[i] = tmp;
PrintResult(PMid, N);
}
int MergeLength(int *PMid, int N)
{
int L,i;
for(L=2; L<N; L=2*L)
{
for(i=1; L*i<N; i+=2)
{
if(PMid[L*i-1]>PMid[L*i])
return L;
}
}
}
void Merge(int *A, int *tmpA, int L, int R, int RightEnd)
{
int LeftEnd = R-1;
int tmpi = L;
while(L<=LeftEnd && R<=RightEnd)
{
if(A[L]>A[R])
tmpA[tmpi++] = A[R++];
else
tmpA[tmpi++] = A[L++];
}
for(; L<=LeftEnd; ) tmpA[tmpi++] = A[L++];
for(; R<=RightEnd; ) tmpA[tmpi++] = A[R++];
}
void NextMerge(int *PMid, int N)
{
printf("Merge Sort\n");
int *tmpA = (int *)malloc(N*sizeof(int));
int L = MergeLength(PMid, N);
int i,j;
for(i=0; (i+1)*2*L-1<N ;i++)
Merge(PMid, tmpA, i*2*L, i*2*L+L, (i+1)*2*L-1);
if(i*2*L+L-1<N) //one part is complete, and the other part is incomplete
{
Merge(PMid, tmpA, i*2*L, i*2*L+L, N-1);
}
if(i*2*L+L-1>=N) //surplus part is incomplete
{
for(j=i*2*L; j<N; j++)
tmpA[j] = PMid[j];
}
PrintResult(tmpA, N);
free(tmpA);
}
int main()
{
int N;
scanf("%d", &N);
int *P = (int *)malloc(N*sizeof(int));
int *PMid = (int *)malloc(N*sizeof(int));
for(int i=0; i<N; i++)
scanf("%d", &P[i]);
for(int i=0; i<N; i++)
scanf("%d", &PMid[i]);
int k = IsInsertion(P, PMid, N);
if(k)
NextInsertion(PMid, k, N);
else
NextMerge(PMid, N);
free(P);
free(PMid);
return 0;
}如果喜欢文章作者
欢迎大（xue）家（mei）来撩
美好的一天，从一道PTA开始