算法进化历程之“快速排序”
算法进化历程之“快速排序”巧若拙（欢迎转载，但请注明出处：http://blog.）
快速排序是在实践中最快的已知排序算法，它的版本非常多，本文将给出常见的一些版本并分析其优化过程。
几乎所有的快速排序算法都要用到以下两个函数：
void QuickSort(ElemType a[], int n) //快速排序的驱动程序
{
QSort(a, 0, n-1);
}
void Swap(ElemType *a, ElemType *b)//家喻户晓的交换函数
{
ElemType c = *a;
*a = *b;
*b = c;
}
快速排序的主程序QSort()的实现根据其优化程度的不同有多个版本，最初级的版本是：
void QSort_1(ElemType a[], int left, int right)
{
int pivot;
if (left < right)
{
pivot = Partition_1(a, left, right); //快速排序分割函数
QSort_1(a, left, pivot-1);
QSort_1(a, pivot+1, right);
}
}
由于分割函数的不同实现方式，导致的快速排序算法版本的多样性。
版本一：取最后一个元素为枢纽元
《算法导论》中给出的第一个版本是取最后一个元素为枢纽元，然后从左侧向右扫描数组，将比枢纽元pivotKey小的值放在左侧，最后把枢纽元交换到适合位置。代码如下：
int Partition_1(ElemType a[], int left, int right)
{
ElemType pivotKey = a[right];
int i, j;
for (i=j=left; j<right; j++)//把比pivotKey小的值放在左侧
{
if (a[j] < pivotKey)
{
if (i != j)
Swap(&a[i], &a[j]);
i++;
}
}
Swap(&a[right], &a[i]);
return i;
}
版本二：取左侧第一个元素为枢纽元
因为更常见的办法是取第一个元素为枢纽元（之后本文版本2-5均采用此法），所以我把Partition_1()略作修改，得到Partition_2()。代码如下：
int Partition_2(ElemType a[], int left, int right)
{
ElemType pivotKey = a[left];
int i, j;
for (i=j=right; j>left; j--)//把比pivotKey大的值放在右侧
{
if (a[j] > pivotKey)
{
if (i != j)
Swap(&a[i], &a[j]);
i--;
}
}
Swap(&a[left], &a[i]);//可以确定a[i]<=a[left]
return i;
}
版本三：从数组的两端交替向中间扫描，每趟做两次交换
很明显，只向一个方向扫描，每遇到比枢纽元pivot小的值就交换到左侧适当位置，会造成很多低效的交换，即某个位置处的元素可能会交换两次。我们可以通过从数组的两端交替向中间扫描，每扫描一次就把“不合群”的元素交换到另一侧的方法，确保每个位置的元素最多只被交换一次，这样效率要高于版本二。
int Partition_3(ElemType a[], int left, int right)
{
ElemType pivotKey = a[left];
while (left < right)//从数组的两端交替向中间扫描，实际上每次被交换的值都是枢纽元
{
while (left < right && a[right] >= pivotKey)
right--;
if (left == right)
break;
Swap(&a[left++], &a[right]);//把比pivotKey t小的值放在左侧
while (left < right && a[left] <= pivotKey)
left++;
if (left == right)
break;
Swap(&a[left], &a[right--]);//把比pivotKey大的值放在右侧
}
return left;//最后枢纽元在left所指处
}
版本四：从数组的两端交替向中间扫描，每趟只做一次交换
进一步观察Partition_3()，我们发现每趟扫描都要发生两次交换，而且每次交换都有枢纽元的参与，还是存在不少多余的交换。能不能每趟只做一次交换呢？可以。代码如下：
int Partition_4(ElemType a[], int left, int right)
{
ElemType pivotKey = a[left];
int i = left;
while (i < right)//从数组的两端交替向中间扫描，每趟只做一次交换，效率较高
{
while (i < right && a[right] >= pivotKey)
right--;
if (i == right)
break;
while (i < right && a[i] <= pivotKey)
i++;
if (i == right)
break;
Swap(&a[i], &a[right]);
}
a[left] = a[i]; //最终将枢纽元归位
a[i] = pivotKey;
return i;//最后枢纽元在i所指处
}
版本五：用新元素覆盖已备份的旧元素
Partition_4()的交换操作比Partition_3()少了一半，应该说效率提高了不少。但交换操作本身需要三个动作，能不能有更好的方法来代替Swap()函数呢？或者说能否一次性把所有的元素“分配”到适合的位置呢？有！那就是先保存好第一个需要替换的元素值，然后用新元素覆盖已保存的旧元素——即此时有新旧两个位置存储了新元素的值。如此依次覆盖替换，最后把第一个被替换的元素值存储到最后一个“新元素”的“旧位置”，即完成了所有元素的位置安排。代码如下：
int Partition_5(ElemType a[], int left, int right)
{
ElemType pivotKey = a[left];
while (left < right)//从数组的两端交替向中间扫描，用新元素替换已保存的“不合群”元素，比交换操作效率高
{
while (left < right && a[right] >= pivotKey)
right--;
if (left == right)
break;
//因为a[left]的值已经有备份，故可以被替代；同理，执行此操作后a[right]的值也已经备份了，原a[right]就可以被覆盖了
a[left] = a[right];
while (left < right && a[left] <= pivotKey)
left++;
if (left == right)
break;
a[right] = a[left];
}
a[left] = pivotKey;
return left;//最后枢纽元在left所指处
}
版本六：随机分割
前面五个版本，通过改进扫描方式和交换元素的方法，提高了效率。但由于每趟扫描都取左边第一个元素为枢纽元，很可能造成划分的不平衡，而导致时间复杂度变坏。采用随机产生枢纽元位置的方法，可以更好的实现均衡分割。算法借鉴了Partition_4()的扫描和交换方式。代码如下：
int Partition_6(ElemType a[], int left, int right)
{
ElemType pivotKey;
int i = rand() % (right-left+1) + left;//随机产生枢纽元位置
Swap(&a[left], &a[i]); //把枢纽元存储到a[left]
pivotKey = a[left];
i = left;
while (i < right)//从数组的两端交替向中间扫描，每趟只做一次交换，效率较高
{
while (i < right && a[right] >= pivotKey)
right--;
if (i == right)
break;
while (i < right && a[i] <= pivotKey)
i++;
if (i == right)
break;
Swap(&a[i], &a[right]);
}
a[left] = a[i]; //最终将枢纽元归位
a[i] = pivotKey;
return i;//最后枢纽元在i所指处
}
版本七：三数中值分割
随机产生枢纽元位置固然不错，但生产随机数的成本本身就不低，所以更好的一个替代方案是使用数组左端，右端和中心位置上的三个元素的中值作为枢纽元。算法借鉴了Partition_5()的扫描和交换方式。
代码如下：
int Partition_7(ElemType a[], int left, int right)
{
ElemType pivotKey = Median3(a, left, right);//三数中值分割，返回枢纽元
while (left < right)//从数组的两端交替向中间扫描，用新元素替换已保存的“不合群”元素，比交换操作效率高
{
while (left < right && a[right] >= pivotKey)
right--;
if (left == right)
break;
a[left] = a[right];
while (left < right && a[left] <= pivotKey)
left++;
if (left == right)
break;
a[right] = a[left];
}
a[left] = pivotKey;
return left;//最后枢纽元在left所指处
}
ElemType Median3(ElemType a[], int left, int right)//三数中值分割，返回枢纽元a[left]，并确保确保a[right]大于枢纽元
{
int mid = (left + right) / 2;
//确保a[right]是最大的
if (a[left] > a[right])
Swap(&a[left], &a[right]);
if (a[mid] > a[right])
Swap(&a[mid], &a[right]);
//把 a[left] 作为枢纽元返回 ，要求 a[left] >= a[mid]
if (a[left] < a[mid])
Swap(&a[left], &a[mid]);
return a[left];
}
版本八：消除尾递归
分割函数的不同实现方式就介绍到这里，接下来我们对QSort()函数进行优化。
最简单的优化是消除尾递归。代码如下：
void QSort_2(ElemType a[], int left, int right)//消除尾递归，效率更高
{
int pivot, i;
while (left < right)
{
pivot = Partition_7(a, left, right);
QSort_2(a, left, pivot-1);
left = pivot+1; //使用迭代，消除尾递归
}
}
版本九：用插入排序解决小数组
对于很小的数组（N<20），快速排序不如插入排序好。所以我们可以采取一个这样的策略：若数组长度小于MAXLENTH，采用直接插入排序，否则采用快速排序。
代码如下：
void QSort_3(ElemType a[], int left, int right)
{
int pivot, i = left;
while (i + MAXLENTH < right)
{
pivot = Partition_7(a, i, right);
QSort_3(a, left, pivot-1);
i = pivot + 1; //使用迭代，消除尾递归
}
InsertSort(a, i, right);
}
void InsertSort(ElemType a[], int left, int right)//直接插入排序
{
int i, j;
ElemType temp;
for (i=left+1; i<=right; i++)
{
temp = a[i];
for (j=i;(j>0) && (a[j-1]>temp); j--)
{
a[j] = a[j-1];
}
a[j] = temp;
}
}
版本十：Hoare的原始版本
我在《数据结构与算法分析——C语言描述》（Mark Allen Weiss著）中看到了快速排序的一个好的实现方法（通过对比《算法导论》的描述，我认为这种方法很可能就是快速排序算法发明人Hoare最早提出的版本），该方法先利用Median3()函数，在实现三数分割的同时，对这三个元素也进行了排序（我的Median3()函数与书中的略有不同，但功能基本相似），这样就设置了边界哨兵，同时要求a[i] == pivotKey时也要停止扫描，这样就可以不必每次判断是否越界，非常适合元素相异的大型数组，效率可以提高一倍。
代码如下：
void QSort_4(ElemType a[], int left, int right)
{
ElemType pivotKey;
int i, j;
if (left + MAXLENTH < right)
{
pivotKey = Median3(a, left, right);//三数中值分割，返回枢纽元a[left]，并确保确保a[right]大于枢纽元
i = left;
j = right;
while (1)//a[i] == pivotKey也交换，可以不设边界，效率较高
{
while (a[--j] > pivotKey) {}
while (a[++i] < pivotKey) {}
if (i < j)
Swap(&a[i], &a[j]);
else
break;
}
Swap(&a[left], &a[j]);
QSort_4(a, left, j-1);
QSort_4(a, j+1, right);
}
else
{
InsertSort(a, left, right);
}
}
消除尾递归的版本如下：
void QSort_5(ElemType a[], int left, int right)//a[i] == pivotKey也交换，可以不设边界（消除尾递归版本）
{
ElemType pivotKey;
int i, j;
i = left;
while (i + MAXLENTH < right)
{
pivotKey = Median3(a, i, right);//三数中值分割，返回枢纽元a[left]，并确保确保a[right]大于枢纽元
left = i;
j = right;
while (1)//a[i] == pivotKey也交换，可以不设边界，效率较高
{
while (a[--j] > pivotKey) {}
while (a[++i] < pivotKey) {}
if (i < j)
Swap(&a[i], &a[j]);
else
break;
}
Swap(&a[left], &a[j]);
QSort_5(a, left, j-1);
i = j + 1; //使用迭代，消除尾递归
}
InsertSort(a, i, right);
}
快速排序真的很快，但也很难正确实现，我上面列出的算法虽然都进行了小规模数据的测试，但不敢保证大规模数据时是否还能正确使用，请热心的您给测试一下吧。感谢您的阅读。
