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类中的随机数的生成的工具类,这个随机类需要单独研究一下。