快速排序(quicksort)是分治法的典型例子，它的主要思想是将一个待排序的数组以数组的某一个元素X为轴，使这个轴的左侧元素都比X大，而右侧元素都比X小(从大到小排序)。然后以这个X在变换后数组的位置i分为左右两个子数组，再分别进行快速排序，直到子数组中只有一个元素为止。
快速排序算法如下
voidquicksort(intA[],intp,intr)
{
inti;
if(p<r)
{
i=partition(A,p,r);
quicksort(A,0,i-1);
quicksort(A,i+1,r);
}
}
其中partition函数将得到X所在的位置i（在这里总以数组的最后一个元素为轴）。
intpartition(intA[],intp,intr)
{
inti=p-1,j;
for(j=p;j<r;j++)
{
if(A[j]>=A[r])
{
i++;
swap(&A[i],&A[j]);
}
}
swap(&A[i+1],&A[r]);
returni+1;
}
由于总是选择数组的最后一个元素做为轴，因此可能出现X的左边为n - 1或接近n - 1个元素，而右边没有元素，或元素很少的情况，即X最大或比较大。这样使quicksort将出现最坏的情况，也就是时间复杂度为O(n^2)。因此partition可以采用随机方式得到轴X的位置i。 这样它的平均情况是非常好的（时间复杂度为O(nlogn)），也就是说，最坏情况很难出现。
intnew_random(intmin,intmax)
{
return(min+(int)(((float)rand()/RAND_MAX)*(max-min)));
}
intrandomize_partition(intA[],intp,intr)
{
inti=new_random(p,r);
swap(&A[i],&A[r]);
returnpartition(A,p,r);
}
完整的代码如下
#include<stdio.h>
#include<stdlib.h>
voidout_int_array(intdata[],intn)
{
inti;
for(i=0;i<n;i++)
{
printf("%d",data[i]);
}
printf("\n");
}
voidswap(int*a,int*b)
{
intx;
x=*a;
*a=*b;
*b=x;
}
intnew_random(intmin,intmax)
{
return(min+(int)(((float)rand()/RAND_MAX)*(max-min)));
}
intpartition(intA[],intp,intr)
{
inti=p-1,j;
for(j=p;j<r;j++)
{
if(A[j]>=A[r])
{
i++;
swap(&A[i],&A[j]);
}
}
swap(&A[i+1],&A[r]);
returni+1;
}
voidquicksort(intA[],intp,intr)
{
inti;
if(p<r)
{
i=partition(A,p,r);
quicksort(A,0,i-1);
quicksort(A,i+1,r);
}
}
intrandomize_partition(intA[],intp,intr)
{
inti=new_random(p,r);
swap(&A[i],&A[r]);
returnpartition(A,p,r);
}
voidrandomize_quicksort(intA[],intp,intr)
{
inti;
if(p<r)
{
i=randomize_partition(A,p,r);
quicksort(A,0,i-1);
quicksort(A,i+1,r);
}
}
intmain()
{
intA[]={4,1,44,-12,5,125,30};
intB[]={4,1,44,-12,5,125,30};
out_int_array(A,7);
quicksort(A,0,6);
out_int_array(A,7);
printf("--------------------------randomize-----------------------------\n");
srand((unsigned)time(NULL));
randomize_quicksort(B,0,6);
out_int_array(B,7);
return0;
}
本文转自 androidguy 51CTO博客，原文链接：/androidguy/215359，如需转载请自行联系原作者
