|
計(jì)算名次與按名次排序問題的算法優(yōu)化 (c/c++)
之前寫過這個小算法，也沒有在意，只是用for循環(huán)來一個個的比較。后來才覺得這在數(shù)據(jù)量很大的情況下會產(chǎn)生很多額外的開銷。因此進(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)行排序： 移動次數(shù)為2n,申請一個額外的數(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[]; } 另外一個移動次數(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 |
|
|
