首页 > 代码库 > 快速排序递归非递归队列堆栈实现

快速排序递归非递归队列堆栈实现

2024-07-17 00:41:42   222人阅读

递归实现

#include<iostream>
using namespace std;
template <class T>
void QuickSort(T A[],int left,int right)
{
	if(left<right)
	{	
		int i=left;
	    int j=right+1;
		do
		{
			do i++;while(A[i]<A[left]);
			do j--;while(A[j]>A[left]);
			if(i<j) Swap(A[i],A[j]);
		}while(i<j);
		Swap(A[left],A[j]);
		QuickSort(A,left,j-1);
		QuickSort(A,j+1,right);
	}
}
template <class T>
void Swap(T &a,T &b)
{
	T temp =a;
	a=b;
	b=temp;
}

int main()
{

	int A[7]={1,8,4,2,3,5,6};
	cout<<A[8]<<endl;
	QuickSort(A,0,6);
	for(int i=0;i<7;i++)
	{
		cout<<A[i]<<" "<<endl;
	}
	return 0;
}

递归使用partition实现


#include<iostream>
using namespace std;
#include<queue>
template <class T>
int partition (T A[],int left,int right)
{
	int i=left,j=right+1;
	if(left<right)
	{
		do
		{
			do i++;while(A[i]<A[left]);
			do j--;while(A[j]>A[left]);
			if(i<j) Swap(A[i],A[j]);
		}while(i<j);
		Swap(A[left],A[j]);
	}
	return j;
}
template <class T>
void QuickSort(T A[],int left,int right)
{
	if(left<right)
	{
		int j=partition(A,left,right);
		QuickSort(A,left,j-1);
		QuickSort(A,j+1,right);
	}
}

template <class T>
void Swap(T &a,T &b)
{
	T temp =a;
	a=b;
	b=temp;
}
int main()
{

	int A[18]={1,8,2,4,5,1,2,8,2,4,5,2,3,4,2,3,5,6};
	QuickSort(A,0,17);
	for(int i=0;i<18;i++)
	{
		cout<<A[i]<<" "<<endl;
	}
	return 0;
}

非递归使用栈实现


#include<iostream>
using namespace std;
#include<stack>
template <class T>
int partition (T A[],int left,int right)
{
	int i=left,j=right+1;
	if(left<right)
	{
		do
		{
			do i++;while(A[i]<A[left]);
			do j--;while(A[j]>A[left]);
			if(i<j) Swap(A[i],A[j]);
		}while(i<j);
		Swap(A[left],A[j]);
	}
	return j;
}
template <class T>
void QuickSort(T A[],int low,int high)
{
	stack<T> st;
	if(low<high)
	{
		int mid=partition(A,low,high);
		if(low<mid-1)
		{
			st.push(low);
			st.push(mid-1);
		}
		if(mid+1<high)
		{
			st.push(mid+1);
			st.push(high);
		}
		while(!st.empty())
		{
			T q=st.top();
			st.pop();
			T p=st.top();
			st.pop();
			mid=partition(A,p,q);
			if(p<mid-1)
			{
				st.push(p);
				st.push(mid-1);
			}
			if(mid+1<q)
			{
				st.push(mid+1);
				st.push(q);
			}
		}
	}
}
template <class T>
void Swap(T &a,T &b)
{
	T temp =a;
	a=b;
	b=temp;
}
int main()
{

	int A[7]={1,8,4,2,3,5,6};
	QuickSort(A,0,6);
	for(int i=0;i<7;i++)
	{
		cout<<A[i]<<" "<<endl;
	}
	return 0;
}

非递归队列实现


#include<iostream>
using namespace std;
#include<queue>
template <class T>
int partition (T A[],int left,int right)
{
	int i=left,j=right+1;
	if(left<right)
	{
		do
		{
			do i++;while(A[i]<A[left]);
			do j--;while(A[j]>A[left]);
			if(i<j) Swap(A[i],A[j]);
		}while(i<j);
		Swap(A[left],A[j]);
	}
	return j;
}

template <class T>
void QuickSort(T A[],int low,int high)
{
	queue<T> st;
	if(low<high)
	{
		int mid=partition(A,low,high);
		if(low<mid-1)
		{
			st.push(low);
			st.push(mid-1);
		}
		if(mid+1<high)
		{
			st.push(mid+1);
			st.push(high);
		}
		while(!st.empty())
		{
			T q=st.front();
			st.pop();
			T p=st.front();
			st.pop();
			mid=partition(A,q,p);
			if(q<mid-1)
			{
				st.push(q);
				st.push(mid-1);
			}
			if(mid+1<p)
			{
				st.push(mid+1);
				st.push(p);
			}
		}
	}
}
template <class T>
void Swap(T &a,T &b)
{
	T temp =a;
	a=b;
	b=temp;
}
int main()
{

	int A[18]={1,8,2,4,5,1,2,8,2,4,5,2,3,4,2,3,5,6};
	QuickSort(A,0,17);
	for(int i=0;i<18;i++)
	{
		cout<<A[i]<<" "<<endl;
	}
	return 0;
}



联系
我们