学步园

//下面的选择算法来自于C.A.R.Hoare，代码由qsort4稍作修改而得
void selectHoare(DType l, DType u, DType k)
{
    if( l >= u )
        return;
    swap( l, randint(l,u) );
    DType t = x[l];
    DType i = l;
    DType j = u + 1;
    while(true)
    {
        do i++; while i         do j--; while x[j] > t;
        if( i > j )
            break;
        DType temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    }
    swap(l, j);
    if( j         selectHoare(j+1, u, k);
    else if( j > k )
        selectHoare(l, j-1, k);
}