c++快速查找实现（递归和非递归）

    　因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

以图为例子，更好理解：

以一个数组作为示例，取区间第一个数为基准数。

初始时，i = 0;  j = 9;   X = a[i] = 72

由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++;  这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

数组变为：

 i = 3;   j = 7;   X=72

再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

代码实现：

/*the quickSort,partion method first */
template<class DataType>
int Partition(vector<DataType> &vect, int low, int high)
{
	DataType base = vect[low];//the first element as compare-base
	
	while( low < high)
	{
		while( low < high && vect[high] >= base )
			high--;
		if( low < high )
			vect[low] = vect[high];//move the value of high to the low
		while( low < high && vect[low] < base)
			low++;
		if( low < high )
			vect[high] = vect[low];
	}
	vect[low] = base;//at this time,low==high
	return low;
}

递归的快速排序：

/*recursive*/
template<class DataType> 
void QuickSort_Recursive(vector<DataType> &vect, int low, int high )
{
	if( low < high)
	{
		int mid = Partition(vect, low, high);
		QuickSort_Recursive(vect, low, mid-1);
		QuickSort_Recursive(vect, mid+1, high);
	}
}

/*no recursive,using stack*/
template<class DataType>
void QuickSort_NoRecursive(vector<DataType> &vect, int low, int high)
{
	stack<int> stack;
	
	if( low < high )
	{
		int mid = Partition(vect, low, high);
		/*using devide-and-conquer,stack only save the first and the last element in the child*/
		if( low < mid-1 )
		{
			stack.push(low);
			stack.push(mid-1);
		}
		if( high > mid+1 )
		{
			stack.push(mid+1);
			stack.push(high);
		}
		
		while(!stack.empty())
		{
			int q = stack.top();
			stack.pop();
			int p = stack.top();
			stack.pop();
			
			mid = Partition(vect, p, q);
					
			if( p < mid-1 )
			{
				stack.push(p);
				stack.push(mid-1);
			}
			if( q > mid+1 )
			{	
				stack.push(mid+1);
				stack.push(q);
			}
		}
	}
}

#include <ctime>//clock()
#include <cstdlib>
#include <algorithm>//random_shuffle
#include <stack>
#include <vector>
#include <iostream>

using namespace std;

/*the quickSort,partion method first */
template<class DataType>
int Partition(vector<DataType> &vect, int low, int high)
{
	DataType base = vect[low];//the first element as compare-base
	
	while( low < high)
	{
		while( low < high && vect[high] >= base )
			high--;
		if( low < high )
			vect[low] = vect[high];//move the value of high to the low
		while( low < high && vect[low] < base)
			low++;
		if( low < high )
			vect[high] = vect[low];
	}
	vect[low] = base;//at this time,low==high
	return low;
}

/*recursive*/
template<class DataType> 
void QuickSort_Recursive(vector<DataType> &vect, int low, int high )
{
	if( low < high)
	{
		int mid = Partition(vect, low, high);
		QuickSort_Recursive(vect, low, mid-1);
		QuickSort_Recursive(vect, mid+1, high);
	}
}

/*no recursive,using stack*/
template<class DataType>
void QuickSort_NoRecursive(vector<DataType> &vect, int low, int high)
{
	stack<int> stack;
	
	if( low < high )
	{
		int mid = Partition(vect, low, high);
		/*using devide-and-conquer,stack only save the first and the last element in the child*/
		if( low < mid-1 )
		{
			stack.push(low);
			stack.push(mid-1);
		}
		if( high > mid+1 )
		{
			stack.push(mid+1);
			stack.push(high);
		}
		
		while(!stack.empty())
		{
			int q = stack.top();
			stack.pop();
			int p = stack.top();
			stack.pop();
			
			mid = Partition(vect, p, q);
					
			if( p < mid-1 )
			{
				stack.push(p);
				stack.push(mid-1);
			}
			if( q > mid+1 )
			{	
				stack.push(mid+1);
				stack.push(q);
			}
		}
	}
}

int main(int argc, char** argv)
{
	int len = 1000000;
	vector<int> vect;
	for(int i=0; i<len; i++)
		vect.push_back(rand());
	clock_t t1 = clock();
	QuickSort_Recursive(vect, 0, len-1);
	clock_t t2 = clock();
	cout<<"recursive using time:"<<1.0*(t2-t1)/CLOCKS_PER_SEC<<endl;

	random_shuffle(vect.begin(), vect.end());//Rearranges the elements in the range [first,last) randomly	
	t1 = clock();
	QuickSort_NoRecursive(vect, 0, len-1);
	t2 = clock();
	cout<<"No recursive using time:"<<1.0*(t2-t1)/CLOCKS_PER_SEC<<endl;

	return 0;
}

[liujl@localhost mycpp]$ g++ -g quickSort.cxx -o quickSort
[liujl@localhost mycpp]$ ./quickSort 
recursive using time:0.34
No recursive using time:0.43

c++快速查找实现（递归和非递归）

原文：http://blog.csdn.net/richerg85/article/details/19117123