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
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAX 105
using namespace std;int main(){int a[MAX],b[MAX];int N;scanf("%d",&N);for(int i=0;i<N;i++){scanf("%d",&a[i]);}for(int i=0;i<N;i++){scanf("%d",&b[i]);}int is1=1,tag;for(int i=1;i<N;i++){if(b[i]<b[i-1]){tag=i;break;}}for(int i=tag;i<N;i++){if(b[i]!=a[i]){is1=0;break;}}if(is1==1){printf("Insertion Sort\n");int n=tag+1;sort(b,b+n);printf("%d",b[0]);for(int i=1;i<N;i++){printf(" %d",b[i]);}}else{printf("Merge Sort\n");int isok=0,k=1;while(isok==0){isok=1;for(int i=0;i<N;i++){if(a[i]!=b[i]){isok=0;break;}}k*=2;int left_min;for(left_min=0;(left_min+k-1)<N;left_min+=k){sort(a+left_min,a+left_min+k);}if(left_min<N){sort(a+left_min,a+N);}}printf("%d",a[0]);for(int i=1;i<N;i++){printf(" %d",a[i]);}}return 0;
}
本题关键在于理解归并。
传统的归并算法分为递归和非递归两种。
本题只要掌握了非递归算法的思路即可求解。
在网上搜到一段比较容易理解的非递归归并算法，以便以后翻看时理解。
/*** merge_sort: 非递归实现 --迭代* 非递归思想: 将数组中的相邻元素两两配对。用merge函数将他们排序，* 构成n/2组长度为2的排序好的子数组段，然后再将他们排序成长度为4的子数组段，* 如此继续下去，直至整个数组排好序。**/#include <stdio.h>#include <stdlib.h>#define LEN 13// merge_sort(): 非递归实现-自底向上// 将原数组划分为left[min...max] 和 right[min...max]两部分void merge_sort(int *list, int length){int i, left_min, left_max, right_min, right_max, next;int *tmp = (int*)malloc(sizeof(int) * length);if (tmp == NULL){fputs("Error: out of memory\n", stderr);abort();}for (i = 1; i < length; i *= 2) // i为步长，1,2,4,8……{for (left_min = 0; left_min < length - i; left_min = right_max){right_min = left_max = left_min + i;right_max = left_max + i;if (right_max > length)right_max = length;next = 0;while (left_min < left_max && right_min < right_max)tmp[next++] = list[left_min] > list[right_min] ? list[right_min++] : list[left_min++];while (left_min < left_max)list[--right_min] = list[--left_max];while (next > 0)list[--right_min] = tmp[--next];}int t;for (t=0;t<length;t++)printf("%d ",list[t]);printf("\n");}free(tmp);} int main(void){int a[LEN] = { 3,1,2,8,7,5,9,4,0,6,-1,-2,-3};int i;for (i = 0; i < LEN; i++)printf("%d ", a[i]);printf("\n");merge_sort(a, LEN);// print arrayfor (i = 0; i < LEN; i++)printf("%d ", a[i]);return 0;}上面这一段代码出处：http://www.cnblogs.com/bluestorm/archive/2012/09/06/2673138.html