1098. Insertion or Heap Sort (25)

​ 时间限制

​ 100 ms

​ 内存限制

​ 65536 kB

​ 代码长度限制

​ 16000 B

​ 判题程序

​ Standard

​ 作者

​ CHEN, Yue

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (<=100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Heap Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

Sample Output 1:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

Sample Input 2:

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

Sample Output 2:

Heap Sort
5 4 3 1 0 2 6 7 8 9

堆排序与插入排序

判断是否为堆排序还是插入排序可根据插入排序的特性，插入排序必定是前面有序，后面与源列表一致

注意点：在进行判断时，不要以为没有相同值，我就被坑的好惨。。。。委屈，所以在定位时要考虑这一点

堆排序，首先将首位与未排序的最后一位交换，再调整为大顶堆即可

void heap_sort(int root,int n,elementype a[]){
  int father,child;
  for(father=root;(father*2+1)<n;father=child){
    child=father*2+1;//由于从0开始所以左孩子为2*+1
    if(child!=n-1&&a[child]<a[child+1]) ++child;  //选较大的孩子
    if(a[father]<a[child]) swap(a[father],a[child]);
    else break;
  }
}

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a,b;

void heap_sort(int root,int n){
	int father,child;
	for(father=root;(father*2+1)<n;father=child){
		child=father*2+1;
		if(child!=n-1&&b[child]<b[child+1]) ++child;
		if(b[father]<b[child]) swap(b[father],b[child]);
		else break;
	}
}

int main(){
	int n;
	scanf("%d",&n);
	a.resize(n);
	b.resize(n);
	for(int i=0;i<n;++i){
		scanf("%d",&a[i]);
	}
	for(int i=0;i<n;++i){
		scanf("%d",&b[i]);
	}
	int p=1;
	while(p<n&&b[p-1]<=b[p])++p;
	int index=p;
	while(p<n&&a[p]==b[p])++p;
	if(p==n){
		printf("Insertion Sort\n");
		sort(b.begin(),b.begin()+index+1);
		printf("%d",b[0]);
		for(int i=1;i<n;++i){
			printf(" %d",b[i]);
		}
	}else{
		printf("Heap Sort\n");
		p=n-1;
		while(b[0]<b[p]&&p>=1)--p;
		swap(b[0],b[p]);
		heap_sort(0,p);
		printf("%d",b[0]);
		for(int i=1;i<n;++i){
			printf(" %d",b[i]);
		}
	}
}