舍伍德求中间值（Sherwood 型线性时间选择算法 ）

① 先判断是否需要进行随机划分即（ kϵ（ 1， n） ? n>1?）；

② 产生随机数 j，选择划分基准，将 a[j]与 a[l]交换；

③ 以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组值大于基准值；

④ 判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组 重复步骤②③

import time
import random

def look_for(L,left,right):
    m=random.randint(left,right)#产生随机数
    n=L[left]
    L[left]=L[m]
    L[m]=n #完成随机值与left交换
    if(left>=right):
        return L[left]
    if(left<=right):
        i=left
        j=right
        key=L[left]
        
        while i<j:
            while i < j and key<=L[j]:
                j-=1
            L[i]=L[j]#从右往左找到一个比key小的，将其赋值给基准值
            while i<j and L[i]<=key:
                i+=1
            L[j]=L[i]#从左往右找到一个比key大的，将其赋值给
        L[i]=key
        #已完成左侧比key小，右侧比key大
        if(len(L)%2==0 and i==int(len(L)/2)-1):
            return key
        elif(len(L)%2!=0 and i==int(len(L)/2)):
            return key
        if(i>int(len(L)/2)-1):
            return look_for(L,left,i-1)
        else:
            return look_for(L,i+1,right)
begin=time.clock()    
a=[6,1,2,7,3,4,5,8,9]
m=look_for(a,0,len(a)-1)
end=time.clock()
print(m)
print(end-begin)