题目

根据维基百科的定义：

插⼊排序是迭代算法，逐⼀获得输⼊数据，逐步产⽣有序的输出序列。每步迭代中，算法从输⼊序列中取出⼀元素，将之插⼊有序序列中正确的位置。如此迭代直到全部元素有序。归并排序进⾏如下迭代操作：⾸先将原始序列看成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

题目分析

已知原始数组a，和对a排序过程中数组b，判断是归并排序还是插入排序，并打印再进行一轮排序后的结果

解题思路

判断是归并排序还是插入排序--插入排序过程中数组特点：第一个非升序数字（假设其索引为i）后的剩余数字都与原数组中相同位置数字相同

思路 01

如果是插入排序，对[0,i+1]的数字进行排序就是下一轮插入排序的结果
如果是归并排序，从原始数组使用非递归归并代码执行归并过程，并在每一轮判断排序结果是否已经是题目中已知的数组b，若是，则再进行一轮归并即可得出结果

思路 02

对原始数组分别进行插入排序和归并排序，在每一轮结束后，判断排序结果是否已经是题目中已知的数组b，若是，则再进行一轮排序即可得出结果

Code

Code 01

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

	// 1 接收输入

	int n, a[100], b[100], i, j;

	cin >> n;

	for (int i = 0; i < n; i++)

		cin >> a[i];

	for (int i = 0; i < n; i++)

		cin >> b[i];

	// 2 判断是哪种排序

	for (i = 0; i < n - 1 && b[i] <= b[i + 1]; i++); //找到第一个非升序数字下标

	for (j = i + 1; a[j] == b[j] && j < n; j++); //从非升序数字后，开始找第一个下标相同元素不同的下标

	if (j == n) {// 若第一个非升序数字后所有元素都与原数组相同，是插入排序

		cout << "Insertion Sort" << endl;

		sort(a, a + i + 2);

	} else {// 归并排序

		cout << "Merge Sort" << endl;

		int k = 1, flag = 1;

		while(flag) {

			flag = 0;

			for (i = 0; i < n; i++) {

				if (a[i] != b[i])

					flag = 1;

			}

			k = k * 2;

			for (i = 0; i < n / k; i++) // 对左边模拟归并排序

				sort(a + i * k, a + (i + 1) * k);

			sort(a + n / k * k, a + n); // 如果有右边剩余，对齐进行排序

		}

	}

	// 3 打印数组

	for (j = 0; j < n; j++) {

		if (j != 0) printf(" ");

		printf("%d", a[j]);

	}

	return 0;

}

Code 02

#include <iostream>

#include <algorithm>

using namespace std;

const int N=111;

int origin[N],tempOri[N],changed[N];

int n; //元素个数

// 判断数组是否相等

bool isSame(int A[],int B[]) {

	for(int i=0; i<n; i++)

		if(A[i]!=B[i])return false;

	return true;

}

// 打印数组

void showArray(int A[]) {

	for(int i=0; i<n; i++) {

		printf("%d",A[i]);

		if(i<n-1)printf(" ");

	}

	printf("\n");

}

// 插入排序

bool insert_sort() {

	bool flag = false;

	for(int i=1; i<n; i++) {

		if(i!=1&&isSame(tempOri,changed)) {

			flag = true;

		}

		// 写法一：

		int j,temp = tempOri[i];

		for(j=i-1; j>=0; j--) {

			if(temp>=tempOri[j])break;

			else tempOri[j+1]=tempOri[j];

		}

		tempOri[j+1]=temp;

		// 写法二：

//		int j=i,temp = tempOri[i];

//		while(j>0&&tempOri[j-1]>temp){

//			tempOri[j]=tempOri[j-1];

//			j--;

//		}

//		tempOri[j]=temp;

		if(flag)return true;

	}

	return false;

}

// 归并排序

void merge_sort() {

	bool flag = false;

	for(int step=2; step/2<=n; step*=2) { // 每次步长扩大一倍

		if(step!=2&&isSame(tempOri,changed))

			flag = true;

		for(int i=0; i<n; i+=step)  // 一轮排序，分成很多step组

			sort(tempOri+i,tempOri+min(i+step,n)); //每个step组升序排序

		if(flag) {

			showArray(tempOri);

			return;

		}

	}

}

int main(int argc, char * argv[]) {

	scanf("%d",&n);

	for(int i=0; i<n; i++) {

		scanf("%d",&origin[i]);

		tempOri[i]=origin[i];

	}

	for(int i=0; i<n; i++) {

		scanf("%d",&changed[i]);

	}

	if(insert_sort()) {

		printf("Insertion Sort\n");

		showArray(tempOri);

	} else {

		printf("Merge Sort\n");

		for(int i=0; i<n; i++) {

			tempOri[i]=origin[i]; //还原tempOri数组

		}

		merge_sort();

	}

	return 0;

}

巴特西

PAT Basic 插⼊与归并(25) [two pointers]

题目