问题描述

根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式：
输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：
首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

解决方法

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 105;
//a用来做插入 b用来做结果的对比 c用来做归并
int a[maxn], b[maxn], c[maxn];
bool cmp(int a[], int b[], int n);
//二路归并
void mergeSort(int A[], int n)
{
  /*
    flag用于在选择相同的序列后在进行一次归并排序
    因为题目一定有结果不是插入一定是归并所以不用返回值
  */
  int flag = 1;
  for (int step = 2; step / 2 < n; step *= 2)
  {
    for (int i = 0; i < n; i += step)
    {
      int mid = i + step / 2 - 1;
      if (mid + 1 < n)
      {
        //直接使用sort来代替传统的merge函数
        sort(A + i, A + min(i + step - 1, n - 1) + 1);
      }
    }
    if (flag == 0)
      return;
    if (cmp(c, b, n))
      flag--;
  }
}
bool insertSort(int A[], int n)
{
  int j = 0;
  /*
    flag用于在选择相同的序列后在进行一次插入排序
  */
  int flag = 1;
  for (int i = 1; i < n; i++)
  {
    int temp = A[i];
    j = i;
    while (j > 0 && temp < A[j - 1])
    {
      A[j] = A[j - 1];
      j--;
    }
    A[j] = temp;
    if (flag == 0)
      return true;
    if (cmp(a, b, n))
    {
      flag--;
    }
  }
  return false;
}
/*
  比较两个数组是否相同
*/
bool cmp(int a[], int b[], int n)
{
  for (int i = 0; i < n; i++)
  {
    if (a[i] != b[i])
      return false;
  }
  return true;
}
/*
  输出数组的元素
*/
void printArr(int a[], int n)
{
  for (int i = 0; i < n; i++)
  {
    printf("%d", a[i]);
    if (i != n - 1)
      printf(" ");
  }
}
int main(void)
{
  //获取输入
  int m = 0;
  scanf("%d", &m);
  for (int i = 0; i < m; i++)
  {
    scanf("%d", a + i);
    c[i] = a[i];
  }
  for (int i = 0; i < m; i++)
  {
    scanf("%d", b + i);
  }

  //先看看是否是插入排序是就不用去执行归并了
  bool res1 = insertSort(a, m);
  if (res1)
  {
    printf("Insertion Sort\n");
    printArr(a, m);
  }
  else
  {
    //执行归并
    printf("Merge Sort\n");
    mergeSort(c, m);
    printArr(c, m);
  }
  return 0;
}

基本策略

• 写出插入排序和归并排序的非递归方法来记录每一次归并或者插入的序列做对比

结果展示

PatB1035.png

日期问题

• 因为把注释版的提交了一遍所以显示的是8/19