舍伍德算法c

⑴ 哪位大神能指教下MO的排序问题

1.出现的问题是如果本来是顺序或倒序，那么排序的时间最长
排序的次数与初始排序序列有关，
修正方法:
加个随机函数，随机选择一个数与第一个数交换，把该数作为一个分区元素
这句是舍伍德算法
2.
排序的次数与初始排序序列有关.
3.
nlog(n)

⑵ 舍伍德算法的基本思想

设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为这显然不能排除存在x∈Xn使得 tA(x)>>tA(n)的可能性。
希望获得一个概率算法B，使得对问题的输入规模为n的每一个实例均有
这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。
舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。

⑶ 有哪些随机数算法呢

1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度
随着计算时间的增加而不断地提高。
2、拉斯维加斯算法（LasVegas）：要么给出问题的正确答案，要么得不到答案。反复求解多次，可
使失效的概率任意小。
3、蒙特卡罗算法（MonteCarlo）：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次
都进行随机选择，可使不正确答案的概率变得任意小。
4、舍伍德算法（Sherwood）：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很
坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。

⑷ 舍伍德算法的3数组实现链表

在不包含指针的程序没汁语言如VB中，可以采用数组来实现链表，实现了“虚假”的指针操作。但就是这种“虚假”指针，恰恰不仅弥补某些指针的某些缺结，还发挥了这种“虚假”指针的优点。采用这种数据结构，抛弃了顺序存储在插入运算中需要移动大量元素的缺点。采用这种数据结构，利用,舍伍德算法进行查找、插入和删除操作，其效率在传统的顺序存储和链式存储之间。
在所有的程序设计语言中都有数组，可以利用两个数组
m_pData和m_pLink来表示所给的含有多个元素的有序集。用m_pData存储有序链表的数据，用m_pLink存储有序链表的数据元索的直接后继的指针(在数组中的索引号)。m_pLink[O]指向有序链表的第一个元素，换句话说，m_pData[m_plink[0]]是有序链表中的最小元素。一般来说，如果m_pData[i】是有序链表中的第k个元素，则m_pData[m_plink[i]]是有序链表中的第k+1个元素。有序链表的有序性表现在：对于任意的I≤i≤n，有m_pData[i]≤m_pData[m_plink[i]]。有序链表中的最大元素m_pData[k]有m_plink[k]-O(无后继，指向第零个结点，第零个结点是监视哨)且m_pDaIa[0]为一个大数。
倘若采用顺序搜索的方式在这种有序链表中查找指定的元素，每次查找与有序链表建立的顺序有关，此时采用舍伍德算法可以消除这种联系。
利用数组下标的索引性质，可以设计一个随机化的搜索算法，以改进搜索的时间复杂性。该算法的基本思想是随机选取数组元素若干次，从较接近搜索元素x的位置开始进行顺序查找，而没有必要从有序链表的开始位置进行搜索，从而较大幅度地提高查找效率。
遗憾的是在STL容器类中的Voctor类采用顺序存储，List类采用链式存储，并没有这样的一种数据结构一用数组模拟有序链表。模仿标准STL中的类模板的实现，我们编制了一个类模板COrderList，并实现了用舍伍德算法进行查找、插入等算法。

⑸ 重精解除率怎么算

1）数值概率算法：常用于数值问题的求解，得到的往往是近似解（1）解的精度随计算时间的增加而提高（2）在许多情况下，计算出问题的精确解是不可能或没必要 2）蒙特卡罗算法：用于求解问题的准确解，可以求得问题的一个解，但该解未必正确（1）求得正确解的概率依赖于算法的计算时间多次执行蒙特卡罗算法，可以提高获得正确解的概率（2）无法有效判定所得到的解是否肯定正确。 3）拉斯维加斯算法：不会得到不正确的解（1）有时找不到问题的解（2）找到正确解的概率随算法计算时间的增加而提高（3）用同一拉斯维加斯算法反复对问题实例求解足够多次，可使求解失败的概率任意小。 4）舍伍德算法：总能求解得到问题的一个解，而且所求得得解总是正确的。将确定性算法引入随机性改造成舍伍德算法，可消除或减少问题对于好坏实例间的差别。

⑹ 舍伍德算法总能得到问题的一个正确解吗

1.出现的问题是如果本来是顺序或倒序，那么排序的时间最长排序的次数与初始排序序列有关，修正方法:加个随机函数，随机选择一个数与第一个数交换，把该数作为一个分区元素这句是舍伍德算法2.排序的次数与初始排序序列有关.3.nlog(n)

⑺ 算法具有确定性,因此在写算法中一定不能包含随机数调用的函数

错的，这里举个例子吧：随机快速排序，每次随机取一个值作为排序分类标准把当前区间拆成两部分，但是最后它还是会排好序，是一个具有确定结果的算法，只是得到结果的过程随机。
希望能帮到你。

⑻ 舍伍德算法的4用类模板实现算法

用类模板实现的算法如下：
template<classType>
boolCOrderlist<Type>：：Search(Type x, int&index)
//搜索有序链袭中的指定元素x、并将其位置放在index变量中
{//mCnrrentNumber为当前有序链表中元素的个数，它为类模
//板CorderLisl的数据成员,m为随机搜索的次数；
int m=(int)sqrt(double(m_CurmntNumber));
int j;
index=O;
//m_LowBound为当前有序链表中最小元素的值．它为类模板
//CorderList的数据成员;
Type max=m_LowBound;
for(int i=l；i<=m，i++}
{j=randl();
//产生一个随机数j，在数组m_pData[]随机中找一个值
Type y-m—pDataU]：
If((max<y)&&(y<x))
//找最靠近查找元素x的索引位置Index
{max=y；
index=j；}
}
//从最靠近查找元素x的Index所指向的位置升妯进行顺序搜索
while(m_pData[m_pLink[index]]<x)
index=m_pLink[index]；∥指针后移
return(n_pData[m_pLink[indcx]==x)；//是否找到
}