qsort 与 sort

回复帖子

@Thecats  2017-05-26 17:16 回复

本来一直都用sort的 但是有一天突然发现qsort在洛谷上运行比sort快好多 而且两个题目都有这样的倾向qwq

R2256688 qsort()

魔法照片 Accepted

100 代码 C++11,0.8kB

提交时间 2017-05-25 17:58:50

耗时/内存 63ms , 12187kb

R2256624 sort()

魔法照片 Accepted

100 代码 C++11,0.6kB

提交时间 2017-05-25 17:51:15

耗时/内存143ms , 12039kb

R2258606 qsort()

瑞士轮 Unaccepted

80 8A2T

代码 C++11,0.9kB

提交时间 2017-05-25 21:59:38

耗时/内存 2027ms , 16460kb

R2261382 sort()

瑞士轮 Unaccepted

60 6A4T

代码 C++11,0.9kB

提交时间 2017-05-26 17:06:37

耗时/内存 908ms , 14175kb

然后百度感觉大家都说sort比qsort快。。。 and 也有qsort更快的qwq

是STL的锅??

求解耶qwq

ps:如果需要我把代码贴出来w

谢谢谢谢❤

@Thecats  2017-05-27 11:57 回复 举报
sort() 6A4T 
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<sstream>
#include<queue>
using namespace std;
int N,R,Q;
struct LZL{
    int c,s,w;
}X[200005];
int cmp(LZL a,LZL b)
{
    if(a.s<b.s)  return 0;
    if(a.s>b.s)  return 1;
    if(a.c<b.c)  return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d",&N,&R,&Q);
    N*=2;
    for(int i=1;i<=N;i++)  scanf("%d",&X[i].s),X[i].c=i;
    for(int i=1;i<=N;i++)  scanf("%d",&X[i].w);
    while(R--){
        sort(X+1,X+1+N,cmp);
        /*for(int i=1;i<=N;i++){
            cout<<"("<<X[i].c<<"-"<<X[i].s<<") ";
        }*/
        for(int i=1;i<=N;i+=2){
            if(X[i].w>X[i+1].w)  X[i].s++;
            else X[i+1].s++;
        }
        //puts("");
    }
    sort(X+1,X+1+N,cmp);
    printf("%d\n",X[Q].c);
    return 0;
}
@Thecats  2017-05-27 23:02 回复 举报
qsort() 8A2T
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<sstream>
#include<queue>
using namespace std;
int N,R,Q;
struct LZL{
    int c,s,w;
}X[200005];
int cmp(const void *a,const void *b)
{
    if((*(LZL *)a).s<(*(LZL *)b).s)  return 1;
    if((*(LZL *)a).s>(*(LZL *)b).s)  return -1;
    if((*(LZL *)a).c<(*(LZL *)b).c)  return -1;
    return 1;
}
int main()
{
    scanf("%d%d%d",&N,&R,&Q);
    N*=2;
    for(int i=1;i<=N;i++)  scanf("%d",&X[i].s),X[i].c=i;
    for(int i=1;i<=N;i++)  scanf("%d",&X[i].w);
    while(R--){
        qsort(X+1,N,sizeof(X[0]),cmp);
        /*for(int i=1;i<=N;i++){
            cout<<"("<<X[i].c<<"-"<<X[i].s<<") ";
        }*/
        for(int i=1;i<=N;i+=2){
            if(X[i].w>X[i+1].w)  X[i].s++;
            else X[i+1].s++;
        }
        //puts("");
    }
    qsort(X+1,N,sizeof(X[0]),cmp);
    printf("%d\n",X[Q].c);
    return 0;
}
@引领天下  2017-05-28 07:17 回复 举报

@Thecats

尴尬

sort不是只用bool吗……

是不是跟cmp函数类型有关系

还有你如果想这样A的话加个读入优化试试

代码:

int read(){
     char c=getchar();
     int x=0;
     while (c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
     return x;
}

然后你qsort的cmp有返回值-1是怎么会是?

是不是这句加快了排序速度?

你把改到sort里试试

@Thecats  2017-05-28 12:56 回复 举报

sort用bool int都可以

qsort排序规则是<0放前面 >0放后面w

@CommonAnts 2017-06-12 15:24 回复 举报

二者算法不同。qsort是快速排序,sort是内省排序(快速排序递归一定深度后转堆排序)。对于没有卡qsort的序列,qsort的常数确实小一些。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。