前言

排序问题实现过很多次了，但是如何保证随机的乱序呢？这就是洗牌问题了（Shuffle）

洗牌算法FisherYates原理

洗牌问题

Fisher-Yates shuffle算法

首先来看看Collection里面的方法

code：

	/**
	 * Created by ymk on 2019/3/28.
	 * 这个算法主要是用来实现洗牌算法的
	 */
	public class FisherYates {

	    public static void main(String[] args) {
	        Integer[] raw = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
	        List<Integer> pokers = Arrays.asList(raw);
	        Joiner joiner= Joiner.on(",");
	        System.out.println(joiner.join(pokers));
	        Collections.shuffle(pokers);
	        System.out.println(joiner.join(pokers));
	    }
	}

输出：

	1,2,3,4,5,6,7,8,9,10,11,12,13
	5,9,1,12,7,8,2,10,11,6,3,4,13

源码实现

    public static void shuffle(List<?> list) {
        Random rnd = r;
        if (rnd == null)
            r = rnd = new Random(); // harmless race.
        shuffle(list, rnd);
    }

    private static Random r;

	 @SuppressWarnings({"rawtypes", "unchecked"})
	    public static void shuffle(List<?> list, Random rnd) {
	        int size = list.size();
	        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
	            for (int i=size; i>1; i--)
	                swap(list, i-1, rnd.nextInt(i));
	        } else {
	            Object arr[] = list.toArray();

	            // Shuffle array
	            for (int i=size; i>1; i--)
	                swap(arr, i-1, rnd.nextInt(i));

	            // Dump array back into list
	            // instead of using a raw type here, it's possible to capture
	            // the wildcard but it will require a call to a supplementary
	            // private method
	            ListIterator it = list.listIterator();
	            for (int i=0; i<arr.length; i++) {
	                it.next();
	                it.set(arr[i]);
	            }
	        }
	    }

为什么优秀？

如果简单粗暴的随机抽取不够好呢？这就和昨天的钢条问题一样，在简单随机抽取的过程中就有可能出现重复的位置，就等于浪费了一次抽取。而使用了Fisher-Yates方法之所以优秀，就是在原理上保证了不会出现浪费次数，每一次抽卡的范围都在慢慢变小

自己实现

	package Shuffle;
	import com.google.common.base.Joiner;
	import java.util.*;

	/**
	 * Created by ymk on 2019/3/28.
	 * 这个算法主要是用来实现洗牌算法的
	 */
	public class FisherYates {

	    public static void byMyWayFisherYates(Integer[] raw) {
	        Random rnd = new Random();
	        //nextInt(n)生成的值范围是[0,n)的
	        for (int i = raw.length; i>1; i--) {
	            swap(raw,i-1,rnd.nextInt(i));
	        }
	    }


	    public static void swap(Integer[] raw, int i, int j) {
	        Integer temp = raw[i];
	        raw[i] = raw[j];
	        raw[j] = temp;
	    }


	    public static void main(String[] args) {
	        Integer[] raw = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
	        List<Integer> pokers = Arrays.asList(raw);
	        Joiner joiner = Joiner.on(",");
	        System.out.println(joiner.join(pokers));
	        Collections.shuffle(pokers);
	        System.out.println(joiner.join(pokers));

	        Integer[] newRaw = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
	        System.out.println(joiner.join(newRaw));
	        byMyWayFisherYates(newRaw);
	        System.out.println(joiner.join(newRaw));
	    }
	}