当前位置 博文首页 > 爱新觉罗?炒饭的博客：舍伍德型概率算法
舍伍德型概率算法可用于消除算法的时间复杂度与输入实例间的关系，
可用于分析确定性算法的平均时间复杂度。
舍伍德算法总是能求得问题的一个解，并且所求得的解总是正确的。但与其相对应的确定性算法相比较，舍伍德算法的平均时间复杂度并没有改进。
舍伍德算法并不是避免算法的最坏情况行为**，而是设法消除了算法的不同输入实例对时间性能的影响。**对所有输入实例而言，舍伍德算法的运行时间比较均匀，其时间复杂度与原有的确定性算法在平均情况下的时间复杂性相当。
随机洗牌算法
void shuffle(int cards[],int n) //n表示牌的数量
{
if(cards==NULL) //没有牌
return;
srand(time(0)); //便于后面使用rand()
int i,index;
for(i=0;i<n-1;i++)
{
//产生[i,n)间的一个随机数，表示cards数组的下标，保证前面已经确定的元素不会参加下面的选取
index=i+rand()%(n-i);
//交换cards[i]和cards[index]
int temp=cards[i];
cards[i]=crads[index];
cards[index]=temp;
}
}
随机快速排序
void quickSort(int r[],int low,int high)
{
srand(time(0));
int i,k;
if(low<high)
{
i=randomNum(low,high);//在[low,high]随机选取一个元素作为下标
swap(r[low],r[i]); //交换r[low]和r[i]的值
k=partition(r,low,high); //进行第一次划分
quickSort(r,low,k-1);
quickSort(r,k+1,high);
}
}
选择问题
int select(int r[],int low,int high,int k) //在r数组中选择第k小的元素
{
int i,s;
if(high-low<=k) //数组长度小于k，无法选择
return r[high];
else
{
i=randomNum(low,high);//在[low,high]随机选取一个元素作为下标
swap(r[low],r[i]);
s=partition(r,low,high);
if(s==k)
return r[s];//元素r[s]就是要找到元素
else if(k,s)
return select(r,low,s-1,k); //在前半部分继续查找
else
return select(r,s+1,high,k); //在后半部分继续查找
}
}
