快速排序

手写代码

从这里开始就是真正的考验了。

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

勇者将刚才写的所有魔法代码全部试了一下，发现全部TLE，然而用桶排序的话会MLE。

“……”勇者累得说不出话来。

“不要急躁吗，其实我从照相馆那里借了点书过来，说不定就有你想要的哦！”

勇者翻开了书，上面写了神奇的魔法。

快速排序，O(NlogN)

注：这个是从小到大排的……大（其）家（实）自（是）己（我）写（懒）一（的）下（写）从（了）大（而）到（已）小（啊）的（蛤）吧（蛤）！

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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){ //从右到左找比中间数小的 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
     
      #include
      
       #include
       
        #include
        
         #include
         
          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.s)return 1;    return 0;}
     

“可是这些代码我都看得懂，”勇者说，“但是怎么用啊？”

“那这就太简单了。”

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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.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）即可了！

“汗……原来这么简单。”勇者说，“行吧，我们到下一个厂子！”