乱序算法及C++函数

文章来源：http://hi.baidu.com/lujunqianglw/blog/item/270401ade85f891e4a36d6dc.html

转载自

最终编辑

我们经常看到排序的算法，但有的时候，也需要将某个有序的序列打乱顺序，就叫“乱序”吧。
按排序的定义，“乱序”应该是这样的：将一组记录（或者元素，本身可以是有序或者无序的）按照某
个域的值（称之为“排序码”）的随机次序重新排列的过程。
这里我们注意到无论是排序还是乱序，都是按某个域的值进行的。比如我们将一组数据存放在
某个数组中，需要进行乱序，则只需要将数据下标（1-N）进行乱序后，再依次输出数组的内容，就可以
达到乱序的目的了。
一提到随机，当然免不了需要用到随机函数，这里并不打算讨论随机的深入算法，只说明随机
函数在乱序算法中的使用。随机函数一般都不是真正的随机，而是通过算法在某个范围内按某个分布函
数生成的随机数。在VB中，Rnd()函数可以生成0-1之间的随机小数，然后再通过运算得到想要的分布范
围；在C++中，使用rand()函数可以生成0-RAND_MAX（0x7ffff)之间的整数，也同样需要经过运算。当然
为了每次生成的随机数不同，在VB中使用Rnd()函数之前，要先用Randonize time 语句，使用当前时间作
随机种子；而在C++中，则可以用 srand((unsigned)time(NULL)); 来设置随机种子。要说明的是，随机种
子语句一般只用一次，多次使用反而会使随机函数"不随机"了。这里仅以C++为例，来写一个自定义的函数，
这个函数的作用是，输入整数a和b，随机生成[a,b]之间的整数（Echo注：这个[a,b]是指区间，即生成的数
是包含a和b的）。

//生成a,b 之间的随机整数
int Random (int a, int b)
{
int area=0;
int ret=0;
//生成区间
area=b-a+1;
ret=(int)(rand()*area/(1.0 * RAND_MAX)+a);
return ret;
}

说完了随机函数，我们再来看看如何乱序。假设我们先把需要乱序的数保存在一个数组A中，另外
建一个与A数组一样大小的数组B，来存放乱序后的结果。
算法一：这是经常看到的算法
(1)从A中随机抽取一个数；
(2)查一下B中是否已经有这个数
(3)如果B中没有，则把这个数放到B中；如果有表示重复了,再回到(2)
(4)直到B中的数组满了,结束;

这里存在两个问题：
1、在步骤（2）中去检查已经随机抽出来的数是不是有被抽过，这本身就存在问题，因为有可能在A中某个数
本身就是出现多次，比如这样一个序列："1,2,4,5,2,3,4,7,22" 数字2和4都出现的2次。所以这种判断方式只能
用于不出现重复的情况；
2、设想一下随机抽取最后一个数的情况，假设一个序列“1,2,3,4,5,6,7" 随机抽取6次后得到"5,3,1,2,4,7"
就剩下最后一个数字6了，但是这时在第（1）步中是随机抽取一个数，程序会在1-7中随机选择一个数，有可能
重复了很多次后仍没有选出6这个数，但实际上，这时已经不需要再随机了，只有6才可以被抽取。
通过算法一我们可以看出乱序不能以抽取的数据内容作为标准，而应该是这样一种方式：先将需要乱序
的数放到临时数组A中，然后:
算法二:
(1)从A中随机抽取一个数K，并放入B中；
(2)从A中把K删除；
(3)回到第（1）步，直到A中为空
使用这种方式，可以不需要理会A中数据是否重复，同时，每次到步骤（2）后，A中的数据个数就少1，也不需要
进行判断。这其实也符合实际生活中我们打乱顺序的过程：随机抽一张牌，放到外面；再随机抽一张牌，放到原
刚才那张的上面，直到结束。
让我们看看C++的程序，下面的程序是给直接在数组中进行乱序，每次随机选择一个位置，把它与最后一
个位置的数据对换，直到结束。

//生成0-n不重复的随机数字
void GetRand(int n,int arr[])
{
int i;
int p;
int tmp;
for (i=0;i<=n;i++)
{
   arr[i]=i;
}

for (i=n;i>0;i--)
{
   p=Random(0,i);
   tmp=arr[p];
   arr[p]=arr[i];
   arr[i]=tmp;
}
}

在主程式调用上面函数时，需要先用 srand((unsigned)time(NULL));语句来设置随机种子。生成随机数组后，
即可使用下标的方式引用数据了。测试的主程式没有写，有兴趣的朋友可以自己完成，其实只要输出arr[]的值
就看以看到乱序后的结果了。
Echo备注：GetRand函数里没有检查arr[]的大小，有可能会出现错误，请保证arr下标为0-n,即大小为n+1。