算法导论学习笔记——7快速排序
程序员文章站
2022-07-08 22:20:54
...
7快速排序
void QuickSort(ll A[],ll p,ll r)
{
if(p<r)
{
ll q=Partition(A,p,r);
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
}
ll Partition(ll A[],ll p,ll r)
{
x=A[r];
i=p-1;
for(j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i++;
swap(A[i],A[j]);
}
}
swap(A[i+1],A[r]);
return i+1;
}
完整程序
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> pll;
const int inf = 0x3f3f3f3f;
const int maxn=100010;
ll A[maxn];
ll Partition(ll A[],ll p,ll r)
{
ll x=A[r];
ll i=p-1;
for(ll j=p;j<=r-1;j++)
{
if(A[j]<=x)
{
i++;
swap(A[i],A[j]);
}
}
swap(A[i+1],A[r]);
return i+1;
}
void QuickSort(ll A[],ll p,ll r)
{
if(p<r)
{
ll q=Partition(A,p,r);
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
}
int main()
{
ll n;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
cin>>A[i];
QuickSort(A,1,n);
for(ll i=1;i<=n;i++)
cout<<A[i]<<' ';
return 0;
}
上一篇: 【冒泡排序】、【快速排序】