洗牌算法(Shuffle)

洗牌算法(Shuffle)简单说,可以看成把一个数组的元素打乱。

假设要洗牌的数组是 ArrayA, 可以这么考虑:

1. 新建一个和 ArrayA 等常的空数组 ArrayB

2. 依次遍历 ArrayA 的元素,并随机分配到 ArrayB 的未赋值位置。

这个想法理论上可行,但实践很麻烦,不信试试怎么将一个值随机分配到 ArrayB 的未赋值位置?这步如果用代码表示,还是挺繁琐的。

洗牌算法有一个基本要求是,洗牌前后的元素集合不变但元素顺序会改变。尝试新的算法如下:

1. 依次遍历 ArrayA 的每个元素

2. 遍历到某个元素时,再随机选择一个元素,并与当前遍历到的元素交换

3. 以上执行到 ArrayA 的最后一个与元素。

代码如下:

    /**
     * 对数组洗牌
     *
     * @param array
     */
    void shuffle(int[] array) {
        int digitalCount = digitalCount(array.length);
        int base = (int) Math.pow(10, digitalCount); // digitalCount 计算整数的位数
        for (int i = 0; i < array.length; i++) {
            int denominator = (int) (Math.random() * base) % array.length;
            //exchange array[i] and array[denominator]
            int tmp = array[i];
            array[i] = array[denominator];
            array[denominator] = tmp;
        }
    }

完整的代码,参:

http://git.oschina.net/iridiumcao/iridiumonline/blob/master/helloalgorithm/src/main/java/info/iridiumcao/algorithm/shuffle/Shuffle.java

注:在 Java 集合 API 中也有现成的 Shuffle 工具了,比如:Collections.shuffle(...)