专栏首页AI那点小事1035. 插入与归并(25)

1035. 插入与归并(25)

根据维基百科的定义:

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

归并排序进行如下迭代操作:首先将原始序列看成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

#include <iostream>
using namespace std;

bool check(int* A , int* Order,int N)
{
    bool flag = true;
    for ( int i = 0 ; i < N ; i++){
        if ( A[i] != Order[i]){
            flag = false;
            break;
        }
    }
    return flag;
}

void Swap(int* a , int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Print(int* A ,int N)
{
    cout<<A[0];
    for ( int i = 1 ; i < N ; i++){
        cout<<" "<<A[i];
    }
}

bool Insert_Sort(int* A ,int* B , int N)
{
    bool isInsert = false;
    int i , j;
    for ( i = 1 ; i < N ; i++){
        int tmp = A[i];
        for ( j = i ; j > 0 && A[j-1] > tmp ; j--){
            A[j] = A[j-1];
        }
        A[j] = tmp;
        if(isInsert){
            cout << "Insertion Sort" << endl;
            Print(A,N);
            break;
        }else if(check(A,B,N)){
                isInsert = true;
            }
    }
    return isInsert;
 } 

void Merge(int a[], int low, int mid, int high)
{
    int t[high - low];
    int i = low, j = mid, k = 0;

    while(i < mid && j < high){
        if(a[i] <= a[j])
            t[k ++] = a[i ++];
        else
            t[k ++] = a[j ++];
    }

    while(i < mid)
        t[k ++] = a[i ++];
    while(j < high)
        t[k ++] = a[j ++];

    for(i = low, k = 0; i < high; i ++){
        a[i] = t[k ++];
    }
}

bool Merge_Sort(int* A , int* B,int N)
{
    int i ,j;
    bool isMerge = false;
    for ( i = 1 ; i < N ; i *= 2){
        for ( j = 0 ; j < N ; j += i*2){
            if ( j + i*2 <= N){
                Merge(A,j,j+i,j+i*2);
            }else if ( j + i <= N){
                Merge(A,j,j+i,N);
            }
        }
        if(isMerge){
            cout << "Merge Sort" << endl;
            Print(A,N);
            break;
        }else if(check(A,B,N)){
                isMerge = true;
            }
    }
    return isMerge;
}

int main()
{
    int N; 
    cin>>N;
    int A[N],C[N];
    int B[N];
    for ( int i = 0 ; i < N ; i++){
        cin>>A[i];
        C[i] = A[i];
    } 
    for ( int i = 0 ; i < N ; i++){
        cin>>B[i];
    }

    bool flag1 = Merge_Sort(A,B,N);
    if ( flag1 == true){
        return 0;
    }else{
        bool flag2 = Insert_Sort(C,B,N);    
        return 0;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • 算法训练 矩阵乘法

    问题描述   输入两个矩阵,分别是m*s,s*n大小。输出两个矩阵相乘的结果。 输入格式   第一行,空格隔开的三个正整数m,s,n(均不超过200...

    AI那点小事
  • 历届试题 最大子阵

    问题描述   给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。

    AI那点小事
  • 1065. 单身狗(25)

    “单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人,以便给予特殊关爱。

    AI那点小事
  • 2017年中国大学生程序设计竞赛-中南地区赛暨第八届湘潭市大学生计算机程序设计大赛题解&源码(A.高斯消元,D,模拟,E,前缀和,F,LCS,H,Prim算法,I,胡搞,J,树状数组)

    A-------------------------------------------------------------------------------...

    Angel_Kitty
  • 「2017 Multi-University Training Contest 2」2017多校训练2

    给定数组a[1..n]和b[1..n],b[i]在[1~n]内。要得到a[n+1..2n],每次选b数组的一个,令a[i]为j=b[k]到i-1位置中最大的a[...

    饶文津
  • 【USACO 1.2】Palindromic Squares

    饶文津
  • 【CodeForces 620D】Professor GukiZ and Two Arrays

    两个数列,一个有n个数,另一个有m个数,让你最多交换两次两个数列的数,使得两个数列和的差的绝对值最小,求这个差的绝对值、最少交换次数、交换数对

    饶文津
  • P1903 【模板】分块/带修改莫队(数颜色)

    题目描述 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到...

    attack
  • 图论--拓扑排序--模板

    风骨散人Chiam

扫码关注云+社区

领取腾讯云代金券