如何修改快速排序算法,使它在最坏情况下的计算时间为O(nlog n)

/*
快排么。网上一搜就一堆了。算法只是一种思想或说成一种方法而已，并非就C语言。其它语言也一样
快排也有点像二路归并：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边，小于q的放到q的另一边,然后再以q为分界点，分别对q的两边
进行排序（快排时直接再对q两边重新取支点，整理，再取支点，...直到支点两旁都有序。也就是支点两旁只有一个数时）
*/
#include <stdio.h>
#include <stdlib.h>
int Qsort(int p[],int beg,int end)
{
if(beg+1>=end)return 0;//退出递归
int low,hight,q;
low=beg;
hight=end;
q=p[low];//q为支点，其实q可以为随机数。但相应以下程序就要改了
while(1){
while(low<hight && p[hight]>q)hight--;
if(low>=hight)break;
p[low++]=p[hight];
while(low<hight && p[low]<q)low++;
p[hight++]=p[low];
}
p[low]=q;
Qsort(p,beg,low-1);
Qsort(p,low+1,end);
}
int main()
{
int i,a[]={1,32,6,4,54,654,6,6,2,76,76,7,66,5,544,334,34,78};
Qsort(a,0,sizeof(a)/4-1);
for(i=0;i<sizeof(a)/4;i++)printf(" %d ",a[i]);
system("pause");
return 0;
}
快速排序的优势和支点元素的选择有关系。
所选支点元素每次递归后都在最前面或最后面。这样情况就会最差了。
我们知道一般的排序。（如冒泡。。）在一个数组p[m,n]中排序。都是确定最大或最小，而确定最大值（最小值）要经过n-m-1次比较。
而整个过程就差不多是(n-m-1)!次比较。
快排中：一次比较可以确定支点元素的位置。若p[m,q,n](q为支点元素）。当然确定第一个元素也是要比较（n-m-1)次。但第二个，第三个（第二层）就是(q-m-1)和(n-q-1)次比较。
明显q的值若为m或n，快排就没有什么优势了