根据一结构中的一个数据对整个结构进行排序.解决方案

根据一结构中的一个数据对整个结构进行排序...
比如
struct num{
int a;
int b;
}
struct num group[50000];
根据a对结构数组排序，不管b的大小;
有没有比较快的。。。
我的菜鸟代码超时了。。。[code=C/C++][/code]

#include<stdio.h>
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void main()
{
struct num{
int a;
int b;
};
struct num grp[50000];
int n,i=0,j,k,l;
scanf("%d",&n);
while(i<n){
scanf("%d%d",&grp[i].a,&grp[i].b);
i++;
}
for(j=0;j<n;j++)
{
for(k=j+1;k<n;k++)
{
if(grp[k].a<grp[j].a)
{
swap(&grp[k].a,&grp[j].a);
swap(&grp[k].b,&grp[j].b);
}
}
}
int min,max;
for(l=0,min=grp[l].a,max=grp[l].b;l<n;l++)
{
if(max>=grp[l].a){
max=(max>grp[l].b)?max:grp[l].b;
}else{
printf("%d %d\n",min,max);
min=grp[l].a;
max=grp[l].b;
}
if(l==n-1){
printf("%d %d\n",min,max);
return;
}
}

}
这是一个对输入的区间取并然后升序输出的题目。。。谢谢各位了。。。

------解决方案--------------------
NAME
qsort - sorts an array

SYNOPSIS
#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
int(*compar)(const void *, const void *));
------解决方案--------------------
任何nlogn的算法都足够.
希尔,堆,快排,等
甚至还可以桶排序,毫无压力
------解决方案--------------------
快速排序，堆排序

C/C++ code


#include<stdio.h>
#include<stdlib.h>


struct num
{
    int a;
    int b;
};

int cmp(const void *aa, const void *bb)
{
    return (*(struct num *)aa).a-(*(struct num *)bb).a?1:-1;
}

void main()
{

    struct num grp[50000];
    int n,i=0,j,k,l;
    scanf("%d",&n);
    while(i<n)
    {
        scanf("%d%d",&grp[i].a,&grp[i].b);
        i++;
    }

    qsort(grp, n, sizeof(grp[0]), cmp);  //用C库中自带的qsort
    
    int min,max;
    for(l=0,min=grp[l].a,max=grp[l].b;l<n;l++)
    {
        if(max>=grp[l].a)
        {
            max=(max>grp[l].b)?max:grp[l].b;
        }
        else
        {
            printf("%d %d\n",min,max);
            min=grp[l].a;
            max=grp[l].b;
        }
        if(l==n-1)
        {
            printf("%d %d\n",min,max);
            return;
        }
    }
    
}

根据一结构中的一个数据对整个结构进行排序.解决方案

相关推荐