A1098 Insertion or Heap Sort (25)与1089题型类似（重点******）

掌握堆排序的含义以及写法，关于排序题需要再整理一下 易错点，是关于insert排序的时候，应该是a[i]<=b[i]; 写法一：

#include<cstdio> #include<algorithm> using namespace std; const int maxn=101; int origin[maxn],a[maxn],b[maxn]; void downAdjust(int A[],int low,int high) { int i=low,j=i*2; while(j<=high) { if(j+1<=high&&A[j+1]>A[j]) j=j+1; if(A[j]>A[i]) { swap(A[j],A[i]); i=j; j=i*2; } else break; } } bool isSame(int A[],int B[],int n) { for(int i=1;i<=n;i++) { if(A[i]!=B[i]) return false; } return true; } void heap(int n) { int i; for( i=n/2;i>=1;i--) downAdjust(b,i,n); for(i=n;i>1;i--) { if(i!=n&&isSame(b,a,n)) break; swap(b[i],b[1]); downAdjust(b,1,i-1); } swap(b[i],b[1]); downAdjust(b,1,i-1); } int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&origin[i]); b[i]=origin[i]; } for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;a[i]<a[i+1]&&i<n;i++); for(j=i+1;a[j]==origin[j]&&j<=n;j++); if(j==n+1) { printf("Insertion Sort\n"); sort(b+1,b+i+2); } else { printf("Heap Sort\n"); heap(n); } for(i=1;i<=n;i++) { printf("%d",b[i]); if(i!=n) printf(" "); } }

写法二：

#include<cstdio> #include<algorithm> using namespace std; const int maxn=110; int origin[maxn],a[maxn],b[maxn]; void downAdjust(int A[],int low,int high) { int i=low,j=i*2; while(j<=high) { if(j+1<=high&&A[j+1]>A[j]) j=j+1; if(A[j]>A[i]) { swap(A[j],A[i]); i=j; j=i*2; } else break; } } int main() { int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&origin[i]); b[i]=origin[i]; } for(i=1;i<=n;i++) scanf("%d",&a[i]); for(i=1;a[i]<=a[i+1]&&i<n;i++); for(j=i+1;a[j]==origin[j]&&j<=n;j++); if(j==n+1) { printf("Insertion Sort\n"); sort(a+1,a+i+2); } else { printf("Heap Sort\n"); j=n; while(j>=2&&a[j]>=a[1])j--; swap(a[1],a[j]); downAdjust(a,1,j-1); } for(i=1;i<=n;i++) { printf("%d",a[i]); if(i!=n) printf(" "); } }