快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
（2）快速排序的基本思想
设当前待排序的无序区为R[low..high]，利用分治法可将快速排序的基本思想描述为：
①分解：
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。
注意：
划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])：
R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
其中low≤pivotpos≤high。
②求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
③组合：
因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。
以图为例子，更好理解：
以一个数组作为示例，取区间第一个数为基准数。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
72 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
初始时，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--;
数组变为：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
48 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
88 |
85 |
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]。
数组变为：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
48 |
6 |
57 |
42 |
60 |
72 |
83 |
73 |
88 |
85 |
代码实现：
/*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);
}
}
}
}
完整的代码如下，经过测试没有发现问题，测试是用rand（）随机产生的100000数据排序，并计算递归和非递归算法花费时间：
#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
可以看到，递归的速度要比非递归快！！