经典算法研究系列：十二、快速排序算法所有版本的c/c++实现
作者：July、二零一一年三月二十日。
出处：http://blog.csdn.net/v_JULY_v。
--------------------------------------------------
前言：
相信，经过本人之前写的前俩篇关于快速排序算法的文章：第一篇、一、快速排序算法，及第二篇、一之续、快速排序算法的深入分析，各位，已经对快速排序算法有了足够的了解与认识。但仅仅停留在对一个算法的认识层次上，显然是不够的，即便你认识的有多透彻与深入。最好是，编程实现它。
而网上，快速排序的各种写法层次不清，缺乏统一、整体的阐述与实现，即，没有个一锤定音，如此，我便打算自己去实现它了。于是，今花了一个上午，把快速排序算法的各种版本全部都写程序一一实现了一下。包括网上有的，没的，算法导论上的，国内教材上通用的，随机化的，三数取中分割法的，递归的，非递归的，所有版本都用c/c++全部写了个遍。
鉴于时间仓促下，一个人考虑问题总有不周之处，以及水平有限等等，不正之处，还望各位不吝赐教。不过，以下，所有全部c/c++源码，都经本人一一调试，若有任何问题，恳请指正。ok，本文主要分为以下几部分内容：
第一部分、递归版
一、算法导论上的单向扫描版本
二、国内教材双向扫描版
2.1、Hoare版本
2.2、Hoare的几个变形版本
三、随机化版本
四、三数取中分割法
第二部分、非递归版好的，请一一细看。
第一部分、快速排序的递归版本
一、算法导论上的版本
在我写的第二篇文章中，我们已经知道：
“再到后来，N.Lomuto又提出了一种新的版本，此版本....，即优化了PARTITION程序,它现在写在了 算法导论 一书上”：快速排序算法的关键是PARTITION过程，它对A[p..r]进行就地重排：
PARTITION(A, p, r)
1 x ← A[r] //以最后一个元素，A[r]为主元
2 i ← p - 1
3 for j ← p to r - 1 //注，j从p指向的是r-1，不是r。
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] <-> A[j]
7 exchange A[i + 1] <-> A[r] //最后，交换主元
8 return i + 1然后，对整个数组进行递归排序：
QUICKSORT(A, p, r)
1 if p < r
2 then q ← PARTITION(A, p, r) //关键
3 QUICKSORT(A, p, q - 1)
4 QUICKSORT(A, q + 1, r)根据上述伪代码，我们不难写出以下的c/c++程序：
首先是，PARTITION过程：int partition(int data[],int lo,int hi)
{
int key=data[hi]; //以最后一个元素，data[hi]为主元
int i=lo-1;
for(int j=lo;j<hi;j++) ///注，j从p指向的是r-1，不是r。
{
if(data[j]<=key)
{
i=i+1;
swap(&data[i],&data[j]);
}
}
swap(&data[i+1],&data[hi]); //不能改为swap(&data[i+1],&key)
return i+1;
}补充说明：举个例子，如下为第一趟排序（更多详尽的分析请参考第二篇文章）：
第一趟(4步)：
a：3 8 7 1 2 5 6 4 //以最后一个元素，data[hi]为主元b：3 1 7 8 2 5 6 4
c：3 1 2 8 7 5 6 4
d：3 1 2 4 7 5 6 8 //最后，swap(&data[i+1],&data[hi])
而其中swap函数的编写，是足够简单的：
void swap(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}然后是，调用partition，对整个数组进行递归排序：
void QuickSort(int data[], int lo, int hi)
{
if (lo<hi)
{
int k = partition(data, lo, hi);
QuickSort(data, lo, k-1);
QuickSort(data, k+1, hi);
}
}现在，我有一个问题要问各位了，保持其它的不变，稍微修改一下上述的partition过程，如下：
int partition(int data[],int lo,int hi) //请读者思考
{
int key=data[hi]; //以最后一个元素，data[hi]为主元
int i=lo-1;
for(int j=lo;j<=hi;j++) //现在，我让j从lo指向了hi，不是hi-1。
{
if(data[j]<=key)
{
i=i+1;
swap(&data[i],&data[j]);
}
}
//swap(&data[i+1],&data[hi]); //去掉这行
return i; //返回i，非i+1.
}如上，其它的不变，请问，让j扫描到了最后一个元素，后与data[i+1]交换，去掉最后的swap(&data[i+1],&data[hi])，然后，再返回i。请问，如此，是否可行？
其实这个问题，就是我第二篇文章中，所提到的：
“上述的PARTITION(A, p, r)版本，可不可以改成这样咧?以下这样列”：PARTITION(A, p, r) //请读者思考版本。
1 x ← A[r]
2 i ← p - 1
3 for j ← p to r //让j 从p指向了最后一个元素r
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] <-> A[j]
//7 exchange A[i + 1] <-> A[r] 去掉此最后的步骤
8 return i //返回 i，不再返回 i+1.望读者思考，后把结果在评论里告知我。
我这里简单论述下：上述请读者思考版本，只是代码做了以下三处修改而已：1、j从 p->r；2、去掉最后的交换步骤；3、返回 i。首先，无论是我的版本，还是算法导论上的原装版本，都是准确无误的，且我都已经编写程序测试通过了。但，其实这俩种写法，思路是完全一致的。
为什么这么说列?请具体看以下的请读者思考版本，
int partition(int data[],int lo,int hi) //请读者思考
{
int key=data[hi]; //以最后一个元素，data[hi]为主元
int i=lo-1;
for(int j=lo;j<=hi;j++) //....
{
if(data[j]<=key) //如果让j从lo指向hi，那么当j指到hi时，是一定会有A[j]<=x的
{
i=i+1;
swap(&data[i],&data[j]);
}
}
//swap(&data[i+1],&data[hi]); //事实是，应该加上这句，直接交换，即可。
return i; //
}我们知道当j最后指到了r之后，是一定会有A[j]<=x的（即=），所以这个if判断就有点多余，没有意义。所以应该如算法导论上的版本那般，最后直接交换swap(&data[i+1],&data[hi]); 即可，返回i+1。所以，总体说来，算法导论上的版本那样写，比请读者思考版本更规范，更合乎情理。ok，请接着往下阅读。
当然，上述partition过程中，也可以去掉swap函数的调用，直接写在分割函数里：
int partition(int data[],int lo,int hi)
{
int i,j,t;
int key = data[hi]; //还是以最后一个元素作为哨兵，即主元元素
补充：软件开发 , C++ ,
