快速排序之“采取“尾递归”和“三数取中”技术的快速排序”
下面针对快速排序进行一些优化。
QUICKSORT算法包含两个对其自身的递归调用，即调用PARTITION后，左边的子数组和右边的子数组分别被递归排序。QUICKSORT中的第二次递归调用并不是必须的，可以用迭代控制结构来代替它，这种技术叫做“尾递归”，大多数的编译器也使用了这项技术。最坏的情况下，就是划分不好的时候，递归深度为O(n)，能够二分的话递归深度为O（lgn），但是怎么才能得到好的划分呢？前面在快速排序中用了个随机化技术，“三数取中”能够让随机化更加理想。有这两项技术护体，快速排序不管在时间复杂度还是空间复杂度上都能得到优化。所谓“三数取中”是指，从子数组中随机选出三个元素，取其中间数作为主元，这算是前面随机化版本的升级版，即使是升级版，也只能影响快速排序时间复杂度O（nlgn）的常数因子。
下面以一个程序代码实现来讲解。
#include <string.h>
#include <time.h>
#define BUFFER_SIZE 10
int Partition(int *a,int p,int r)
{
int tmp=0;
int i=0;
int j=0;
i=p-1;
for(j=p;j<r;j++)
{
if(a[j]<=a[r])
{
i++;
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
}
}
tmp=a[i+1];
a[i+1]=a[r];
a[r]=tmp;
return i+1;
}
int RandomPartition(int *a,int p,int r)
{
int min=0;
int mid=0;
int max=0;
int i=0;
int j=0;
int k=0;
int tmp=0;
srand((unsigned)time(NULL));
i=rand()%(r-p+1)+p;
j=rand()%(r-p+1)+p;
k=rand()%(r-p+1)+p;
min=a[i];
mid=a[j];
max=a[k];
min=(min<mid)?min:mid;
mid=(mid<max)?mid:max;
mid=(mid>min)?mid:min;
if(a[i]==mid)
{
tmp=a[i];
a[i]=a[r];
a[r]=tmp;
}
else if(a[j]==mid)
{
tmp=a[j];
a[j]=a[r];
a[r]=tmp;
}
else if(a[k]==mid)
{
tmp=a[k];
a[k]=a[r];
a[r]=tmp;
}
return Partition(a,p,r);
}
void QuickSort(int *a,int p,int r)
{
int q=0;
while(p<r)//直到把右半边数组划分成最多只有一个元素为止，就排完了！不能用if哦，用if的话，右半边数组就只被划分一次。
{
q=RandomPartition(a,p,r);
QuickSort(a,p,q-1);
p=q+1;
}
}
int main()
{
int i=0;
int j=0;
int a[BUFFER_SIZE];
//随机生成数组
srand((unsigned)time(NULL));
for(j=0;j<BUFFER_SIZE;j++)
{
a[j]=rand()%100;
}
printf("随机生成的数组：\n");
for(i=0;i<BUFFER_SIZE;i++)
{
printf("%d ",a[i]);
}
printf("\n");
QuickSort(a,0,BUFFER_SIZE-1);
printf("对数组进行快速排序：\n");
for(i=0;i<BUFFER_SIZE;i++)
{
printf("%d ",a[i]);
}
system("pause");
return 0;
}
优化的尾递归：
QUICKSORT (A, p, r )
while p < r
do Partition and sort the small subarray ?rst
q ← PARTITION(A, p, r )
if q ? p < r ? q
then QUICKSORT (A, p, q ? 1)
p ← q + 1
else QUICKSORT (A, q + 1, r )
r ← q ? 1
