期望为线性的选择算法

期望为线性的选择算法

平时，我们在做从一堆没有排序的数中，找出最大，或者最小，必须要做N-1次比较。

而当我们同时需要找出最大最小值时，我们只需要3|_n/2_|次比较。具体做法是：我们把所有的数分为两组，比较每一组并记录较大和较小的数值，把较大的放在一组找最大的，把较小的放在一组找最小的。

但我们在现实中会遇到很多找第i个最小或者最大的值的情况，在这种情况下，我们有更牛的算法，它的期望为线性时间。RANDSOMIZE-SELECT算法，它是以快速排序算法为模型的，与快速排序法不同的是：快速排序法需要递归的处理划分的两边的情况，而RANDSOMIZE-SELECT算法只需要递归的处理一边的情况。

RANDOMIZED-SELECT(A,p,r,i)
    if p = r 
        then retrun A[p]
    q= RANDOMIZED-PARTITION(A,p,r)
    k= q-p+1
    if i = k
       then return A[q]
    else if i<k
        return RANDOMIZED-SELECT(A,p,q-1,i)
    else
        return RANDOMIZED-SELECT(A,q+1,r,i-k)
　　

RANDOMIZED-PARTITION(A,p,r)
    i=RANDOM(p,r)
    exchange A[r],A[i]
    return PARTITION(A,p,r)
PARTITION(A,p,r)
    x=A[r]
    i=p-1
    for j=p to r-1
    do if A[j]<=x
        i++
        exchange A[i],A[j]//j是为了找比x小的数，而j后面的i是为了记录比x大的数，所以在遇到比x小的数时，就交换位置，完成小的在前，大的在后
    exchange A[i+1],A[r]//最后把x和比大的数交换位置

    return i+1

在PARTITION算法中，这个算法是快速排序算法的关键。而 RANDOMIZED-PARTITION中i的选取是随机的，在最坏的情况下，每次分割的位置元的位置都导致一边没有元素，这样就不能够达到线性了。