舍伍德(Sherwood)算法学习笔记Posted on
一.概念引入
设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。
有时候无法直接把确定性算法改造为舍伍德算法，这时候对输入洗牌。
下面是洗牌算法源代码：
import java.util.Random;public class Shuffle { main(String[] args) {int a[] = new int[]{1,2,4,5,8};/** Collections.shuffle(list)参数只能是list*/myShuffle(a);for(int i:a) {//犯了个低级错误，输出了a[i]，结果数组下标越界异常System.out.print(i+” “);}System.out.println();}myShuffle(int[] a) {int len = a.length;for(int i=0; i<len; i++) {Random r = new Random();j = r.nextInt(len);(i!=j) {temp = a[i];a[i] = a[j];a[j] = temp;}}}}
二.舍伍德思想解决迅雷2010年校招–发牌
问题描述：52张扑克牌分发给4人，每人13张，要求保证随机性。已有随机整数生成函数rand()，但开销较大。请编写函数实现void deal(int a[],int b[],int c[],int d[])，扑克牌用序号0-51表示，分别存在大小为13的a，b,c,d四个数组中，要求尽可能高效。
import java.util.Random;public class Poker {/** 这道题确实不怎么明白，直接初始化后洗牌算法不得了* 不过解答只是替换nextInt，直接线性同余了，交换次数也减少了* 交换次数是随机产生的array[] = new int[52]; main(String[] args) {for(int i=0; i<array.length; i++) {array[i] = i;}int a[] = new int[13];int b[] = new int[13];int c[] = new int[13];int d[] = new int[13];deal(a,b,c,d);(int i=0; i<13; i++) {System.out.println(a[i]+” “+b[i]+” “+c[i] + ” “+d[i]);}}deal(int[] a, int[] b, int[] c, int[] d) {int m = 10;q = 10;Random r = new Random();(int i=0; i<num; i++) {m = m*p + q;m = m%(51-i);int j = 51 – m;if(i!=j) {swap(array,i,j);}}for(int i=0; i<13; i++) {a[i] = array[i];b[i] = array[i+13];c[i] = array[i+26];d[i] = array[i+39];}}swap(int[] a, int i, int j) {temp = a[i];a[i] = a[j];a[j] = temp;}}
三.舍伍德思想快拍算法解决第k小问题
import java.util.Arrays;import java.util.Random;/* * 目前还不知道找不到咋办？ * 这是个愚蠢的问题，肯定找得到，因为是找第k个 * 只需要判断k的合法性，香港空间，在selectK函数外部 SherwoodQsort {/***舍伍德思想快拍算法解决第k小问题(就是正所第k个)*记得看算法导论时提出一个算法是维护一个k大小数组，扫描原有数组不断插入排序，最后第k个元素就是所求*这样等于说是求出了前k小，并不仅仅是第k小，肯定效率不如下面。 main(String[] args) {a[] = new int[]{1,8,4,9,0,32,45,27,6,5,65535};int b[] = new int[a.length];b = Arrays.copyOf(a, a.length);//Collections.sort只对list可用Arrays.sort(b);System.out.print(“待排序数组排序后为：”);for(int i:b) {System.out.print(i+” “);}System.out.println();int k = 5;ans = selectK(a,0,a.length-1,k);System.out.print(“第k(5)个数组元素是:”+ans+”\n”);}selectK(int[] a, int left, int right, int k) {((left>=right) {return a[left];}r = createRandom(left,right);int i = left;/** 注意：数组a的最后一项65535表示最大值,是特地加上去的* 产生的r最多是a.length-1(因为right=a.length-1)* 这样下面的j=r+1才绝对不会越界，大多是这么处理的(i!=r) {//注意是和r交换swap(a,a[i],a[r]);}p = a[left];(true) {(a[++i]<p);while(a[–j]>p);(i>=j) {break;}swap(a,i,j);}//交换，完成一次划分a[left] = a[j];a[j] = p;int t = j-left+1;if(t==k) {return p;//或者a[j]}right = j – 1;}else {/** 原来这个顺序错了，虚拟主机，结果一直数组下标越界*/k = k – t;left = j+1;}}}swap(int[] a, int i, int j) {temp = a[i];a[i] = a[j];a[j] = temp;}createRandom(int left, int right) {Random r = new Random();return r.nextInt(right-left+1) + left;}}
四.舍伍德随机化思想搜索有序表
问题描述举例
搜索思想
随机抽取数组元素若干次，从较接近搜索元素x的位置开始做顺序搜索。
任何的限制，都是从自己的内心开始的。
