例 11.3. 线性查找

    1、实现一个算法，在一组随机排列的数中找出最小的一个。你能想到的最直观的算法一定是Θ(n)的，想想有没有比Θ(n)更快的算法？

    3、进一步泛化，在一组随机排列的数中找出第k小的，这个元素称为k-th Order Statistic。能想到的最直观的算法肯定是先把这些数排序然后取第k个，时间复杂度和排序算法相同，可以是Θ(nlgn)。这个问题虽然比前两个问题复杂，但它也有平均情况下时间复杂度是Θ(n)的算法，将上一节习题1的快速排序算法稍加修改就可以解决这个问题：

    1. /* 从start到end之间找出第k小的元素 */
    2. int order_statistic(int start, int end, int k)
    3.     用partition函数把序列分成两半，中间的pivot元素是序列中的第i个;
    4.     if (k == i)
    5.         返回找到的元素;
    6.         从后半部分找出第k-i小的元素并返回;
    7.     else
    8.         从前半部分找出第k小的元素并返回;