1098 Insertion or Heap Sort (25 分)

题目链接

插入排序与堆排序

注意：
1.插入排序可以用sort函数直接排了，速度很快。
2.比较两个数组是否相等可以用vector存，然后直接比对。
3.堆排序利用了左孩子与父节点2倍的关系，所以读入的时候从1开始存，比较方便。
4.堆向下调整的时候注意是不断递减，不是递增。

#include<bits/stdc++.h>
using namespace std;
vector<int> org(105,0),ans(105,0),tmp(105,0);
int n;
void show(vector<int> v){
	for(int i=1;i<=n;i++){
		if(i!=1) cout<<" ";
		cout<<v[i];
	}
}
bool insertSort(){
	bool flag=false;
	for(int i=2;i<=n;i++){
		if(i!=2 && tmp==ans){
			flag=true;
		}
		sort(tmp.begin()+1,tmp.begin()+i+1);
		if(flag){
			return true;
		}		
	}
	return false; 
}
void downAdjust(int low, int high){
	int i=low, j=2*i;
	while(j<=high){
		if(j+1<=high && tmp[j+1] > tmp[j]){
			j=j+1;
		}
		if(tmp[j] > tmp[i]){
			swap(tmp[j], tmp[i]);
			i = j;
			j = 2*i;
		}else break;
	}
}
void heapSort(){
	bool flag=false;
	for(int i = n/2; i >=1; i--){
		downAdjust(i,n); //建堆 
	}
	for(int i=n; i >1; i--){
		if(i!= n && tmp == ans){
			flag=true;
		}
		swap(tmp[i], tmp[1]); //交换heap[i]与堆顶
		downAdjust(1,i-1);//调整i前面的堆
		if(flag){
			show(tmp);
			return;
		} 
	} 
}
int main(){
	
	cin>>n;
	for(int i=1;i<=n;i++){ //为了堆排序 
		cin>>org[i];
		tmp[i] = org[i];
	}
	for(int i=1;i<=n;i++){
		cin>>ans[i];
	}
	if(insertSort()){
		cout<<"Insertion Sort"<<endl;
		show(tmp);
	}else{
		cout<<"Heap Sort"<<endl;
		tmp = org;
		heapSort();
	}
	return 0;
}