Java中打乱一个数组的2种公平算法分享

2019-11-26 15:14:38

字体：大中小

来源：转载

供稿：网友

公平算法，打乱数组

这是前几天面试的时候遇见的一道题目，看到这个题首先想到了洗牌程序：

方法一：洗牌程序原理

在java.util包中的Collections类中的 shuffle方法，现在手工实现以下代码如下：

package test.ms;import java.util.Random;public class Redistribute2 {	public static void main(String[] args) {				//define the array 		int[] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2};				// before redistribute output		System.out.println("before redistribute:");		for(int i = 0 ; i<s.length; i++){			System.out.print(s[i]+" ");		}				// invoke the method 		shuffle(s,new Random());				System.out.println();				// after redistribute output		System.out.println("after redistribute:");		for(int i = 0 ; i<s.length; i++){			System.out.print(s[i]+" ");		}	}  	// using the random get the random number	public static  void  shuffle(int[] array, Random random){				for(int i = array.length; i >= 1; i--){						swap(array,i-1,random.nextInt(i));		}	}		// the two number swap  in the array	public static void swap(int[] array, int i , int j){	 		int temp = array[i];				array[i] = array[j];				array[j] = temp;	 			}}

swap方法用于交换数组中的两个数， shuffle方法用于根据随机源生成的随机数进行交换。
输出结果如下：

before redistribute:1 5 4 3 6 9 8 7 0 8 5 6 7 2 after redistribute:9 8 7 8 0 6 1 6 5 5 2 3 7 4

方法二：生成随机索引交换

该方法利用Set集合的特性：Set集合中的数据不重复，生成数组的索引，根据生成的索引进行交换数据。

实现方式如下：

package test.ms;import java.util.Iterator;import java.util.LinkedHashSet;import java.util.Random;import java.util.Set;public class Redistribute {		public static void main(String[] args) {		int[] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2};		redistribute(s);	}	public static void  redistribute(int[] s){		Random  random = new Random();				Set<Integer> set = new LinkedHashSet<Integer>();				// redistribute the  index		while(true){			int t =random.nextInt(s.length);			set.add(t);			if(set.size()== s.length)			break;		}		System.out.println("before redistribute:");		for(int i = 0 ; i<s.length; i++){			System.out.print(s[i]+" ");		}		System.out.println();		System.out.println("redistribute the index ");System.out.println(set);				int [] out = new int[s.length];				int count = 0;				for(Iterator<Integer> iterator = set.iterator(); iterator.hasNext();){			out[count] = s[iterator.next()];			count++;		}				// out the result;		System.out.println("after redistribute:");		for(int i = 0 ; i<s.length; i++){			System.out.print(out[i]+" ");		}	}	}

这个方法首先生成索引，然后根据新索引进行数据交换，代码都写在main方法里了，不是太好。

生成结果如下：

before redistribute:1 5 4 3 6 9 8 7 0 8 5 6 7 2 redistribute the index [6, 2, 9, 1, 10, 5, 11, 4, 12, 3, 7, 8, 0, 13]after redistribute:8 4 8 5 5 9 6 6 7 3 7 0 1 2

关于随机数的生成，用了java类中的随机数的生成的工具类，这个随机类需要单独研究一下。

上一篇：Java中的Vector和ArrayList区别及比较

下一篇：Java实现求小于n的质数的3种方法