分类
OI

排序算法(2) — 非常规排序 — sort/桶排

写在前面 为什么说这两个是非常规排序,第一个是stl库,第二个是真的暴力出奇迹233

sort

理论最优时间复杂度: O(n log2(n)) 因为这个东西忘记了所有排序的人估计不止我一个
sort(start,end,cmp);
此函数位于algorithm库中
  • start 开始排序的位置<必选项>
  • end 结束排序的位置<必选项>
  • cmp() 排序的优先级实际上如果要用优先队列你还会见到他<可选项,不填写的话就是升序排列啦>

示例


这个东西真的是超级好用的,吹暴sort!!! 数组排序<升序>:
sort(a,a+n)// 从a[0]到a[n-1]
数组排序<降序>:
bool cmp(int c,int d){
    return c>d;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&a[i]);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) printf("%d",a[i]);
}
相比你们也已经猜到了结构体排序的方法:
bool cmp(node c,node d){
    if(c.a>d.a) return true;
    else if(c.b>d.b) return true;
    else return false;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d%d",&a[i].a,&a[i].b);
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++) printf("%d %d\n",a[i].a,a[i].b);
}
所以说这玩意这么好为什么还要用别的呢对吧 如果你想验证一下自己是否学会sort可以试试这道题:[https://www.luogu.org/problemnew/show/P1093]

桶排

时间复杂度:O(max)(max是指数列中间的最大值) 空间复杂度:常数级别 不知道大伙还记不记得在bfs时我们所打的哈希表,桶排与这个东西神似 不知道也没关系 我们想一下,我们打一张表,出现过得数字为true,没有出现过的为false,然后从头遍历,这真的一点都不常规排序…… 伪代码:
    for(int i=1;i<=n;i++){
        scanf("%d",&temp);
        if(temp>max) max=temp;
        x[temp]++;
    }
    for(int i=1;i<=max;i++) {
        for(int j=1;j<=x[i];j++){
            printf("%d ",i);
        }
    }
皮到一个境界2333

End

总而言之,这篇讲的两个不常规排序并不需要理解方法,并且时间复杂度真的是一低再低了233,可谓是简单粗暴还省时,不过缺陷也是有的啦,sort速度终究还是快不过归并,桶排的内存就很感人了… ]]>

“排序算法(2) — 非常规排序 — sort/桶排”上的2条回复

发表评论

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