计算名次与按名次排序问题的算法优化

 计算名次与按名次排序问题的算法优化

(c/c++)

之前写过这个小算法，也没有在意，只是用for循环来一个个的比较。后来才觉得这在数据量很大的情况下会产生很多额外的开销。因此进行了优化。

计算名次：进行最少次数的比较。

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]++;

}

按名次进行排序：

移动次数为2n,申请一个额外的数组的算法

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[];

}

另外一个移动次数为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