输入进行随机洗牌,同样可收到舍伍德算法的效果。例如,对于确定性选择算法,可以用下面的洗牌算法shuffle将数组a中元素随机排列,然后用确定性选择算法求解。这样做所收到的效果与舍伍德型算法的效果是一样的。?public static void parable []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);? }?}Р8Р跳跃表Р舍伍德型算法的设计思想还可用于设计高效的数据结构。?如果用有序链表来表示一个含有n个元素的有序集S,则在最坏情况下,搜索S中一个元素需要(n)计算时间。?提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时,可借助于附加指针跳过链表中若干结点,加快搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。?应在跳跃表的哪些结点增加附加指针以及在该结点处应增加多少指针完全采用随机化方法来确定。这使得跳跃表可在O(logn)平均时间内支持关于有序集的搜索、插入和删除等运算。Р9Р跳跃表Р在一般情况下,给定一个含有n个元素的有序链表,可以将它改造成一个完全跳跃表,使得每一个k级结点含有k+1个指针,分别跳过2k-1,2k-1-1,…,20-1个中间结点。第i个k级结点安排在跳跃表的位置i2k处,i0。这样就可以在时间O(logn)内完成集合成员的搜索运算。在一个完全跳跃表中,最高级的结点是logn级结点。Р完全跳跃表与完全二叉搜索树的情形非常类似。它虽然可以有效地支持成员搜索运算,但不适应于集合动态变化的情况。集合元素的插入和删除运算会破坏完全跳跃表原有的平衡状态,影响后继元素搜索的效率。Р10
全文预览
