标签：桶排

写在前面 为什么说这两个是非常规排序，第一个是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速度终究还是快不过归并，桶排的内存就很感人了… ]]>