舍伍德（Sherwood）算法进修笔记
添加时间:2013-7-27 点击量:
一.概念引入
设A是一个断定性算法，当它的输入实例为x时所需的策画时候记为tA（x）。设Xn是算法A的输入范围为n的实例的全部，则当题目的输入范围为n时，算法A所需的均匀时候为
。这显然不克不及打消存在x∈Xn使得的
可能性。获得一个随机化算法B，使得对题目的输入范围为n的每一个实例均有
。这就是舍伍德算法设计的根蒂根基思惟。当s（n）与tA（n）比拟可忽视时，舍伍德算法可获得很好的均匀机能。
概率算法的一个特点是对同一实例多次应用同一概率算法成果可能同。舍伍德算法（O（sqrt（n）），综合了线性表和线性链表的长处）总能求的题目的一个正确解，当一个断定性算法在最坏景象和均匀景象下差别较大时可在这个断定性算法中引入随机性将之成一个舍伍德算法；引入随机性不是为了打消最坏，而是为了削减最坏和特定实例的接洽关系性。比如线性表a的查找若是找10（独一无二），若是在a[0]则为O（1），若是最后一个则O（n），可见时间与输入实例有关，此时可引入随机性将之成一个舍伍德算法。
有时辰无法直接把断定性算法为舍伍德算法，这时辰对输入洗牌。
下面是洗牌算法源代码：
import java.util.Random;
public class Shuffle {
public static void 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（）;
}
private static void myShuffle（int[] a） {
int len = a.length;
for（int i=0; i<len; i++） {
Random r = new Random（）;
//直接Random.nextInt（len）提示静态办法里无法引用
int j = r.nextInt（len）;
//Collections.swap（list，i，j）必须是list类型
if（i!=j） {//本来没加这个前提
int 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，直接线性同余了，互换次数也削减了
互换次数是随机产生的
/
//为便利swap和deal函数应用
static int array[] = new int[52];
public static void 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）;
//如许输出便利
for（int i=0; i<13; i++） {
System.out.println（a[i]+ +b[i]+ +c[i] + +d[i]）;
}
}
private static void deal（int[] a， int[] b， int[] c， int[] d） {
int m = 10;
int p = 31;//须要素数
int q = 10;
Random r = new Random（）;
int num = r.nextInt（52）;//轮回次数
for（int i=0; i<num; i++） {
m = mp + 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];
}
}
private static void swap（int[] a， int i， int j） {
//互换是正确的
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
三.舍伍德思惟快拍算法解决第k小题目
import java.util.Arrays;
import java.util.Random;
/
今朝还不知道找不到咋办？
这是个笨拙的题目，必然找获得，因为是找第k个
只须要断定k的合法性，在K函数外部
/
public class SherwoodQsort {
/
舍伍德思惟快拍算法解决第k小题目（就是正所第k个）
记得看算法导论时提出一个算法是保护一个k大小数组，扫描原稀有组络续插入排序，最后第k个元素就是所求
如许便是说是求出了前k小，并不仅仅是第k小，必然效力不如下面。
/
public static void main（String[] args） {
//重视：数组a的最后一项默示最大值
int 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;
//重视：没把数组a的最后一项算进去
int ans = K（a，0，a.length-1，k）;
System.out.print（第k（5）个数组元素是:+ans+\n）;
}
private static int K（int[] a， int left， int right， int k） {
//重视right=a.length-1，没把数组a的最后一项算进去
while（true） {//更新left，right，k的值，直到找到为止
if（left>=right） {
return a[left];
}
//随机选择划分项，重视right=a.length-1，没把数组a的最后一项算进去
int r = createRandom（left，right）;
int i = left;
/
重视：数组a的最后一项65535默示最大值，是特地加上去的
产生的r最多是a.length-1（因为right=a.length-1）
如许下面的j=r+1才绝对不会越界，大多是这么处理惩罚的
/
int j = right+1;//right=a.length-1，就是数组最大项65535
if（i!=r） {
//重视是和r互换
swap（a，a[i]，a[r]）;
}
//实际上是partion函数，因为须要返回p和j，就不零丁写了
int p = a[left];//固然初试i=left，但下标不成是i
while（true） {
//直到左边小于划分项，右边大于为止
while（a[++i]<p）;
while（a[--j]>p）;
//写在互换之前
if（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]
}else if（t>k） {//在左边
right = j - 1;
}else {
/
本来这个次序错了，成果一向数组下标越界
/
k = k - t;
left = j+1;
}
}
}
private static void swap（int[] a， int i， int j） {
//互换是正确的
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static int createRandom（int left， int right） {
Random r = new Random（）;
return r.nextInt（right-left+1） + left;
}
}
四.舍伍德随机化思惟搜刮有序表
- 题目描述
用两个数组来默示所给的含有n个元素的有序集S。用value[0:n]存储有序集中的元素，link[0:n]存储有序集中元素在数组value中地位的指针（实际上应用数组模仿链表）。link[0]指向有序集中的第一个元素，集value[link[0]]是凑集中的最小元素。一般地，若是value[i]是所给有序集S中的第k个元素，则value[link[i]]是S中第k+1个元素。S中元素的有序性发挥解析为，对于随便率性1<=i<=n有value[i]<=value[link[i]]。对于凑集S中的最大元素value[k]有，link[k]=0且value[0]是一个大数。
- 举例
- 搜刮思惟
随机抽取数组元素若干次，从较接近搜刮元素x的地位开端做次序搜刮。
import java.util.Random;
public class SearchK {
public static void main（String[] args） {
int value[] = new int[]{65535，2，3，13，1，5，21，8};
int link[] = new int[]{4，2，5，6，1，7，0，3};
//查看是否存在元素k
int k = 13;
boolean flag = searchK（value，link，k）;
System.out.println（元素K（13）是否找到:+flag）;
}
private static boolean searchK（int[] value， int[] link， int x） {
int max = value[1];
int m = （int）Math.sqrt（value.length-1）;
Random r = new Random（）;
int index = 1;//这个初始化本是为了不让编译器报错（未初始化）
for（int i=0; i<m; i++） {
//随机产生元素地位，加1是为了不取到value[0]
int j = r.nextInt（value.length-1） + 1;
int y = value[j];
/
不熟悉打听max感化
value[index]必然小于x，所以下面才可以次序搜刮
/
if（max<y&&y<x） {
max = y;
index = j;
}
}
//次序搜刮
while（value[link[index]]<x） {
index = link[index];
}
return value[link[index]]==x;
}
}
/
不懂，n个元素
if（!searchK（value，link，x））
{
value[++n] = x;
link[n] = link[index];
link[index] = n;
}
//删除凑集中指定元素
template<class Type>
void OrderedList<Type>::Delete（Type k）
{
int index;
if（searchK（value，link，x））
{
int p = link[index];
if（p == n）
{
link[index] = link[p];
}
else
{
if（link[p]!=n）
{
int q = SearchLast（）;
link[q] = p;
link[index] = link[p];
}
value[p] = value[n];//删除元素由最大元素来弥补
link[p] = link[n];
}
n--;
}
}
/
五.舍伍德算法解决跳跃表题目
舍伍德型算法的设计思惟还可用于设计高效的数据布局，进步有序链表效力的一个技能是在有序链表的项目组结点处增设附加指针以进步其搜刮机能。在增设附加指针的有序链表中搜刮一个元素时，可借助于附加指针跳过链表中若干结点，加快搜刮速度。这种增长了向前附加指针的有序链表称为跳跃表。
有空写吧……
六.随机抽题算法
共有n道题，请求以雷同概率随机抽取m道不反复试题。可以编号为1到n，围成一圈，每次抽取round，并出圈，下次再选到时辰忽视如此直到选好了m题；不过若是n斗劲大会占用斗劲多的时候，先解析出圈的影响，round出圈后小于round的编号不变，大于的编号减一；对于已经抽到的题目（共k道），存入数组并由小到大排好序，再次选择roundk+1，若是大于便是round1则roundk+1加1，一向进行斗劲到roundk，不过如许可能会死轮回，可以在中心断定，若是和roundi相等则加一过后若是小于roundi+1，则则直接插入已选题数组，不然和roundi+2斗劲，如此进行。
七.总结
很多题目还是没闹熟悉打听，主如果材料太少，我查万方和维普数据库统共找到不跨越10篇介绍舍伍德算法的，此中大项目组都是泛泛而谈。
遗留题目：搜刮有序表时怎么初始化link数组？value[0]为什么搞个无穷大？初试找index为什么是sqrt（n）？查了n多材料也没头绪，懂的伴侣给指导下。
文艺不是炫耀，不是花哨空洞的文字堆砌，不是一张又一张的逆光照片，不是将旅行的意义转化为名牌包和明信片的物质展示；很多时候它甚至完全不美——它嘶吼、扭曲，它会痛苦地抽搐，它常常无言地沉默。——艾小柯《文艺是一种信仰》
一.概念引入
设A是一个断定性算法，当它的输入实例为x时所需的策画时候记为tA（x）。设Xn是算法A的输入范围为n的实例的全部，则当题目的输入范围为n时，算法A所需的均匀时候为
概率算法的一个特点是对同一实例多次应用同一概率算法成果可能同。舍伍德算法（O（sqrt（n）），综合了线性表和线性链表的长处）总能求的题目的一个正确解，当一个断定性算法在最坏景象和均匀景象下差别较大时可在这个断定性算法中引入随机性将之成一个舍伍德算法；引入随机性不是为了打消最坏，而是为了削减最坏和特定实例的接洽关系性。比如线性表a的查找若是找10（独一无二），若是在a[0]则为O（1），若是最后一个则O（n），可见时间与输入实例有关，此时可引入随机性将之成一个舍伍德算法。
有时辰无法直接把断定性算法为舍伍德算法，这时辰对输入洗牌。
下面是洗牌算法源代码：
import java.util.Random;
public class Shuffle {
public static void 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（）;
}
private static void myShuffle（int[] a） {
int len = a.length;
for（int i=0; i<len; i++） {
Random r = new Random（）;
//直接Random.nextInt（len）提示静态办法里无法引用
int j = r.nextInt（len）;
//Collections.swap（list，i，j）必须是list类型
if（i!=j） {//本来没加这个前提
int 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，直接线性同余了，互换次数也削减了
互换次数是随机产生的
/
//为便利swap和deal函数应用
static int array[] = new int[52];
public static void 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）;
//如许输出便利
for（int i=0; i<13; i++） {
System.out.println（a[i]+ +b[i]+ +c[i] + +d[i]）;
}
}
private static void deal（int[] a， int[] b， int[] c， int[] d） {
int m = 10;
int p = 31;//须要素数
int q = 10;
Random r = new Random（）;
int num = r.nextInt（52）;//轮回次数
for（int i=0; i<num; i++） {
m = mp + 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];
}
}
private static void swap（int[] a， int i， int j） {
//互换是正确的
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
三.舍伍德思惟快拍算法解决第k小题目import java.util.Arrays;
import java.util.Random;
/
今朝还不知道找不到咋办？
这是个笨拙的题目，必然找获得，因为是找第k个
只须要断定k的合法性，在K函数外部
/
public class SherwoodQsort {
/
舍伍德思惟快拍算法解决第k小题目（就是正所第k个）
记得看算法导论时提出一个算法是保护一个k大小数组，扫描原稀有组络续插入排序，最后第k个元素就是所求
如许便是说是求出了前k小，并不仅仅是第k小，必然效力不如下面。
/
public static void main（String[] args） {
//重视：数组a的最后一项默示最大值
int 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;
//重视：没把数组a的最后一项算进去
int ans = K（a，0，a.length-1，k）;
System.out.print（第k（5）个数组元素是:+ans+\n）;
}
private static int K（int[] a， int left， int right， int k） {
//重视right=a.length-1，没把数组a的最后一项算进去
while（true） {//更新left，right，k的值，直到找到为止
if（left>=right） {
return a[left];
}
//随机选择划分项，重视right=a.length-1，没把数组a的最后一项算进去
int r = createRandom（left，right）;
int i = left;
/
重视：数组a的最后一项65535默示最大值，是特地加上去的
产生的r最多是a.length-1（因为right=a.length-1）
如许下面的j=r+1才绝对不会越界，大多是这么处理惩罚的
/
int j = right+1;//right=a.length-1，就是数组最大项65535
if（i!=r） {
//重视是和r互换
swap（a，a[i]，a[r]）;
}
//实际上是partion函数，因为须要返回p和j，就不零丁写了
int p = a[left];//固然初试i=left，但下标不成是i
while（true） {
//直到左边小于划分项，右边大于为止
while（a[++i]<p）;
while（a[--j]>p）;
//写在互换之前
if（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]
}else if（t>k） {//在左边
right = j - 1;
}else {
/
本来这个次序错了，成果一向数组下标越界
/
k = k - t;
left = j+1;
}
}
}
private static void swap（int[] a， int i， int j） {
//互换是正确的
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
private static int createRandom（int left， int right） {
Random r = new Random（）;
return r.nextInt（right-left+1） + left;
}
}
文艺不是炫耀，不是花哨空洞的文字堆砌，不是一张又一张的逆光照片，不是将旅行的意义转化为名牌包和明信片的物质展示；很多时候它甚至完全不美——它嘶吼、扭曲，它会痛苦地抽搐，它常常无言地沉默。——艾小柯《文艺是一种信仰》四.舍伍德随机化思惟搜刮有序表
- 题目描述
用两个数组来默示所给的含有n个元素的有序集S。用value[0:n]存储有序集中的元素，link[0:n]存储有序集中元素在数组value中地位的指针（实际上应用数组模仿链表）。link[0]指向有序集中的第一个元素，集value[link[0]]是凑集中的最小元素。一般地，若是value[i]是所给有序集S中的第k个元素，则value[link[i]]是S中第k+1个元素。S中元素的有序性发挥解析为，对于随便率性1<=i<=n有value[i]<=value[link[i]]。对于凑集S中的最大元素value[k]有，link[k]=0且value[0]是一个大数。
- 举例
- 搜刮思惟
随机抽取数组元素若干次，从较接近搜刮元素x的地位开端做次序搜刮。
import java.util.Random;
public class SearchK {
public static void main（String[] args） {
int value[] = new int[]{65535，2，3，13，1，5，21，8};
int link[] = new int[]{4，2，5，6，1，7，0，3};
//查看是否存在元素k
int k = 13;
boolean flag = searchK（value，link，k）;
System.out.println（元素K（13）是否找到:+flag）;
}
private static boolean searchK（int[] value， int[] link， int x） {
int max = value[1];
int m = （int）Math.sqrt（value.length-1）;
Random r = new Random（）;
int index = 1;//这个初始化本是为了不让编译器报错（未初始化）
for（int i=0; i<m; i++） {
//随机产生元素地位，加1是为了不取到value[0]
int j = r.nextInt（value.length-1） + 1;
int y = value[j];
/
不熟悉打听max感化
value[index]必然小于x，所以下面才可以次序搜刮
/
if（max<y&&y<x） {
max = y;
index = j;
}
}
//次序搜刮
while（value[link[index]]<x） {
index = link[index];
}
return value[link[index]]==x;
}
}
/
不懂，n个元素
if（!searchK（value，link，x））
{
value[++n] = x;
link[n] = link[index];
link[index] = n;
}
//删除凑集中指定元素
template<class Type>
void OrderedList<Type>::Delete（Type k）
{
int index;
if（searchK（value，link，x））
{
int p = link[index];
if（p == n）
{
link[index] = link[p];
}
else
{
if（link[p]!=n）
{
int q = SearchLast（）;
link[q] = p;
link[index] = link[p];
}
value[p] = value[n];//删除元素由最大元素来弥补
link[p] = link[n];
}
n--;
}
}
/五.舍伍德算法解决跳跃表题目
舍伍德型算法的设计思惟还可用于设计高效的数据布局，进步有序链表效力的一个技能是在有序链表的项目组结点处增设附加指针以进步其搜刮机能。在增设附加指针的有序链表中搜刮一个元素时，可借助于附加指针跳过链表中若干结点，加快搜刮速度。这种增长了向前附加指针的有序链表称为跳跃表。
有空写吧……
六.随机抽题算法
共有n道题，请求以雷同概率随机抽取m道不反复试题。可以编号为1到n，围成一圈，每次抽取round，并出圈，下次再选到时辰忽视如此直到选好了m题；不过若是n斗劲大会占用斗劲多的时候，先解析出圈的影响，round出圈后小于round的编号不变，大于的编号减一；对于已经抽到的题目（共k道），存入数组并由小到大排好序，再次选择roundk+1，若是大于便是round1则roundk+1加1，一向进行斗劲到roundk，不过如许可能会死轮回，可以在中心断定，若是和roundi相等则加一过后若是小于roundi+1，则则直接插入已选题数组，不然和roundi+2斗劲，如此进行。
七.总结
很多题目还是没闹熟悉打听，主如果材料太少，我查万方和维普数据库统共找到不跨越10篇介绍舍伍德算法的，此中大项目组都是泛泛而谈。
遗留题目：搜刮有序表时怎么初始化link数组？value[0]为什么搞个无穷大？初试找index为什么是sqrt（n）？查了n多材料也没头绪，懂的伴侣给指导下。
