以期望线性时间做选择 口基本思想:采用分治策略,借鉴快速排序的随机划分法,对输入 数组进行递归划分,但是只处理划分的一边 RANDOMIZED-SELECT(A, P, r,i) P ∥临界问题处理 then return Alp 3q← RANDOMIZED-PARTITION(A,P,r)进行划分,返回划分元下标 4k←q-p+1 ∥k=rank(A[qD)inAp,,r,返回划分元的序号 5 if i=k then return Algl: 7 else if i<k 8 then return RANDOMIZED-SELECT(A, P,g-1,i) else 10 return RANDOMIZED-SELECT( A, 9+1, r,i-k) 2021/1/26以期望线性时间做选择  基本思想：采用分治策略，借鉴快速排序的随机划分法，对输入 数组进行递归划分，但是只处理划分的一边。 2021/1/26 10 RANDOMIZED-SELECT ( A, p, r, i ) 1 if p = r // 临界问题处理 2 then return A[p] 3 q ← RANDOMIZED-PARTITION( A, p, r ) //进行划分，返回划分元下标 4 k ← q – p + 1 // k=rank(A[q]) in A[p,…,r], 返回划分元的序号 5 if i = k 6 then return A[q]; 7 else if i < k 8 then return RANDOMIZED-SELECT ( A, p, q - 1, i ) 9 else 10 return RANDOMIZED-SELECT( A, q+1, r, i – k )