题解 P1177 【【模板】快速排序】
基础的排序题
很水很水的
先说下思路吧
1.快速排序（题目要求手打 然而我并不想手打）
快速排序是一种基于二分思想的算法，复杂度为 O( n*log2(n) )
然后如果遇到毒瘤出题人的话（给你一个本身就有序（或者趋近于有序）的序列），那么你的快速排序就会退化成 O( n^2 )的复杂度
STL之sort版：
#include<bits/stdc++.h>//万能头（贼爽，但别把变量名设成其他关键字）
#define F(i,n,m) for(int i=n;i<=m;i++)//灵性define，减少码量（for打得我烦）
using namespace std;
int a[10000001];
int main()
{
int n;
cin>>n;
F(i,1,n)
cin>>a[i];//输入
random_shuffle(a+1,a+n+1); //打乱它
sort(a+1,a+n+1);//快排（终究我还是用了STL的sort）
F(i,1,n)
cout<<a[i]<<' ';//输出
return 0;
}二分手打sort：
#include<bits/stdc++.h>
#defind F(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
int n,a[1000001];
void mysort(int l,int r)//自己写的快排
{
int mid=a[(l+r)/2];//找中间的数进行2分
int i=l,j=r;
do{
while(a[i]<mid)
i++;//找左半部分大于中间数的
while(a[j]>mid)
j--;//找右半部分小于中间数的
if(i<=j)
{
swap(a[i],a[j]);//换位
i++;//左指针右移
j--;//右指针左移
}
}
while(i<=j);
if(l<j) mysort(l,j);
if(i<r) mysort(i,r);
}
int main()
{
cin>>n;
F(i,1,n)
cin>>a[i];
random_shuffle(a+1,a+n+1); //打乱它
mysort(1,n);//快排
F(i,1,n)
cout<<a[i]<<' ';//输出
return 0;
}2.堆排序（STL大法好）
#include<bits/stdc++.h>
#define F(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
int main()
{
priority_queue<int,vector<int>,greater<int> > q;//小根堆
int n,x;
cin>>n;
F(i,1,n)
{
cin>>x;
q.push(x);
}
F(i,1,n)
{
cout<<q.top()<<' ';
q.pop();
}
return 0;
}3.桶排序
理论上来说，桶排序所要占用的空间很大，所以我们可以用STL容器中的毒瘤数据结构map来做（相当于动态开筒）
上代码：
#include<bits/stdc++.h>
#define F(i,n,m) for(int i=n;i<=m;i++)
using namespace std;
int main()
{
map<int,int> a;
int n;
cin>>n;
F(i,1,n)
{
int x;
cin>>x;
a[x]++;
}
map<int,int>::iterator it=a.begin();
for(it;it!=a.end();it++)
{
aa:;
if(it->second==0) continue;
cout<<it->first<<' '; it->second--; goto aa;
}
return 0;
}