快速排序
scturtle
posted @ 2012年2月21日 12:38
in algorithm
, 1869 阅读
#include <cstdio> #include <cstdlib> #include <ctime> void swap(int &x, int &y) { int t=x; x=y; y=t; } void check(int t[],int n) { bool res=true; for(int i=0;res && i<n-1;i++) if(t[i]>t[i+1]) res=false; if(res) puts("Yes"); else { puts("No"); for(int i=0;i<n;i++) printf("%d ",t[i]); puts(""); } } ////////////////////////////////////////////////////// int partation(int a[], int l, int r,int pi) { swap(a[r],a[pi]); int p=a[r],here=l,j; for(j=l;j<r;j++) if(a[j]<p) swap(a[here++],a[j]); swap(a[here],a[r]); return here; } void qsort1(int a[], int l, int r) { if(l>=r) return; int p=partation(a,l,r,(l+r)/2); qsort1(a,l,p-1); qsort1(a,p+1,r); } ////////////////////////////////////////////////////// void qsort2(int a[],int l,int r) { if(l>=r) return; int p=a[l],i=l,j=r+1; while(1) { while(a[++i]<p); while(a[--j]>p); if(i>=j) break; swap(a[i],a[j]); } swap(a[j],a[l]); qsort2(a,l,j-1); qsort2(a,j+1,r); } ////////////////////////////////////////////////////// void qsort3(int a[],int l,int r) { if(l>=r) return; int i=l-1,j=r+1,p=a[(l+r)/2]; while(1) { while(a[++i]<p); while(a[--j]>p); if(i>j) break; swap(a[i],a[j]); } qsort3(a,l,j); qsort3(a,i,r); } ////////////////////////////////////////////////////// const int n=10000; int t[n]; int main() { freopen("out","w",stdout); srand(time(NULL)); for(int i=0;i<n;i++) t[i]=1+rand()%1000; qsort3(t,0,n-1); check(t,n); return 0; }
2022年9月22日 01:37
Department of School Education, Andhra Pradesh and Various Private & Government School Subject Experts and Teaching Staff have suggested the Practice Model Question Bank for All Languages & Subjects of the Course based on the SCERT & NCERT Syllabus. AP Board Question Paper Pdf Download Department of School Education, Andhra Pradesh and Various Private & Government School Subject Experts and Teaching Staff have suggested the Practice Model Question Bank for All Languages & Subjects of the Course based on the SCERT & NCERT Syllabus.