E[Tn]的上限： Tisl,k n -1+max{Tis<l,k,Tissl,k-15<1-1) =n -1+max{Tj-1,k,Tn-j,k-j} <n-1+max{Tj-1,Tn-j). 算法第一步的 ≤-1⑥ max{ET-小，ETn-} a选择为第j个 小的数的概率 1n ≤n-1+ ∑E [TmarU--1,n-】 是1/n =1 -1 ≤n-1+ ETl. 2 =「n/21E[Tn ]的上限： 算法第一步的 ai选择为第j个 小的数的概率 是1/n