完整的堆排序内容;
其中给出了一个思路,就是对于插入排序,使用sort函数会快很多。。。这也算模拟经典排序的一种取巧方式
#include#include #include #include #include using namespace std;using std::vector;const int maxn=110;int n;int aim_quence[maxn];int heap[maxn];int input[maxn];int flag=0;bool isSame(int a[],int b[]){ for(int i=1;i<=n;i++){ if(a[i]!=b[i]) return false; } return true;}void insert_sort(){ for(int i=2;i<=n;i++){ sort(input+1,input+i+1); if(flag!=0) break; if(isSame(input,aim_quence)){ flag=1; } }}void downAdujst(int low,int high){ //插入时进行向下调整 int i=low; int j=2*i; while(j<=high){ //cout<<11< heap[i]){ swap(heap[j],heap[i]); i=j; j=i*2; }else{ break; } }}void heapSort(){ for(int i=n;i>1;i--){ swap(heap[i],heap[1]); downAdujst(1,i-1); if(flag!=0) break; if(isSame(heap,aim_quence)){ flag=2; } }}void create(){ for(int i=n/2;i>=1;i--){ downAdujst(i,n); }}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&input[i]); heap[i]=input[i]; } for(int i=1;i<=n;i++){ scanf("%d",&aim_quence[i]); } insert_sort(); create(); heapSort(); if(flag==1){ printf("Insertion Sort\n"); for(int i=1;i<=n;i++){ if(i==1) printf("%d",input[i]); else printf(" %d",input[i]); } }else if(flag==2){ printf("Heap Sort\n"); for(int i=1;i<=n;i++){ if(i==1) printf("%d",heap[i]); else printf(" %d",heap[i]); } } system("pause"); return 0;}