PAT A1089 Insert or Merge(C++)

发表于 | 分类于 | |
字数统计: 427 字 | 阅读时长 ≈ 2 分钟
PAT甲级目录 | PAT乙级目录

题目描述

原题地址：A1089 Insert or Merge
中文版：B1035 插入与归并

解题思路

插入排序中间序列特点：已排序部分有序，未排序部分不变。因此可以通过该特点判断是否为插入排序，否则为归并排序。

易错点

  • 注意输出的是下一轮排序序列

也许陌生的知识点

  • 插入排序
1
2
3
4
5
6
7
8
9
10
11
12
void InsertionSort1(){ // 标准操作
  j = i + 1;
  temp = S2[j];
  while(j > 0 && temp < S2[j - 1]){
    S2[j] = S2[j - 1];
    j--;
  }
  S2[j] = temp;
}
void InsertionSort2(){ // 偷懒操作
  sort(S1, S1 + i + 2);
}
  • 归并排序
1
2
3
4
5
6
7
8
9
void mergesort(){ //归并排序
  bool flag = false;
  for(int step = 2; !flag && step / 2 < N; step *= 2){
    if(issame(S1, S2) == true) flag = true;
    for(int i = 0; i < N; i+=step){
      sort(S1 + i, S1 + min(i + step, N));
    }
  }
}

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <algorithm>
using namespace std;
int N, S1[110], S2[110];
bool issame(int a[], int b[]){
  int i = 0;
  while(i < N && a[i] == b[i]) i++;
  return i == N;
}
void mergesort(){ //归并排序
  bool flag = false;
  for(int step = 2; !flag && step / 2 < N; step *= 2){
    if(issame(S1, S2) == true) flag = true;
    for(int i = 0; i < N; i+=step){
      sort(S1 + i, S1 + min(i + step, N));
    }
  }
}
int main(){
  scanf("%d", &N);
  for(int i = 0; i < N; i++){ scanf("%d", &S1[i]); }
  for(int i = 0; i < N; i++){ scanf("%d", &S2[i]); }
  int i, j;
  for (i = 0; i < N - 1 && S2[i] <= S2[i + 1]; i++);
  for (j = i + 1; S1[j] == S2[j] && j < N; j++);
  if (j == N) {
    printf("Insertion Sort\n");
    sort(S1, S1 + i + 2); // 插入排序
  }else{
    printf("Merge Sort\n");
    mergesort();
  }
  for(int i = 0; i < N; i++){
    if(i != 0) printf(" ");
    printf("%d", S1[i]);
  }
  return 0;
}