列排序【C++】

列排序【C++】

时间: 2ms        内存:128M

描述:

对一组纪录按任意指定列排序。现请你编写程序实现该功能。已给定类部分代码,不可删除和修改已有代码,只可以扩充。

输入:

测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (<=100000) 和 C,其中 N 是纪录的条数,C 是指定排序的列号。以下有 N行,每行包含一条学生纪录。每条学生纪录由学号(6位数字,同组测试中没有重复的学号)、姓名(不超过8位且不包含空格的字符串)、成绩(闭区间[0, 100]内的整数)组成,每个项目间用1个空格隔开。当读到 N=0 时,全部输入结束,相应的结果不要输出。

输出:

对每个测试用例,首先输出1行“Case i:”,其中 i 是测试用例的编号(从1开始)。随后在 N 行中输出按要求排序后的结果,即:当 C=1 时,按学号递增排序;当 C=2时,按姓名的非递减字典序排序;当 C=3时,按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时,则按他们的学号递增排序。

示例输入:

3 1 
000007 James 85 
000010 Amy 90 
000001 Zoe 60 
4 2 
000007 James 85 
000010 Amy 90 
000001 Zoe 60 
000002 James 98 
4 3 
000007 James 85 
000010 Amy 90 
000001 Zoe 60 
000002 James 90 
0 0

示例输出:

Case 1:
000001 Zoe 60
000007 James 85
000010 Amy 90
Case 2:
000010 Amy 90
000002 James 98
000007 James 85
000001 Zoe 60
Case 3:
000001 Zoe 60
000007 James 85
000002 James 90
000010 Amy 90

提示:

参考答案(内存最优[1216]):

#include<stdio.h>
#include<string.h>
struct x
{
	char num[99],name[99];
	int score;
};
void f1(int n)
{
	struct x st[n],t;
	int i,j;
	for(i=0;i<n;i++)
	scanf("%s %s %d",st[i].num,st[i].name,&st[i].score);
	for(i=0;i<n;i++)
	for(j=0;j<n-i-1;j++)
	{
		if(strcmp(st[j].num,st[j+1].num)>0)
		{
			t=st[j];
			st[j]=st[j+1];
			st[j+1]=t;
		}
	}
	printf("Case 1:\n");
	for(i=0;i<n;i++)
	printf("%s %s %d\n",st[i].num,st[i].name,st[i].score);
}
void f2(int n)
{
	struct x st[n],t;
	int i,j;
	for(i=0;i<n;i++)
	scanf("%s %s %d",st[i].num,st[i].name,&st[i].score);
	for(i=0;i<n;i++)
	for(j=0;j<n-i-1;j++)
	{
		if(strcmp(st[j].name,st[j+1].name)>0)
		{
			t=st[j];
			st[j]=st[j+1];
			st[j+1]=t;
		}
		else if(strcmp(st[j].name,st[j+1].name)==0)
		{
			if(strcmp(st[j].num,st[j+1].num)>0)
			{
			t=st[j];
			st[j]=st[j+1];
			st[j+1]=t;
		    }
		}
	}
	printf("Case 2:\n");
	for(i=0;i<n;i++)
	printf("%s %s %d\n",st[i].num,st[i].name,st[i].score);
}
void f3(int n)
{
	struct x st[n],t;
	int i,j;
	for(i=0;i<n;i++)
	scanf("%s %s %d",st[i].num,st[i].name,&st[i].score);
	for(i=0;i<n;i++)
	for(j=0;j<n-i-1;j++)
	{
		if(st[j].score>st[j+1].score)
		{
			t=st[j];
			st[j]=st[j+1];
			st[j+1]=t;
		}
		else if(st[j].score==st[j+1].score)
		{
			if(strcmp(st[j].num,st[j+1].num)>0)
			{
			t=st[j];
			st[j]=st[j+1];
			st[j+1]=t;
		    }
		}
	}
	printf("Case 3:\n");
	for(i=0;i<n;i++)
	printf("%s %s %d\n",st[i].num,st[i].name,st[i].score);
}
int main()
{
    int n,x;
    while(scanf("%d%d",&n,&x))
    {
    	if(n==0&&x==0)
    	break;
    	if(x==1)
    	f1(n);
    	if(x==2)
    	f2(n);
    	if(x==3)
    	f3(n);
    }
} 

参考答案(时间最优[0]):

#include <iostream>
#include <string>

using namespace std;

class colSort
{

public:

    enum {MAXREC=100000};

    string no[MAXREC];

    string name[MAXREC];

    int score[MAXREC];

    int recnum; //记录数目

public:

    void sort(int index);

    //index =1,2,3; 按第index列排序


};

void colSort::sort(int index)
{
    int i,j,sc;
    string str,na;
    if(index==1)
    {
        for(j=0; j<=recnum; j++)
        {
            for(i=0; i<recnum-j-1; i++)
            {
                if(no[i]>no[i+1])
                {
                    str=no[i];
                    no[i]=no[i+1];
                    no[i+1]=str;

                    na=name[i];
                    name[i]=name[i+1];
                    name[i+1]=na;

                    sc=score[i];
                    score[i]=score[i+1];
                    score[i+1]=sc;
                }
            }
        }
    }

    else if(index==2)
    {
        for(j=0; j<=recnum; j++)
        {
            for(i=0; i<recnum-j-1; i++)
            {
                if(name[i]>name[i+1])
                {

                        str=no[i];
                        no[i]=no[i+1];
                        no[i+1]=str;

                        na=name[i];
                        name[i]=name[i+1];
                        name[i+1]=na;

                        sc=score[i];
                        score[i]=score[i+1];
                        score[i+1]=sc;

                }
                else if(name[i]==name[i+1])
                {
                    if(no[i]>no[i+1])
                    {

                            str=no[i];
                            no[i]=no[i+1];
                            no[i+1]=str;

                            na=name[i];
                            name[i]=name[i+1];
                            name[i+1]=na;

                            sc=score[i];
                            score[i]=score[i+1];
                            score[i+1]=sc;

                    }
                }
            }
        }
    }

    else if(index==3)
    {
        for(j=0; j<=recnum; j++)
        {
            for(i=0; i<recnum-j-1; i++)
            {
                if(score[i]>score[i+1])
                {

                        str=no[i];
                        no[i]=no[i+1];
                        no[i+1]=str;

                        na=name[i];
                        name[i]=name[i+1];
                        name[i+1]=na;

                        sc=score[i];
                        score[i]=score[i+1];
                        score[i+1]=sc;

                }
                else if(score[i]==score[i+1])
                {
                    if(no[i]>no[i+1])
                    {

                            str=no[i];
                            no[i]=no[i+1];
                            no[i+1]=str;

                            na=name[i];
                            name[i]=name[i+1];
                            name[i+1]=na;

                            sc=score[i];
                            score[i]=score[i+1];
                            score[i+1]=sc;

                    }
                }
            }
        }
    }

}

int main()
{
    int n,c,t,i;
    colSort demo;
    t=1;
    while(cin>>n>>c&&n!=0&&c!=0)
    {
        demo.recnum=n;
        for(i=0;i<n;i++)
        {
            cin>>demo.no[i]>>demo.name[i]>>demo.score[i];
        }
        demo.sort(c);

        cout<<"Case "<<t<<":"<<endl;
        for(i=0;i<n;i++)
            cout<<demo.no[i]<<" "<<demo.name[i]<<" "<<demo.score[i]<<endl;
        t++;

    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注