模板：排序（三）

╰半橙微兮° 2021-12-23 09:27 148阅读 0赞

# 快速排序 #

## 手写代码 ##

从这里开始就是真正的考验了。  
这个厂子全是工业大户的订单，他们非常狂躁，因此需要较快的时间出货，而且为了压缩成本，你也不能买太多的桶。

勇者将刚才写的所有魔法代码全部试了一下，发现全部TLE，然而用桶排序的话会MLE。  
“……”勇者累得说不出话来。  
“不要急躁吗，其实我从照相馆那里借了点书过来，说不定就有你想要的哦！”  
勇者翻开了书，上面写了神奇的魔法。  
**快速排序，O(NlogN)**  
*注：这个是从小到大排的……大（其）家（实）自（是）己（我）写（懒）一（的）下（写）从（了）大（而）到（已）小（啊）的（蛤）吧（蛤）！*

#include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace std;
    int n,a[100001];
    void qsort(int l,int r){
        if(l>=r)return;
        else{
            int i=l,j=r;
            int mid=a[(l+r)/2];
            do{
                while(a[i]<mid){
         //从左到右找比中间数大的 
                    i++;
                } 
                while(a[j]>mid){
         //从右到左找比中间数小的 
                    j--;
                }
                if(i<=j){
                    int temp=a[i];//交换a【i】a【j】 
                    a[i]=a[j];//使l~j都是小数 
                    a[j]=temp;//i~r都是大数 
                    i++;j--;//继续找（同时防止死循环） 
                }
            }while(i<=j);
            qsort(l,j);
            qsort(i,r);
        }
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        qsort(1,n);
        for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        return 0;
    }

## 解释 ##

“**快速排序采用了二分的想法，选取一个基准点，保证前面的数字全部小于它。后面的数字全部大于它，指针一个从前往后，一个从后往前，遇到不符合上述标准的话（除非左指针在右指针右面了），就交换这两个数，然后以交换的数为基准递归即可**……”  
勇者将上述代码改了改，交了上去，然后AC了。  
“然而，c++自带一个函数默认从小到大排序……”

## c++自带函数sort ##

### 代码 ###

#include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace std;
    int main(){
        int n,a[100];
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        sort(a+1,a+n+1); 
        for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        return 0;
    }

“……”勇者石化中。  
————————————

### 函数sort的扩展 ###

第四个厂子，客户还是那些客户，不过他们的要求有点怪异。  
他们的要求不只是钢材的长短，还有粗细。  
以长短为第一关键字，粗细为第二关键字，从大到小排一下。

“虽然手写快排可以完成这个……但是人家实在不想写手写怎么办！”勇者抱怨到。  
“别着急，我们还有神奇的cmp呢！”  
首先我们先用cmp解决一下如何实现从大到小排序吧！

bool cmp(int a,int b){
        if(a>b)return 1;
        return 0;
    }

很容易理解吧。  
那么我们开始关键字排序的cmp吧。  
这里面为了方便sort排序于是用到了高深的结构体

struct ha{
        int l,s;
    }a[100];
    bool cmp(ha a,ha b){
        if(a.l>b.l)return 1;
        if(a.l<b.l)return 0;
        if(a.s>b.s)return 1;
        return 0;
    }

“可是这些代码我都看得懂，”勇者说，“但是怎么用啊？”  
“那这就太简单了。”

#include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<iostream>
    using namespace std;
    struct ha{
        int l,s;
    }a[100];
    bool cmp(ha a,ha b){
        if(a.l>b.l)return 1;
        if(a.l<b.l)return 0;
        if(a.s>b.s)return 1;
        return 0;
    }
    int main(){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d%d",&a[i].l,&a[i].s);
        }
        sort(a+1,a+n+1,cmp); 
        for(int i=1;i<=n;i++){
            printf("%d %d\n",a[i].l,a[i].s);
        }
        return 0;
    }

也就是说，只需要写成**sort（a+1，a+n+1，cmp）**即可了！  
“汗……原来这么简单。”勇者说，“行吧，我们到下一个厂子！”

转载于:https://www.cnblogs.com/luyouqi233/p/7706039.html