快速排序（Quick Sort）

参考资料

• 快速排序 - OI Wiki

实现

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
int a[N];
void qsort(int l,int r)
{
	if(l>r)return;
	int i=l,j=r;
	while(i!=j)
	{
		while(a[j]>=a[l]&&i<j)j--;
		while(a[i]<=a[l]&&i<j)i++;
		if(i<j)swap(a[i],a[j]);
	}
	swap(a[l],a[i]);
	qsort(l,i-1);
	qsort(i+1,r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	qsort(1,n);
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
	return 0;
}

例题

洛谷 P1177 【模板】排序

洛谷 P1177 【模板】排序

将读入的 $n$ 个数从小到大排序后输出。（$n\le10^5$）

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
int a[N];
void qsort(int l,int r)
{
	if(l>r)return;
	int i=l,j=r;
	while(i!=j)
	{
		while(a[j]>=a[l]&&i<j)j--;
		while(a[i]<=a[l]&&i<j)i++;
		if(i<j)swap(a[i],a[j]);
	}
	swap(a[l],a[i]);
	qsort(l,i-1);
	qsort(i+1,r);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	qsort(1,n);
	for(int i=1;i<=n;i++)
	{
		cout<<a[i]<<' ';
	}
	return 0;
}