题目大意:对 $n$ 组数据进行从小到大排序,在这里我们使用快速排序
题目思路:
先来整理一下快排的主要思想
1.确定分界点:左边界 $q[l]$,右边界 $q[r]$,中间值(平均值)$q[l+r>>1]$,随机
2.调整区间(重要!)根据 $x$ 的值将整个区间分为两半,使得把 $\geq x$的放到 $x$ 的左边,$\leq x$ 的放到 $x$ 的右边
3.递归处理左右两端:左右排好序
#include<bits/stdc++.h>
using namespace std;
int q[100010];
void d(int q[],int l,int r)
{
if(l>=r)return;
int i=l-1,j=r+1,x=q[l+r>>1];
while(i<j)
{
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j)swap(q[i],q[j]);
}
d(q,l,j);
d(q,j+1,r);
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>q[i];
d(q,0,n-1);
for(int i=0;i<n;i++)cout<<q[i]<<" ";
}
上面代码中:如果左端点 $\geq$ 右端点,退出。
如何去优美而简洁的处理区间?
1.设 $i$ 为 $l-1$,$j$ 为 $r+1$
2.扫描整个区间
while(i<j)
{
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j)swap(q[i],q[j]);
}