我做的google数组随机排序的算法

[腾讯的一道笔试算法题解答]假设有这样一种字符串，它们的长度不大于 26 ，而且若一个这样的字符串其长度为 m ，则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成，同时我们保证每个字母出现且仅出现一...+阅读

发信人: northor(追求理想的过程是曲折艰辛的!), 信区: Job

标题: 我做的google数组随机排序的算法

发信站: 瀚海星云 (2006年05月30日23:44:13 星期二), 站内信件 POST

由于一开始觉得这个题目不太好做,

就放在最后做了,

结果时间不够,只写了算法:

我考虑题干强调的是一定要随机,就是越乱越好,

于是我就联想到了一堆乒乓球在笼子里摇啊摇的,抽奖的过程,

这个过程应该算是符合题目的要求吧,

那么怎么用random函数来实现这个功能呢?

我又建立了三个int型数组,b[len],c[len],d[len]

首先N = len,乒乓球的个数是N,

然后摇奖:利用random产生0到N-1的随机数,

记作b[0],d[0]=b[0];

这是摇出的第一个球的号码,然后对c[len]赋值,

这个数组,我规定它的作用是对剩下的乒乓球标记,

因为摇出了一个球,剩下了N-1个，

而随机数只能在0开始的连续整数之间产生，

所以剩下的球的号码要是连续整数就可以继续摇了，

所以c[len]记录我对乒乓球的重新标号，

如果最初乒乓球的号码小于b[0],就保持原来的号码，

等于b[0],就让号码为N(作废），

大于b[0]的,全部减1，

这样剩下的N－1个乒乓球的标号就是0到N－2了，

然后产生利用random产生0到N-2的随机数，

对标记号码摇奖，利用摇出的乒乓球的标记号码b[1]，

查到它的真实号码d[1]，

这样第二个随机位置d[1]就产生了，

然后再根据b[1]给剩下的N－2个乒乓球重新标记，

如果乒乓球的标记号码小于b[1],就保持原来的标记号码，

等于b[1]，就让号码为N(作废），

大于b[1]不等于N的,全部减1，

大于b[1]等于N的,不变。

重新标记之后，产生0到N-3的随机数，

就产生了第三个乒乓球的随机号码b[2]，

反回去查询真实号码，得到d[2];

......

最后我们得到了d[len]这个数组，

可以让c[i]=a[d[i]];

然后再把c赋给a，

这样一个模拟乒乓球摇奖的随机过程就完成了，

如果有可能，可以看到a[len]

打乱后排列的顺序，

和一个一个地摇出乒乓球号码的概率分布是一致的。

期待高手点评，