[数据结构与算法]1098 Insertion or Heap Sort (25 分)以及堆排序思想

给定序列长度n，给定初始序列，再给定经过若干次排序后的序列，判断是插入排序还是堆排序，并进行下一次排序。题目链接

思路：

插入排序特点：序列前半部分有序，后半部分不变。
堆排序特点：后半部分有序，前半部分无序，也无规律，所以如果通过判断后半部分有序可能也可以判断是哪一种排序。
这里给出先判断插入排序,如果是插入排序，那么只要进行下一次排序就好了，否则就是堆排序，前面提到，由于堆排序后半部分有序，则可以判断下一个需要排序的位置。而不用从头开始推演一遍，对于每个序列进行比较。
堆排序通用模板要点:
最后一个有儿子的结点开始建堆，循环直到根节点也建立好。
因为根节点是整个堆的最大值(最大堆)，通过与最后一个结点交换，从而达到排序的功能，之后将排好序的结点排除在外。
如果没有哨兵，则child=2*parent在根节点无法更新。

void percdown(int a[],int i,int n)  
{
	int child,parent;
	int max=a[i];
	for(parent=1;parent*2<=n;parent=child) 
	{
		child=2*parent;
		if(child!=n-1&&a[child]<a[child+1]) //找两个儿子结点较大值。
		child++;
		if(max>=a[child]) break;
		else a[parent]=a[child];
	}
	a[parent]=max;
}
void CreatHeap(int a[],int n)
{
	for(int i=n/2;i>=0;i--)   //从最后一个有儿子的结点开始
	percdown(a,i,n);
}
void Heap_Sort(int a[],int n)
{
	CreatHeap(a,n);
	for(int i=n-1;i>0;i=-)
	{
	Swap(a[0],a[i]); //交换根节点和最后一个结点。
	percdown(a,0,i);
	}

}

主程序

#include<stdio.h>
const int maxn=105;
#define INF 1e5
int a[maxn],b[maxn];
void getInit(int a[],int n)
{
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
}
void Travers(int a[],int n)
{
	for(int i=0;i<n;i++)
	{
		printf("%d",a[i]);
		if(i!=n-1) printf(" ");
	}
	printf("\n");
}
void swap(int& a,int &b)
{
	int t=a;
	a=b;
	b=t;
}
int main()
{
	int n,p,p2;
	scanf("%d",&n);
	getInit(a,n);
	getInit(b,n);
	for(p=1;b[p]>b[p-1];p++);
	p2=p;
	for(;a[p]==b[p]&&p<n;p++);
	if(p==n)
	{
		printf("Insertion Sort\n");
		int Tmp=b[p2],i;
		for(i=p2;i>0&&b[i-1]>Tmp;i--)
		b[i]=b[i-1];
		b[i]=Tmp;
		Travers(b,n);
	}else{
		printf("Heap Sort\n");
		int c[n+1]={INF},time=n,parent,child;
		int *p=c+1;
		for(int i=1;i<=n;i++) c[i]=b[i-1];
		for(;c[time]>c[time-1];time--);
		swap(c[1],c[time]);
		int x=c[1];
		for(parent=1;parent*2<=time;parent=child)
		{
			child=parent*2;
			if(child!=time-1&&(c[child]<c[child+1])) child++;
			if(x>=c[child]) break;
			else c[parent]=c[child];	
		}
		c[child]=x;
		Travers(p,n);
	}
	return 0;
}