洗牌算法(Shuffle)

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

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

新建一个和 ArrayA 等常的空数组 ArrayB
依次遍历 ArrayA 的元素，并随机分配到 ArrayB 的未赋值位置。

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

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

依次遍历 ArrayA 的每个元素
遍历到某个元素时，再随机选择一个元素，并与当前遍历到的元素交换
以上执行到 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(...)

FilesExpand file tree

Shuffle.md

Latest commit

History

Shuffle.md

File metadata and controls

洗牌算法(Shuffle)