分析：排序算法很基础的练手题，堆排的思想是要先建堆然后逐渐删除堆顶元素并向下调整。

#include<iostream>
#include<cstdio>
using namespace std;
int seq[110], cop[110], res[110], flag;
int judge(int n){
	for(int i = 0; i<n; i++){
		if(seq[i] != res[i]) return 0;
	}
	return 1;
}
int insertSort(int n){
	for(int i = 1; i<n; i++){
		int j = i-1, tem = seq[i];
		while(j>=0 && seq[j] > tem) {
			seq[j+1] = seq[j];
			j--;
		}
		seq[j+1] = tem;
		if(flag) return 1;
		if(judge(n)) flag = 1;
	}
	return 0;
}
void adjustDown(int k, int len){
	int tem = seq[k];
	for(int i = k*2+1; i<len; i=2*i+1){
		if(i+1 < len && seq[i+1] > seq[i]) i++;
		if(tem >= seq[i]) break;
		seq[k] = seq[i];
		k = i;
	}
	seq[k] = tem;
}
void buildHeap(int len){
	//完全二叉树的编号从0开始，因此初始建堆从最后一个非叶子结点开始 
	for(int i = len/2-1; i>=0; i--){
		adjustDown(i, len);
	}
}
int heapSort(int n){
	buildHeap(n);
	for(int i = n-1; i>=1; i--){
		swap(seq[0], seq[i]); //把当前的最大值换到末尾 
		adjustDown(0, i); //从根节点开始对剩余结点向下调整 
		if(flag) return 1;
		if(judge(n)) flag = 1;
	}
	return 0;
}
int main(){
	//freopen("aa.txt", "r", stdin);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i = 0; i<n; i++){
		cin >> seq[i];
		cop[i] = seq[i];
	}
	for(int i = 0; i<n; i++){
		cin >> res[i];
	}
	if(insertSort(n)){
		cout << "Insertion Sort\n";
	} else {
		for(int i = 0; i<n; i++){
			seq[i] = cop[i];
		}
		if(heapSort(n)){
			cout << "Heap Sort\n";
		}
	}
	for(int i = 0; i<n; i++){
		cout << seq[i];
		i != n-1 ? cout << " " : cout << "\n";
	}
	return 0;
} 复制