班舍伍德( Sherwood算法 复习学过的 Sherwood算法 1)线性时间选择算法 2)快速排序算法 有时也会遇到这样的情况,即所给的确定性算法无法直接改造成 舍伍德型算法。此时可借助于随机预处理技术,不改变原有的 确定性算法,仅对其输入进行随机洗牌,同样可收到舍伍徳算 法的效果。例如,对于确定性选择算法,可以用下面的洗牌算 法 shuffle将数组a中元素随机排列,然后用确定性选择算法求 解。这样做所收到的效果与舍伍德型算法的效果是一样的。 public static void shuffle(Comparable [a, int n) 随机洗牌算法 rnd= new Random for(int i=1; i<n; i ++)i int j=rnd random(n-i+1)+i; MyMath. swap(a, 1, j8 舍伍德(Sherwood)算法 复习学过的Sherwood算法： （1）线性时间选择算法 （2）快速排序算法 有时也会遇到这样的情况，即所给的确定性算法无法直接改造成 舍伍德型算法。此时可借助于随机预处理技术，不改变原有的 确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算 法的效果。例如，对于确定性选择算法，可以用下面的洗牌算 法shuffle将数组a中元素随机排列，然后用确定性选择算法求 解。这样做所收到的效果与舍伍德型算法的效果是一样的。 public static void shuffle(Comparable []a, int n) {// 随机洗牌算法 rnd = new Random(); for (int i=1;i<n;i++) { int j=rnd.random(n-i+1)+i; MyMath.swap(a, i, j); } }