Java面试题公平算法打乱数组(两种实现方式)

公平算法，打乱数组

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

方法一：洗牌程序原理

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

01.package test.ms; 02.

03.import java.util.Random; 04.

05.public class Redistribute2 {

06.public static void main(String[] args) { 07.

08.//define the array

09.int[] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2}; 10.

11.// before redistribute output

12.System.out.println(\"before redistribute:\"); 13.for(int i = 0 ; i17.// invoke the method 18.shuffle(s,new Random()); 19.

20.System.out.println(); 21.

22.// after redistribute output

23.System.out.println(\"after redistribute:\"); 24.for(int i = 0 ; i28.

29.// using the random get the random number

30.public static void shuffle(int[] array, Random random){ 31.

32.for(int i = array.length; i >= 1; i--){ 33.

34.swap(array,i-1,random.nextInt(i)); 35.} 36.} 37.

38.// the two number swap in the array

39.public static void swap(int[] array, int i , int j){ 40.

41.int temp = array[i]; 42.

43.array[i] = array[j]; 44.

45.array[j] = temp; 46. 47. 48.} 49.}

swap方法用于交换数组中的两个数， shuffle方法 用于 根据随机源 生成的随机数进行交换。

输出结果如下：

1.before redistribute:

2.1 5 4 3 6 9 8 7 0 8 5 6 7 2 3.after redistribute:

4.9 8 7 8 0 6 1 6 5 5 2 3 7 4

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

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

实现方式如下：

01.package test.ms; 02.

03.import java.util.Iterator;

04.import java.util.LinkedHashSet; 05.import java.util.Random; 06.import java.util.Set; 07.

08.public class Redistribute { 09.

10.public static void main(String[] args) { 11.int[] s = {1,5,4,3,6,9,8,7,0,8,5,6,7,2}; 12.redistribute(s); 13.}

14.public static void redistribute(int[] s){ 15.Random random = new Random(); 16.

17.Set set = new LinkedHashSet(); 18.

19.// redistribute the index 20.while(true){

21.int t =random.nextInt(s.length); 22.set.add(t);

23.if(set.size()== s.length) 24.break; 25.}

26.System.out.println(\"before redistribute:\"); 27.for(int i = 0 ; i30.System.out.println();

31.System.out.println(\"redistribute the index \");System.out.println(set); 32.

33.int [] out = new int[s.length]; 34.

35.int count = 0; 36.

37.for(Iterator iterator = set.iterator(); iterator.hasNext();){

38.out[count] = s[iterator.next()]; 39.count++; 40.}

41.

42.// out the result;

43.System.out.println(\"after redistribute:\"); 44.for(int i = 0 ; i这个方法首先生成索引，然后根据新索引进行数据交换，代码都写在main方法里了，不是太好。 生成结果如下：

1.before redistribute:

2.1 5 4 3 6 9 8 7 0 8 5 6 7 2 3.redistribute the index

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

6.8 4 8 5 5 9 6 6 7 3 7 0 1 2

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