第k小元素(Las Vegas) 随机算法 o在n个数中随机的找一个数A[i=x,然后将其余n-1 个数与x比较,分别放入三个数组中: oS(元素均<x),S2(元素均=x),S3(元素均>x) >若S≥k则调用 Select(,k) 若S<k但(+2)≥k,则第k小元素就是x; >否则有(s<k,调用Select(s,k-s-2)。 16第k小元素(Las Vegas) ◼ 随机算法  在n个数中随机的找一个数A[i]=x, 然后将其余n-1 个数与x比较，分别放入三个数组中：  S1 (元素均 < x), S2 (元素均=x), S3 (元素均 > x) ➢ 若|S1 |≥k 则调用Select(S1 ,k)； ➢ 若|S1 |<k 但(|S1 |+|S2 |)≥k，则第k小元素就是x； ➢ 否则有(|S1 |+|S2 |)< k，调用Select(S3 ,k-|S1 |-|S2 |)。 16