问题描述：给定一个int数组，要求返回一个数组，内容全部随机打乱
蛮力算法，（随机抽取一张牌放到某一位置，通过复制实现）：
public class Shuffle { //旧牌的备份 int[] backup; //新牌 int[] shuffled; //数组长度，牌数 int n; //构造器，初始化 public Shuffle(int []nums){ backup = nums; n = nums.length; shuffled = new int[n]; } //洗牌 public int[] shuffled(){ //随机取牌，放到位置i（位置从0到n-1） for(int i = 0;i<n;i++){ int k = rand(); /** * 此处省略一段代码， * 此段代码用于存储历次的牌k，并从中搜寻本次k值，若没搜到，则进行下一步操作 * if(k 不属于 已存牌集合） * { * shuffled[i]=backup[k]; * } */ shuffled[i]=backup[k]; } return shuffled; } //随机取牌 public int rand(){ return (int)(n*Math.random()); } public static void main(String[] args) { // write your code here int[] a = {1,2,3,4,5}; Shuffle shuffle = new Shuffle(a); shuffle.shuffled(); } }当 i = x 时，已存储的数值为x个，random出未存储的值的概率为(n-x)/n
也就是说，随机次数的期望为 1+x/n+(x/n)^2 + ……= n/(n-x)，比较次数的期望为x/(n-x)
总的随机次数为 1 + n/(n-1) +n/(n-2) + ... + n, 总的比较次数为1/(n-1) + 2/(n-2) + ... + (n-1)/(n - n + 1)
可以看到，存储以及查询k非常耗时
需要进行改进，如果能跳过存储比较这一步就好了。
改进算法（随机抽取一张牌放到给定位置，通过交换牌的位置实现）
小小程序师 在博客中给出的优化方法如下 http://blog.csdn.net/geniusluzh/article/details/8443682
该算法是C语言实现的
void MySwap(int &x, int &y) { int temp = x; x = y; y = temp; } void Shuffle(int n) { for(int i=n-1; i>=1; i--) { MySwap(num[i], num[rand()%(i+1)]); } } 可以看到，该算法从数组的最后一张牌起做交换。先换最后的一张牌。通过取i+1的模，得到这一张牌可以和任意一张牌进行交换（包括它本身），也就是说，实现了将任意一张牌插入到最后一个位置（对应数组的最大索引）。
接着，i--, 这个时候的交换等价与“将剩下的n-1张牌随意抽一张放在倒数第二的位置”。
依次类推就实现了随机洗牌的效果，已经洗好的牌就放在最后的位置不动，其他的牌进行交换（洗牌）。
在时间复杂度O(n)和空间复杂度上，都要比蛮力算法优秀。
最后给出java实现（由于java没有指针，不知道怎么用方法实现swap）
public class ShuffleBeta { public int[] nums; int n; public ShuffleBeta(int[] nums){ this.nums = nums; n = nums.length; } //洗牌 public int[] shuffled(){ for(int i = n -1; i>=1;i--){ int tmp = nums[i];//第三者 int rd = rand(i);//随机数 nums[i]=nums[rd]; nums[rd]=tmp;//交换 } return nums; } public int rand(int i){ return (int)(i*Math.random()); } }
