关于算法-数据结构: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;
}