|
計(jì)算名次與按名次排序問(wèn)題的算法優(yōu)化 (c/c++)
之前寫(xiě)過(guò)這個(gè)小算法，也沒(méi)有在意，只是用for循環(huán)來(lái)一個(gè)個(gè)的比較。后來(lái)才覺(jué)得這在數(shù)據(jù)量很大的情況下會(huì)產(chǎn)生很多額外的開(kāi)銷。因此進(jìn)行了優(yōu)化。
計(jì)算名次：進(jìn)行最少次數(shù)的比較。 template <class T> void Rank(T a[],int n,int r[]) { for(int i=1,i<n;i++) r[i]=0; for(int i=1;i<n;i++) for(int j=1;j<i;j++) if(a[j]<=a[i])r[i]++; else r[j]++; } 按名次進(jìn)行排序： 移動(dòng)次數(shù)為2n,申請(qǐng)一個(gè)額外的數(shù)組的算法 template <class T> void Rearrange(T a[],int n,int r[]) { T *u=new T[n+1]; for(int i=1;i<n;i++) u[r[i]]=a[i]; for(int i=1;i<n;i++) a[i]=u[i]; delete u[]; } 另外一個(gè)移動(dòng)次數(shù)為n的算法： template <class T> void Rearrange(T a[],int n,int r[]) { for(int i=0;i<n;i++) { while(r[i]!=i) { int t=r[i]; Swap(a[i],a[t]); Swap(r[i],r[t]); } } } Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1591485 |
|
|
