8.5 Randomized Sorting Algorithm 问题的定义 随机算法 算法性能的分析 问题的定义 输入 S={x1, x2, , xn} 输出 排序的S 基本思想 采用随机抽样的方法确定集合的划分点 把集合划分为两个子集合 分别递归地在每个子集合上使用随机排序算法 随机算法 算法 1. 均匀等可能地在S中随机抽取一个样本y; 2. 比较S中每个元素, 把S划分为如下两个集合: