Java中打乱一个数组的2种公平算法分享
公平算法，打乱数组
这是前几天面试的时候遇见的一道题目，看到这个题首先想到了洗牌程序：
方法一：洗牌程序原理
在java.util包中的Collections类中的shuffle方法，现在手工实现以下代码如下：
packagetest.ms;
importjava.util.Random;
publicclassRedistribute2{
publicstaticvoidmain(String[]args){
//definethearray
int[]s={1,5,4,3,6,9,8,7,0,8,5,6,7,2};
//beforeredistributeoutput
System.out.println("beforeredistribute:");
for(inti=0;i<s.length;i++){
System.out.print(s[i]+"");
}
//invokethemethod
shuffle(s,newRandom());
System.out.println();
//afterredistributeoutput
System.out.println("afterredistribute:");
for(inti=0;i<s.length;i++){
System.out.print(s[i]+"");
}
}
//usingtherandomgettherandomnumber
publicstaticvoidshuffle(int[]array,Randomrandom){
for(inti=array.length;i>=1;i--){
swap(array,i-1,random.nextInt(i));
}
}
//thetwonumberswapinthearray
publicstaticvoidswap(int[]array,inti,intj){
inttemp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
swap方法用于交换数组中的两个数， shuffle方法用于根据随机源生成的随机数进行交换。
输出结果如下：
beforeredistribute: 15436987085672 afterredistribute: 98780616552374
方法二：生成随机索引交换
该方法利用Set集合的特性：Set集合中的数据不重复，生成数组的索引，根据生成的索引进行交换数据。
实现方式如下：
packagetest.ms;
importjava.util.Iterator;
importjava.util.LinkedHashSet;
importjava.util.Random;
importjava.util.Set;
publicclassRedistribute{
publicstaticvoidmain(String[]args){
int[]s={1,5,4,3,6,9,8,7,0,8,5,6,7,2};
redistribute(s);
}
publicstaticvoidredistribute(int[]s){
Randomrandom=newRandom();
Set<Integer>set=newLinkedHashSet<Integer>();
//redistributetheindex
while(true){
intt=random.nextInt(s.length);
set.add(t);
if(set.size()==s.length)
break;
}
System.out.println("beforeredistribute:");
for(inti=0;i<s.length;i++){
System.out.print(s[i]+"");
}
System.out.println();
System.out.println("redistributetheindex");System.out.println(set);
int[]out=newint[s.length];
intcount=0;
for(Iterator<Integer>iterator=set.iterator();iterator.hasNext();){
out[count]=s[iterator.next()];
count++;
}
//outtheresult;
System.out.println("afterredistribute:");
for(inti=0;i<s.length;i++){
System.out.print(out[i]+"");
}
}
}
这个方法首先生成索引，然后根据新索引进行数据交换，代码都写在main方法里了，不是太好。
生成结果如下：
beforeredistribute: 15436987085672 redistributetheindex [6,2,9,1,10,5,11,4,12,3,7,8,0,13] afterredistribute: 84855966737012
关于随机数的生成，用了java类中的随机数的生成的工具类，这个随机类需要单独研究一下。