本文主要是介绍1035 插入与归并，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成 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：
Merge Sort
1 2 3 8 4 5 7 9 0 6
/*
这里两个算法学的不好，今天学习一下算法再来看
然后这里行末不输出空格，所以这里选择数组进行输入数据;这里相当于第一行数据是原始数据
第二行是排序过程的数据，属于中间状态;
我们可以用另外一个数组存放一组数据，直接对其进行排序;插入排序未排序的与原始数据
后段一致，可以进行比较判断插入排序;现在要考虑怎么比较中间序列和原始序列;
这里N最大值为100，插入排序最坏的情况是逆序排放，就是降序排列的，每一个都要移动，
时间复杂度为O(n*n);那么中间状态最坏的情况有100*100==10000种情况;
插入排序的前端有序，后端为原始序列;所以对于插入排序是比较好判别的，那么又因为测试序列
属于的排序算法唯一，所以不是插入排序的情况下就只能是归并排序;
然后还要输出算法的下一步，所以这里要实现两个算法;这里要考虑归并的分组，就是怎么分组，怎么看出来时几个一组，这里计算机只能通过比较才能看
出来，不像人能够直观的看出来，这里我们分组只要让下标一致就可以了，
比如下标012345
0/2==0，1/2==0;
2/2==1，3/2==1;
4/2==2，5/2==2;
这里可以通过将下标除以基数得到对应的段数;然后对基数取余就得到段内的下标;
跟段地址还有点相通呢;这里归并的段内排序我就直接用qsort了，方便一点;
用sort了，qsort不知道哪里出了点问题;
*/
#include<iostream>
#include<cstdlib>
#include <algorithm> //sort在算法头文件里;
using namespace std;
//以插入排序为基准判断排序方式;
int check(int* data,int* mid,int length){//这里注意传入三个参数，一个是原始序列，一个是中间序列，一个是长度，根据原始求下一步;//检查后端;这里前端是已经排序的，不方便比较，直接从后端没操作的数据比较;int index=0; //标志不匹配位置的下标;for(int i=length-1;i>=0;i--){ //这里插入排序后端数据未使用原始与中间序列一致;if(data[i]!=mid[i]){index=i;break;}}//检查前端是否是有序序列;for(int i=0;i<index-1;i++){if(mid[i]>mid[i+1]){return -1; //这里返回就是归并排序;}}return 1; //这里返回就是插入排序;
}
//输出数组;
void out(int* a,int length){for(int i=0;i<length-1;i++){cout<<a[i]<<' ';}cout<<a[length-1]<<endl;
}
//归并排序子函数;
void merge(int* data,int N,int seg){ //seg表示归并段长度;for(int i=0;i<N;i+=seg){if(i+seg<=N){sort(data+i,data+i+seg);}else{sort(data+i,data+N);}}
}
//比较函数;判断两个数列是否等价;
bool myequal(int* a,int* b,int length){for(int i=0;i<length;i++){if(a[i]!=b[i]){return false;}}return true;
}
//归并排序函数;
void mergeSort(int* data,int* mid,int N){ //segment是排序段长;//这里归并选择用两个长度的段进行排序;//这里并不需要按找归并的方式合并相邻的两个数列;//只需要让两个数列合并成一个有序数列就好了;int count=1; //归并段数的长度;for(count=2;count<=N;count*=2){if(myequal(data,mid,N)){ //如果相等只需要在归并一次即可退出;merge(mid,N,count);break;}else { //不相等继续归并;第一次一定不等;merge(data,N,count);}}
}
//插入排序函数;
void insertSort(int* data,int* mid,int N){int index=0; //标记不匹配的下标位置;int temp; //存放即将操作的元素;//找后端下标;for(int i=N-1;i>=0;i--){ //这里插入排序后端数据未使用原始与中间序列一致;if(data[i]!=mid[i]){index=i;break;}}//进行一次插入排序;temp=mid[index+1];for(int i=index;i<N&&i>=0;i--){if(temp<mid[i]){mid[i+1]=mid[i];}else if(temp>=mid[i]){mid[i+1]=temp;break;}}
}
int main(){//输入数据;int N;cin>>N;//输入原始序列;int data[N];for(int i=0;i<N;i++){cin>>data[i];}//输入中间序列;int mid[N];for(int i=0;i<N;i++){cin>>mid[i];}//尝试判断排序类型;char type='I'; //‘I’表示插入排序,'M'表示归并排序;if(check(data,mid,N)==1){ cout<<"Insertion Sort"<<endl;type='I';}else if(check(data,mid,N)==-1){cout<<"Merge Sort"<<endl;type='M';}//指向排序的下一步;if(type=='I'){ //插入排序;insertSort(data,mid,N);out(mid,N);}else if(type=='M'){ //归并排序;mergeSort(data,mid,N);out(mid,N);}return 0;
}
/*
反思：这里不要陷入这个牛角尖，多用其他方法，都可以，然后就是排序算法的熟悉，还需要再进步
这道题还没有完全写完;部分正确;
*/这篇关于1035 插入与归并的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
