#include <stdio.h>#define SWAP(a,b) a = b-a+(b=a) #define N 105 void Input(int *unSorted, int partialSorted[], int *n){	int i;	scanf("%d",n);	for(i=1;i<=*n;i++) scanf("%d",&unSorted[i]);	for(i=1;i<=*n;i++) scanf("%d",&partialSorted[i]);}void AdjustDown(int *partialSorted, int k, int n){	//将元素k向下进行调整	int i;	partialSorted[0] = partialSorted[k]; //partialSorted[0]暂存	for(i=2*k;i<=n;i*=2){ //沿key较大的子结点向下筛选		if(i<n && partialSorted[i]<partialSorted[i+1]) 			i ++; //取key值较大的子结点的下标		if(partialSorted[0]>=partialSorted[i]) break; //筛选结束		else{			partialSorted[k] = partialSorted[i]; //将partialSorted[i]调整到双亲结点上			k = i; //修改k值,以便继续向下筛选		} 	} 	partialSorted[k] = partialSorted[0]; //被筛选结点的值放入最终的位置 } void BuildMaxHeap(int *partialSorted, int n){	int i = n/2;	for(;i>0;i--) //从i=[n/2]~1,反复调整堆		AdjustDown(partialSorted,i,n); }int HeapSort(int *unSorted, int *partialSorted, int n){  	int index = n;	for(;index>1 && partialSorted[index-1]<=partialSorted[index];index--);	//进入下一次迭代 	BuildMaxHeap(partialSorted,index); //asending:大顶堆	SWAP(partialSorted[index],partialSorted[1]); //输出堆顶元素(和堆底元素交换) 	AdjustDown(partialSorted,1,index-1); //整理,把剩余的index-2个元素整理成堆	printf("Heap Sort\n"); }int InsertionSort(int unSorted[], int partialSorted[], int n){	int i,j,index,low,high,mid;	for(i=1;i<n && partialSorted[i]<=partialSorted[i+1];i++);	index = ++i;	for(;i<=n && unSorted[i]==partialSorted[i];i++);	if(i>n){		//折半插入(稳定) 		partialSorted[0] = partialSorted[index]; //暂存partialSorted[index] 		low = 1, high = index-1;		while(low<=high){			mid = (low+high)/2; //取中间点 			if(partialSorted[mid]>partialSorted[0]) high = mid-1; //查找左半子表 			else low = mid+1; //查找右半子表 		}		for(j=index-1;j>=high+1;j--)			partialSorted[j+1] = partialSorted[j]; //统一后移元素,空出插入位置		partialSorted[high+1] = partialSorted[0];		printf("Insertion Sort\n");		return 1;	}		return 0;}void Show(int partialSorted[], int n){	int i;	for(i=1;i<=n;i++){		printf("%d",partialSorted[i]);		if(i==n) printf("\n");		else printf(" ");	}}int main(){	int unSorted[N],partialSorted[N];	int n;//	freopen("Data.txt","r",stdin); //段错误 	Input(unSorted,partialSorted,&n);	//模拟来判断unSorted和partialSorted相等是非常愚蠢的行为 	//运用一下堆排序和插入排序的特征,处理问题更快捷 	//先做插入排序的判断,然后进行堆排序	//插入排序不影响全局,而堆排序影响全局(亦即无法根据特征性质判断是否为堆排序)	if(InsertionSort(unSorted,partialSorted,n));	else HeapSort(unSorted,partialSorted,n);	Show(partialSorted,n);	return 0;}