中山市西区建设局网站,黄页号码查询,网站的布局和配色,东莞网站推广运营题目描述
根据维基百科的定义#xff1a;
插入排序是迭代算法#xff0c;逐一获得输入数据#xff0c;逐步产生有序的输出序列。每步迭代中#xff0c;算法从输入序列中取出一元素#xff0c;将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如…题目描述
根据维基百科的定义
插入排序是迭代算法逐一获得输入数据逐步产生有序的输出序列。每步迭代中算法从输入序列中取出一元素将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作首先将原始序列看成 N N N 个只包含 1 1 1 个元素的有序子序列然后每次迭代归并两个相邻的有序子序列直到最后只剩下 1 1 1 个有序的序列。
现给定原始序列和由某排序算法产生的中间序列请你判断该算法究竟是哪种排序算法
输入格式
输入在第一行给出正整数 N ( ≤ 100 ) N (\leq 100) N(≤100)随后一行给出原始序列的 N N N 个整数最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。
输出格式
首先在第 1 1 1 行中输出 Insertion Sort 表示插入排序、或 Merge Sort 表示归并排序然后在第 2 2 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解析
插入排序。最前面若干个数保证有序后续部分保持原样因此我们就可以遍历一次找出第一个逆序的位置记为 p o s pos pos那么我们就比较一下 a , b a,b a,b 数组对于 [ p o s , n ] [pos,n] [pos,n] 这个区间内是否相同如果相同那么就说明是插入排序。归并排序。第一次每两个一组内部排序第二次四个一组内部排序以此类推。因此我们可以枚举 2 , 4 , 8 , . . . 2,4,8,... 2,4,8,...对 a a a 数组进行排序直到某一次发现排完序之后 a a a 数组和 b b b 数组相同了假设当前每一组的元素个数为 i i i那么我们下一步就是要将每 i ∗ 2 i*2 i∗2 个元素为一组进行排序再排序一次即可。
代码实现
#include bits/stdc.h
using namespace std;
const int N 105;
int a[N], b[N];
void solve() {int n;cin n;for (int i 1; i n; i) cin a[i];for (int i 1; i n; i) cin b[i];int pos -1;for (int i 2; i n; i) {if (b[i] b[i - 1]) {pos i;//找到第一个逆序的位置break;}}bool ok true;//判断是否是插入排序for (int i pos; i n; i) if (a[i] ! b[i]) ok false;if (ok) {cout Insertion Sort\n;sort(a 1, a pos 1);//下一步就是把[1,pos]排好序for (int i 1; i n; i) {if (i ! 1) printf( );cout a[i];}} else {cout Merge Sort\n;for (int i 2; i n; i * 2) {//枚举当前排序块的长度for (int l 1; l n; l i) sort(a l, a min(n, l i - 1) 1);bool ok true;//判断是否到达题目给定的状态for (int k 1; k n; k) if (a[k] ! b[k]) ok false;//判断是否相同了if (ok) {//如果到达,直接模拟下一步即可i * 2;for (int l 1; l n; l i) sort(a l, a min(n, l i - 1) 1);for (int j 1; j n; j) {if (j ! 1) cout ;cout a[j];}return;}}}
}
int main()
{int t 1;//cint;while (t--) solve();return 0;
}
