快速排序算法C＋＋實現

//quick sort
//STL中也有現成的快速排序算法，內部實現采用了以下技巧
//1）樞軸的選擇采取三數取中的方式
//2）後半段采取循環的方式實現
//3）快速排序與插入排序結合
#include
#include
#include

using namespace std;

//這一版本是最簡單實現版本，對於快速排序的優化主要有以下幾個方面：
//1）樞軸的選擇，若樞軸選取不全適，比如，若每次遞歸時，兩個子區間中的一個為空，則快速排序將退化為冒泡排序
//關於樞軸的選擇有多種：取最後一個元素、取第一個元素、三數取中、九數取中、隨機值等
//2）另一方面是對迭代過程的優化，減少交換次數，減少遞歸深度等；
template
int partion1(vector& vec,int start,int end)
{//快速排序的核心部分
	//取最後一個作為樞軸和第一個作為樞軸程序類似，以下是取最後一個元素作為樞軸
	int key=vec[end];
	int fast,slow;
	fast=slow=start;

	//用兩個指針的移動實現
	for(;fast
int midNumber(type a,type b,type c)
{
	int big1=max(a,b);
	int big2=max(a,c);
	int big3=max(b,c);

	return min(big1,min(big2,big3));
}

template
int partion2(vector& vec,int start,int end)
{
	//3數取中和9數取中的方式，保證了一定隨機性，以下是3數取中的方式
	int key=midNumber(vec[start],vec[(start+end)/2],vec[end]);

	int midNumPos=0;
	if(key==vec[start])
		midNumPos=start;
	else if(key==vec[end])
		midNumPos=end;
	else
		midNumPos=(start+end)/2;

	vec[midNumPos]=vec[end];
	vec[end]=key;

	//現在采用一種和上一種方案不同的交換方式
	while(start=key)
			end--;

		tmp=vec[start];
		vec[start]=vec[end];
		vec[end]=tmp;
	}

	return start;
}

template
int partion3(vector& vec,int start,int end)
{//取隨機數的方法
	int keyNumPos=start+rand()%(end-start);
	int tmp=vec[keyNumPos];
	vec[keyNumPos]=vec[end];
	vec[end]=tmp;

	int key=vec[end];
	while(start=key)
			end--;

		tmp=vec[start];
		vec[start]=vec[end];
		vec[end]=tmp;
	}
	return start;
}
//以上是三種對樞軸的優化方法，無非就是避免快速排序惡化
//以下是避免不必要的交換過程
template
int partion4(vector& vec,int start,int end)
{//取隨機數的方法
	int keyNumPos=start+rand()%(end-start);
	int tmp=vec[keyNumPos];
	vec[keyNumPos]=vec[end];
	vec[end]=tmp;

	int key=vec[end];
	while(start=key)
			end--;

		vec[start]=vec[end];//start以end覆蓋
	}
	vec[start]=key;
	return start;
}


template
void qSort1(vector& vec,int start,int end)
{
	if(start>=end)return;
	int index=partion4(vec,start,end);//key
	qSort1(vec,start,index-1);
	qSort1(vec,index+1,end);
}

//遞歸過程需要出棧入棧，成本較高，而且可能棧溢出，如果可能的話最好以循環方式代替遞歸
template
void qSort2(vector& vec,int start,int end)
{
	if(start>=end)return;
	
	int index;//key
	while(start
void qSort3(vector& vec,int start,int end)
{
	if(start>=end)return;
	
	int index;//key
	if(end-start>VALUE)
	{	
		while(start
void quickSort(vector& vec)
{
	int length=vec.size();
	qSort2(vec,0,length-1);
}

int main()
{
	int a[10]={1,5,9,0,6,3,2,7,8,4};
	vector vec(a,a+10);

	quickSort(vec);

	for(int i=0;i