欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法导论学习笔记——7快速排序

程序员文章站 2022-07-08 22:20:54
...

7快速排序

算法导论学习笔记——7快速排序
算法导论学习笔记——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);
	}
}

算法导论学习笔记——7快速排序

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;
}
相关标签: 算法导论