数组的Shuffle操作

今天的题目:

实现Random Shuffle的功能,给你一个随机数发生器把一个数组里的元素乱序。

关于“随机乱序“这个概念,我自己的定义是1)新数列和就数列中元素排列的顺序不一样,是为乱序;2)乱序后不能以某种规律来恢复原序,是为随机。

我的思路:

随机从数组A中选一个数,将之作为输出数组的第一个元素,然后将这个元素从数组A中删除得到A’,再从 A’中随机选一个元素,将之作为输出数组的第二个元素。

如此循环下去,得到的输出数组就是一个随机大乱原有数组元素排序的新数组。

地里还有个思路:

for(int i=0; i<n; i++) swap(x[n],x[rand()%(n)]);

每次都用数组最后一个数,和前面随机位置的数交换。

这个思路比我的思路要简洁,节省了存储空间。而且因该也满足以上我对题目的理解。然后从这个算法还能衍生别的算法,比如先随到一个m,然后将原数列分成A[0]-A[m]和A[m+1]-A[n-1]两个数列,然后将两个数列分别按照上面的方法打乱顺序。

如果还想跟随机一点,那么不要用数组最后一个位置的数与之前的数交换,而是用数组中随机的一个位置作为一个交换位置,总是让这个位置上的数随机的同它之前或者之后的某一个数交换。