公平算法，打乱数组
这是前几天面试的时候遇见的一道题目，看到这个题首先想到了洗牌程序：
方法一：洗牌程序原理
在java.util包中的Collections类中的 shuffle方法，现在手工实现以下代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
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方法 用于 根据随机源 生成的随机数进行交换。
输出结果如下：
|
1
2
3
4
|
before redistribute:1 5 4 3 6 9 8 7 0 8 5 6 7 2after redistribute:9 8 7 8 0 6 1 6 5 5 2 3 7 4 |
方法二：生成随机索引交换
该方法利用Set集合的特性：Set集合中的数据不重复，生成数组的索引，根据生成的索引进行交换数据。
实现方式如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
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方法里了，不是太好。
生成结果如下：
|
1
2
3
4
5
6
|
before redistribute:1 5 4 3 6 9 8 7 0 8 5 6 7 2redistribute 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类中的随机数的生成的工具类，这个随机类需要单独研究一下。
