C++|PAT 乙级-1035 C++|c++

0、难点
1、题目
2、代码

0、难点

如何判断是插入排序还是归并排序方法是很巧妙的。

对于插入排序：是每次按顺序取出一个插入到前面的相应位置，那么前面排序好的队伍一定满足升序的规则，后面的还没排序，则和源数组一样的。
对于归并排序：每次划分后，在各自划分的区域排序，这样从全局来看，整个队伍就不一定满足升序的规则。

虽然对于同一数组实际上两者插入算法有可能出现相同结果，但是体题中说了唯一解，故这种多解的情况是不会出现在检查点中的。
那么思路就很简单了，首先按升序找到特征点i，如果i后面的和源数组一样，则是使用了插入排序，否则使用了归并排序（因为两两排序导致源数组后面的有变动）

文章图片

如何实现归并排序？
因为要输出下一步的排序结果，所以我们就要实现排序。插入排序好说，因为对于前i位已经排序好了，下一步肯定是排序前i+1位，直接sort(a,a+i+2)：即将前i+1进行排序。
而归并排序就没这么简单了，其流程如下：

文章图片

具体看代码。

1、题目 【C++|PAT 乙级-1035】1035 插入与归并 (25 分)
2、代码

#include #include using namespace std; int main() { 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]; 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; break; } } 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); //将剩下的部分排序，最后一次就是sort(a,a+n); } } for (j = 0; j < n; j++) { if (j != 0) printf(" "); printf("%d", a[j]); } return 0; }