quicksort.cpp

用c++写的快速排序算法

#include<iostream>
using namespace std;
int Partition(int v[],int low,int high)
{
	int pivotpos=low;int pivot=v[low];			//基准元素
	for(int i=low+1;i<=high;i++)				//检测序列，进行划分
	{
		if(v[i]>=pivot)
		{
			pivotpos++;							//大于基准的交换到左侧
			if(pivotpos!=i){int temp=v[i];v[i]=v[pivotpos];v[pivotpos]=temp;}
		}
	}
	v[low]=v[pivotpos];v[pivotpos]=pivot;		//基准元素就位
	return pivotpos;
}
void QuickSort(int v[],int left,int right)
{
	if(left<right)
	{
		int pivotpos=Partition(v,left,right);	//划分
		QuickSort(v,left,pivotpos-1);			//对左侧子序列递归调用
		QuickSort(v,pivotpos+1,right);			//对右侧子序列递归调用
	}
}
int main()
{
	int n;
	cout<<"Input array size:"<<endl;			//输入数组大小
	cin>>n;
	int *v=new int[n];							//分配存储空间
	for(int i=0;i<n;i++)						//输入元素
	{
		cout<<"Input elements "<<i<<" :";
		cin>>v[i];
		cout<<endl;
	}
	cout<<"Before sort:"<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;
	QuickSort(v,0,n-1);							//调用快速排序算法
	cout<<"After sort:"<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;
	return 0;
}