靠。Sedgewick这3w-qsort算法居然还有bug!# Programming - 葵花宝典
a*n
1 楼
http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf
第9页算法，递归前面那两行，居然把 k<=p, k>=q 给漏了！
虽然结果依然正确，且不影响主要performance，但明显是个bug嘛:)
void quicksort(Item a[], int l, int r)
{
int i = l-1, j = r, p = l-1, q = r; Item v = a[r];
if (r <= l) return;
for (;;)
{
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
if (a[i] == v) { p++; exch(a[p], a[i]); }
if (v == a[j]) { q--; exch(a[j], a[q]); }
}
第9页算法，递归前面那两行，居然把 k<=p, k>=q 给漏了！
虽然结果依然正确，且不影响主要performance，但明显是个bug嘛:)
void quicksort(Item a[], int l, int r)
{
int i = l-1, j = r, p = l-1, q = r; Item v = a[r];
if (r <= l) return;
for (;;)
{
while (a[++i] < v) ;
while (v < a[--j]) if (j == l) break;
if (i >= j) break;
exch(a[i], a[j]);
if (a[i] == v) { p++; exch(a[p], a[i]); }
if (v == a[j]) { q--; exch(a[j], a[q]); }
}