① 先判断是否需要进行随机划分即（ 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)