一个关于快排的问题

做1306的sorting algorithm的时候
一开始写的快排超时了
然后用ilovenwd师兄提供了下面的快排才过了


你快排写得不好.
试试一组 1000000 个0的数据.
参考一下下面这个
voidquick_sort(int*a,intn)...{
inti=0,j=n-1;
intx=a[n/2];
while(i<=j)...{
while(a[i]<x)i++;//注意<不是<=
while(a[j]>x)j--;
if(i<=j)swap(a[i],a[j]),++i,--j;
}
if(j>0)quick_sort(a,j+1);
if(i<n-1)quick_sort(a+i,n-i);
}
关键的不是左边或间.
而是 那个<和<=的区别.
你去看一些比较好的算法书.比如Robert Sedgewick那本.有详细分析.
如果你觉得取中间有可能O(n^2)就一开始就随机Shuffle一下.不过基本没必要.
===============
voidsort(intl,intr)
...{
inti,j,x,t;
i=l;j=r;x=a[(l+r)/2];
do...{
while((a[i]<x)&&(i<r))i++;
while((a[j]>x)&&(j>l))j--;
if(i<=j)...{t=a[i];a[i]=a[j];a[j]=t;i++;j--;}
}while(i<=j);
if(l<j)sort(l,j);
if(r>i)sort(i,r);
}