CodeCollection2018
8/12/2019 - 7:12 AM

随机打乱数组

首先从所有元素中选取一个数与第一个进行交换，然后在2至n中选择一个元素与第二个交换，直到最后一个元素。这样能确保每个元素在每个位置的概率都是1/n。每个元素在第一个的位置是1/n，这是毫无疑问的。第一次交换时，一个元素不在第一个位置的概率是(n-1)/n。所以当第二次交换时，一个元素在第二个位置的概率是(n-1)/n1/n-1=1/n。同时，一个元素不在第一个第二位置的概率是多少呢？很显然是1-1/n-1/n=(n-2)/n。那么在第三次交换时，一个元素在第三个位置的概率就是(n-2)/n1/(n-2)=1/n。依此类推……。

untitled
content_copyfile_download
public static int[] myShuffle(int [] num){
	    if(num==null || num.length==0) return new int[num.length];
	    Random random = new Random();
	    for(int k = 0; k < num.length; k++){
	        int s_num = random.nextInt(num.length-k)+k;
	        swap(num,k,s_num);
	    }
	    return num;
	}
	public static void swap(int [] x,int t,int i) {
		int temp = x[i];
		x[i] = x[t];
		x[t]=temp;
	}