a站下载,赣州微信公众号制作,wordpress迁移安装,网站建设哪家有1035. 插入与归并(25) 时间限制200 ms内存限制65536 kB代码长度限制8000 B判题程序Standard作者CHEN, Yue根据维基百科的定义#xff1a; 插入排序是迭代算法#xff0c;逐一获得输入数据#xff0c;逐步产生有序的输出序列。每步迭代中#xff0c;算法从输入序列中取出一元… 1035. 插入与归并(25) 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 作者 CHEN, Yue 根据维基百科的定义 插入排序是迭代算法逐一获得输入数据逐步产生有序的输出序列。每步迭代中算法从输入序列中取出一元素将之插入有序序列中正确的位置。如此迭代直到全部元素有序。 归并排序进行如下迭代操作首先将原始序列看成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 解析学习的本质和目的是善假于物如果一切都是从0做起那在这个世界上是生存不下去的牛顿都说过“站在巨人的肩上”所以学习算法一样你可以用现有的算法和工具解决问题至于深层次的问题的理解是一个漫长的边实践边思考的过程记得一个数学老师指点学生怎样学习微积分大致意思是说“只要懂得基本的概念就可以了剩下的功夫就是做题做题做题在实践中理解更深的概念如果上来就往底层挖结果就是陷入一个知识黑洞中而再也出不来了学习的本质就是两个认识工具熟练使用工具”。 代码 #include stdio.h
#include stdlib.hint cmp(const void *a, const void *b)
{return *(int *)a - *(int *)b;
}int is_same(int *a, int *b, int N)
{int i;int flag 1;for (i 0; i N; i){if (a[i] ! b[i]){flag 0;break;}}return flag;
}void print(int *arr, int N)
{int loopk;for (loopk 0; loopk N; loopk){printf(%d%s, arr[loopk], loopk N-1 ? : );}printf(\n);
}int main()
{int N;int input[27], part_sort[27], sorted[27];int loopi, loopj, loopk;int flag 1;int once 0;scanf(%d, N);for (loopi 0; loopi N; loopi){scanf(%d, inputloopi);sorted[loopi] *(inputloopi);}for (loopi 0; loopi N; loopi){scanf(%d, part_sortloopi);}for (loopi 0; loopi N-1; loopi){if (part_sort[loopi] part_sort[loopi1]){break;}}for (loopj loopi1; loopj N; loopj){if (part_sort[loopj] ! input[loopj]){flag 0;break;}}#if 0loopi N - 1;while (loopi 0 input[loopi]part_sort[loopi]){loopi--;}qsort(sorted, loopi1, sizeof(int), cmp);for (loopj 0; loopj loopi; loopj){if (sorted[loopj] ! part_sort[loopj]){flag 0;break;}}#endifif (flag 1){printf(Insertion Sort\n);qsort(sorted, loopi2, sizeof(int), cmp);print(sorted, N);}else{printf(Merge Sort\n);for (loopi 1; loopi 20*N; loopi * 2){once is_same(input, part_sort, N);loopj 0; // [loopj*loopi, (loopj1)*loopi-1] partion to be sortwhile ((loopj1) * loopi N){qsort(inputloopj*loopi, loopi, sizeof(int), cmp);loopj;}if (loopj * loopi N){qsort(inputloopj*loopi, N-loopj*loopi, sizeof(int), cmp);}if (once 1){print(input, N);break;}}}return 0;
} 下面分析一下为什么最后注释掉的那段代码是错误的
