关于算法-数据结构:PAT甲级1089-Insert-or-Merge

题目粗心：

给出一一个初始序列，能够将它应用插入排序或归并排序进行排序。当初给出一个序列，问它是由插入排序还是归并排序产生的，并输入下一步将会产生的序列。

算法思路：

这里须要齐全模仿间接插入排序和归并排序中的每一步，并且对于归并排序这里应用非递归形式比拟好管制排序的轮次。

间接插入排序

咱们将长度为n的序列[0,n-1]依照下标i进行划分，[0,i-1]为曾经排好序的序列，[i,n-1]为待排序序列，$1 \leq i\leq n-1$,对于每一个待排序元素temp[i]，咱们应用key暂存，并且在[0,i-1]中查找插入地位j,而后让temp[j]的值赋为key，这样一次插入排序过程就实现，接下来应用flag判断是否曾经和指标序列相等，如果是就输入Insertion Sort和temp数组，如果不是就查看以后的temp数组是否和指标数组统一，如果是就让flag赋值为true。

归并排序

每一次排序过程会将所有步长为step的元素进行排序，这里的步长从2开始，始终到n，每次归并会退让长成倍增加，对于步长的step的归并过程，每一次都从0地位的元素开始，取每step个元素为一组，进行排序，这里应用sort函数代替，须要留神的是，最初一组序列的长度可能小于step，所以sort函数的end地位得抉择i+step和n的最小值。同样的在一次归并过程完结后应用flag判断是否曾经和指标序列相等，如果是就输入Merge Sort和temp数组，如果不是就查看以后的temp数组是否和指标数组统一，如果是就让flag赋值为true。

留神点：

1、对于初始序列和指标序列相等的状况，须要排除该情景，也即是得先做一次排序后而后再比拟是否呈现和指标序列相等的数组。

提交后果：

AC代码：

#include <cstdio>
#include <algorithm>

using namespace std;

int init[105];
int partial_sorted[105];
int temp[105];//工作数组

// 判断数组a和b是否相等
bool isSame(const int a[],const int b[],int n){
    for (int i = 0; i < n; ++i) {
        if(a[i]!=b[i]){
            return false;
        }
    }
    return true;
}

void print(const int a[],int n){
    for (int i = 0; i < n; ++i) {
        printf("%d",a[i]);
        if(i<n-1) printf(" ");
    }
}

// 插入排序
bool insertionSort(int n){
    bool flag = false;//是否和指标序列相等
    // [i,n-1]为待排序元素,[0,i-1]为曾经排序的元素
    for (int i = 1; i < n; ++i) {
        int j=i;//插入地位,初始在有序序列前面插入
        int key = temp[i];//待插入元素
        while (j>0&&key<temp[j-1]){
            temp[j] = temp[j-1];
            --j;
        }
        // 找到插入地位
        temp[j] = key;
        if(flag) {
            printf("Insertion Sort\n");
            print(temp,n);
            return true;
        }
        if(isSame(temp,partial_sorted,n)){
            // 曾经和指标数组相等设置为true，并且在进一步排序后再退出
            flag = true;
        }
    }
    return flag;
}

void mergeSort(int n){
    bool flag = false;//是否和指标序列相等
    // 步长从2开始，最长为n
    for (int step=2;step<=n;step*=2) {
        // 对于所有步长为step的序列进行排序，最初一个序列的长度可能没有step，所以得记录i+step和n的最小值
        for (int i = 0; i<n; i+=step) {
            sort(temp+i,temp+min(i+step,n));
        }
        if(flag) {
            printf("Merge Sort\n");
            print(temp,n);
            return;
        }
        if(isSame(temp,partial_sorted,n)){
            // 曾经和指标数组相等设置为true，并且在进一步排序后再退出
            flag = true;
        }
    }
}

int main(){
    int N;
    scanf("%d",&N);
    for (int i = 0; i < N; ++i) {
        scanf("%d",&init[i]);
        temp[i] = init[i];
    }
    for (int i = 0; i < N; ++i) {
        scanf("%d",&partial_sorted[i]);
    }
    if(!insertionSort(N)){
        // 从新将temp数组赋值为init数组
        for (int i = 0; i < N; ++i) {
            temp[i] = init[i];
        }
        mergeSort(N);
    }
    return 0;
}