快速排序
手写代码
从这里开始就是真正的考验了。
这个厂子全是工业大户的订单，他们非常狂躁，因此需要较快的时间出货，而且为了压缩成本，你也不能买太多的桶。
勇者将刚才写的所有魔法代码全部试了一下，发现全部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
",a[i].l,a[i].s);
}
return 0;
}也就是说，只需要写成sort（a+1，a+n+1，cmp）即可了！
“汗……原来这么简单。”勇者说，“行吧，我们到下一个厂子！”