昨天的归并排序问题出在 插入排序写错了。今天改了改用在堆排序这道题上 test全过

堆排序详解http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621/

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int *arr,*s;
int isheap=0;
bool check() {
	for(int i=0; i<n; i++) {
		if(arr[i+1]!=s[i]) return false;
	}
	return true;
}
void insert_once(int a[],int n) {
	int op;
	for(int i=1; i!=n; i++)
		if(a[i-1]>a[i]) {
			op=i;
			break;
		}
	for(int j=op-1; j>=0&&a[j]>a[j+1]; j--)
		swap(a[j],a[j+1]);
	return ;
}
void HeapAdjust(int *a,int i,int size) { //调整堆
	int lchild=2*i;       //i的左孩子节点序号
	int rchild=2*i+1;     //i的右孩子节点序号
	int max=i;            //临时变量
	if(i<=size/2) {        //如果i不是叶节点就不用进行调整
		if(lchild<=size&&a[lchild]>a[max]) {
			max=lchild;
		}
		if(rchild<=size&&a[rchild]>a[max]) {
			max=rchild;
		}
		if(max!=i) {
			swap(a[i],a[max]);
			HeapAdjust(a,max,size);    //避免调整之后以max为父节点的子树不是堆
		}
	}
}

void BuildHeap(int *a,int size) {  //建立堆
	int i;
	for(i=size/2; i>=1; i--) { //非叶节点最大序号值为size/2
		HeapAdjust(a,i,size);
	}
}

void HeapSort(int *a,int size) {  //堆排序
	int i;
	BuildHeap(a,size);
	for(i=size; i>=1; i--) {
		if(check()) isheap=1;
		swap(a[1],a[i]);        //将余下元素重新建立为大顶堆
		HeapAdjust(a,1,i-1);      //重新调整堆顶节点成为大顶堆
		if(isheap==1) return;
	}
	if(check()) isheap=1;
}
int main(int argc, char** argv) {
	while(cin>>n) {
		isheap=0;
		int size=n;
		arr= new int[n+1];
		s  = new int[n+1];
		for(int i=1; i<=n; i++) {
			cin>>arr[i];
		}
		for(int i=0; i<n; i++) {
			cin>>s[i];
			tmp[i]=s[i];
		}
		HeapSort(arr,size);
		if(isheap == 1) {
			cout<<"Heap Sort"<<endl;
			for(int i=1; i<n; i++) {
				cout<<arr[i]<<" ";
			}
			cout<<arr[n]<<endl;
		} else {
			cout<<"Insertion Sort"<<endl;
			insert_once(s,n);
			for(int i=0; i<n-1; i++) {
				cout<<s[i]<<" ";
			}
			cout<<s[n-1]<<endl;
		}
		delete arr,s;
	}
	return 0;
}

632 total views, no views today