CLRS 9.2期望为线性时间的选择算法

9.2-1
首先，调用RANDOMIZED-SELECT时，传入的参数 i 应该是 1 到 n （ n 是数组长）。在划分过程中，出现极不平衡的情况下有：
第8行调用RANDOMIZED-SELECT， k=1 ，所以 i<k 且 i>0 ，显然不可能；
在第9行调用RANDOMIZED-SELECT，此时 q=r,i>k 即 i>q−p+1=r−p+1 ，要 i 大于数组长，也是不可能的。
综上所述，不会对长度为0的数组递归调用。

9.2-2
在一次划分中，选择主元并不影响子问题的概率。也就是说在RANDOMIZED-PARTITION中调用RANDOM产生的结果是独立于下一次的。

9.2-3
伪代码略，附上可运行代码

#include <iostream>
#include <cstdlib>
using std::cout;
using std::endl;

int RANDOMIZED_PARTITION(int *array,int p, int r)
{
    int i = rand() % (r - p + 1) + p;
    if(i != r)
    {
        int temp = array[i];
        array[i] = array[r];
        array[r] = temp;
    }
    int piovt = array[r];
    i = p - 1;
    for(int j = p; j < r; ++j)
    {
        if(array[j] <= piovt)
        {
            ++i;
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
    int temp = array[i+1];
    array[i+1] = array[r];
    array[r] = temp;
    return i + 1;
}

int RANDOMIZED_SELECT(int *array,int p,int r,int i)
{
    if(p == r)
        return array[p];
    int q = RANDOMIZED_PARTITION(array,p,r);
    int k = q - p + 1;
    if(k == i)
        return array[q];
    else if(i < k)
        return RANDOMIZED_SELECT(array,p,q-1,i);
    else return RANDOMIZED_SELECT(array,q+1,r,i-k);
}

int RANDOMIZED_SELECT_FOR_WHILE(int *array,int p,int r,int i)
{
    while(p < r)
    {
        int q = RANDOMIZED_PARTITION(array,p,r);
        int k = q - p + 1;
        if(k == i)
            return array[q];
        else if(i < k)
            r = q - 1;
        else
        {
            p = q + 1;
            i -= k;
        }
    }
    return array[p];
}

int main()
{
    int array[9] = {5,2,1,4,9,3,7,8,-1};
    cout << RANDOMIZED_SELECT_FOR_WHILE(array,0,8,9) << endl;
    return 0;
}

9.2-4
划分序列为 9,8,7,6,5,4,3,2,1,0 。