java实现洗牌算法——详解Collections.shuffle()

洗牌题目描述

请撰写一个简单的洗牌程序，显示洗牌结果如下：

题目分析：相当于实现52个数字随机打乱顺序（没有王）。

代码实现

@SpringBootApplication
public class HelloWorldMainApplication {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        //将52个数字放入一个List中
        for(int i=0;i<52;i++){
            list.add(i);
        }
        Collections.shuffle(list); //随机打乱list数据

        //按要求输出
        String[] flowers = {"桃", "砖", "梅", "心"};
        String[] numbers = {"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
        for(int i=0;i<52;i++){
            System.out.print(flowers[list.get(i)%4] + numbers[list.get(i)/4] + " ");
            if(i%13==12){
                System.out.print('\n');
            }
        }
    }
}

其实洗牌的功能，主要依靠封装在Collection类中的shuffle()函数来对List对象打乱顺序，在下面我们会对这个函数进行详解。结果如下：

Collection.shuffle()

主要思想如下图，总元素n个，按照从后往前的每个元素i进行操作。

• 从包括元素i之前的所有元素随机取一个元素j（有可能i==j，如图所示的最后一步操作，毕竟也要允许有洗牌之后顺序不变的情况）
• 两个元素互相交换
• 直到洗牌完毕，需要n-1步操作。

我们看一下代码，代码解释在注释里，swap方法里为什么新建了一个局部变量放列表对象的引用？主要是为了规避泛型的缺点，详细在另一篇博客里，传送门。大致内容是这样的，final不final不重要，主要是为了建立一个局部变量，如果不使用局部变量，而直接使用形参list，会报错。如果直接使用泛型，在调用函数的时候也会报错。这是最佳的解决方法。如果有人这里不懂，可以评论，我可以再写个博客解释。

    public static void shuffle(List<?> list) {
        Random rnd = r;
        if (rnd == null)
            r = rnd = new Random(); // 用于取随机数
        shuffle(list, rnd);
    }

   public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
    
        /**
         * 如果不是实现RandomAccess的类的对象，如链表LinkedList，直接get和set值时时间消耗大
         * 这里选择将list的值放到一个Object数组里，但这样空间消耗大，在某些比较短的list里
         * 通过阈值SHUFFLE_THRESHOLD控制时间消耗和空间消耗的平衡
         */
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                //rnd.nextInt(i)可以随机取到[0,i-1]间的某一个数
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // 对arr进行洗牌
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }

    public static void swap(List<?> list, int i, int j) {
        // 注意，这里使用中间变量l，来规避泛型通配符的缺点
        final List l = list;
        l.set(i, l.set(j, l.get(i)));
    }