一路关于成绩排名的编程题目，求指导，表示看不懂他的算法

一道关于成绩排名的编程题目，求指导，表示看不懂他的算法
#include<iostream>
using namespace std;
void ranking(int a[],int b[]);
int main(void)
{
int a[101],b[101],i,n;
cout<<"请输入参赛选手的人数:"<<endl; 
cin>>n;
a[0]=b[0]=n;
cout<<"请输入"<<n<<"个选手的成绩:"<<endl;
for(i=1;i<=n;i++)
{
cin>>a[i];
b[i]=0;
}
ranking(a,b);
cout<<n<<"个选手的成绩和名次依次为:"<<endl;
for(i=1;i<=n;i++)
cout<<a[i]<<" "<<b[i]<<endl;
return 0;
}
void ranking(int a[],int b[])
{
int t[101];
int i,j,k,n,max,rank;
n=a[0];
for(i=1;i<=n;i++)
b[i]=0;
rank=1;
i=1;
while(i<=n)
{
if (b[i]==0)
{
max=a[i];
k=1;
t[k]=i;
for(j=i+1;j<=n;j++)
{
if (b[j]==0&&a[j]>=max)
{
if(a[j]>max)
{
max=a[j];
k=0;
}
k=k+1;
t[k]=j;
}
}
for(j=1;j<=k;j++)
b[t[j]]=rank;
rank=rank+k;
continue;
}
i++;
}
}
编程
[解决办法]
先帮忙把代码格式化下吧：

#include<iostream>
using namespace std;
void ranking(int a[],int b[]);
int main(void)
{
    int a[101],b[101],i,n;
    cout<<"请输入参赛选手的人数:"<<endl;
    cin>>n;
    a[0]=b[0]=n;
    cout<<"请输入"<<n<<"个选手的成绩:"<<endl;
    for(i=1; i<=n; i++)
    {
        cin>>a[i];
        b[i]=0;
    }
    ranking(a,b);
    cout<<n<<"个选手的成绩和名次依次为:"<<endl;
    for(i=1; i<=n; i++)
        cout<<a[i]<<" "<<b[i]<<endl;
    return 0;
}
void ranking(int a[],int b[]) 
 
{
    int t[101];
    int i,j,k,n,max,rank;
    n=a[0];
    for(i=1; i<=n; i++)
        b[i]=0;
    rank=1;
    i=1;
    while(i<=n)
    {
        if (b[i]==0)
        {
            max=a[i];
            k=1;
            t[k]=i;
            for(j=i+1; j<=n; j++)
            {
                if (b[j]==0&&a[j]>=max)
                {
                    if(a[j]>max)
                    {
                        max=a[j];
                        k=0;
                    }
                    k=k+1;
                    t[k]=j;
                }
            }
            for(j=1; j<=k; j++)
                b[t[j]]=rank;
            rank=rank+k;
            continue;
        }
        i++;
    }
}

------解决方案--------------------

说实话，我看了几分钟代码确实也没看太明白……但这不就是简单的排序么，只需要在排序过程中记住各个数在已排序结果中的下标就OK了，废话不多说了，直接用计数排序

void ranking(int a[],int b[])
{
    int iNum = a[0];
    //找到最高分
    int maxHigh=0;
    for(int i =1; i <= iNum; ++i){
        if(a[i] > maxHigh)
            maxHigh = a[i];
    }
    //利用计数排序
    int *C = new int[1+maxHigh];
    for(int i =0; i <= maxHigh; ++i){
        C[i] = 0;
    }
    for(int i =1; i <= iNum; ++i){
        ++C[a[i]];
    }
    for(int i = 0; i < maxHigh; ++i){
        C[i+1] += C[i];
    }
    //开始保存名次
    for(int i =1; i <= iNum; ++i){
        b[i] = iNum + 1 - (C[a[i]]--);
    }

}

[解决办法]
没仔细看楼主的排序代码，似乎是按照索引用选择排序，觉得这个排序实现方法不太好。
用简单而更效率的插入排序，注意比较的时候用原数组（注意下标不是简单的i,j，而是idx[i] idx[j]），交换数据的时候交换索引数组即可。

写了个索引插入排序的函数，其中arr是原数组，idx是索引，要求初始idx中的值是0--n-1,对应arr的下标。
楼主可参考，并修改成适合题目中下标从1开始的。

void sortidx(const int* arr, int* idx, int n)
{
int i, j, temp;
for (i = 1; i < n; i++)
{
temp = idx[i];
for (j = i - 1; j >= 0; j--)
{
if (arr[temp] < arr[idx[j]])
idx[j + 1] = idx[j];
else
break;
}
idx[j + 1] = temp;
}
}

[解决办法]

引用:

Quote: 引用:

没仔细看楼主的排序代码，似乎是按照索引用:

没仔细看楼主的排序代码，似乎是按照索引用选择排序，觉得这个排序实现方法不太好。
用简单而更效率的插入排序，注意比较的时候用原数组（注意下标不是简单的i,j，而是idx[i] idx[j]），交换数据的时候交换索引数组即可。

写了个索引插入排序的函数，其中arr是原数组，idx是索引，要求初始idx中的值是0--n-1,对应arr的下标。
楼主可参考，并修改成适合题目中下标从1开始的。

void sortidx(const int* arr, int* idx, int n) 
 
{
int i, j, temp;
for (i = 1; i < n; i++)
{
temp = idx[i];
for (j = i - 1; j >= 0; j--)
{
if (arr[temp] < arr[idx[j]])
idx[j + 1] = idx[j];
else
break;
}
idx[j + 1] = temp;
}
}

大神，表示看不懂呀，呃，能把原理说清楚点吗？排序呀？好像有点不明白里面是怎么搞得

插入排序呀
这里只不过比普通的插入排序多转了个弯，比较大小的时候用原数组，排序交换位置是针对索引数组的。
这个排序函数执行之后，arr数组的内容是不变的，idx索引数组中是排好序的下标。
比如idx[0]的值是4，那就是arr[4]是最小的，idx[1]的值是1，那么arr[1]的值是第二小的。以此类推。
对于你这个题目，还需要统计名次，在开一个rank的数组，for循环遍历idx数组，rank[idx[i]] = i+1就完成了名次统计（这里假定for循环是从0开始的）

查看更多 下一篇