这里介绍洗牌算法中常用的Fisher-Yates Shuffle算法，及其相关的变体——Sattolo 算法

Fisher-Yates Shuffle算法

Fisher-Yates Shuffle算法（又被称为Knuth Shuffle 算法），是一种用于随机打乱元素顺序的高效洗牌算法。其保证生成的随机排列是等概率的。而且该算法是一种原地算法，对于大数据集场景也十分有效。该算法最初由Ronald Fisher、Frank Yates于1938年提出

基本原理：

对于一个长度为size的数组，从第一个元素开始处理
对于当前正在处理的元素 array[currentIndex］而言，生成一个范围为［currentIndex, size-1］的随机数 random
对currentIndex、random位置上的元素进行交换
从前往后继续处理下一个元素 array[currentIndex+1］
重复上述步骤2~4，直到准备处理数组中最后一个元素时停止

import java.util.Arrays;
import java.util.Random;

public class FisherYatesShuffle {
    public static void shuffle(int[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int size = array.length;
        Random random = new Random();
        for (int currentIndex = 0; currentIndex < size - 1; currentIndex++) {
            // 生成一个位于 [currentIndex，size-1］范围内的随机数
            int randomIndex = random.nextInt(currentIndex, size);
            
            // 交换 currentIndex、randomIndex 位置上的元素
            int temp = array[currentIndex];
            array[currentIndex] = array[randomIndex];
            array[randomIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] array = new int[]{11, 33,55,22,44,66};
        System.out.println("array before shuffle: "+ Arrays.toString(array));
        shuffle(array);
        System.out.println("array after shuffle: "+ Arrays.toString(array));
    }
}

Sattolo 算法

该算法其实是Fisher-Yates Shuffle算法的变种，其同样保证生成的随机排列是等概率的。与Fisher-Yates Shuffle算法相比，该算法的不同之处在于第2步。即其生成的随机数在[currentIndex+1, size-1］区间。即保证每个元素的新位置与其原始位置一定是不同的

import java.util.Arrays;
import java.util.Random;

public class SattoloShuffle {
    public static void shuffle(String[] array) {
        if (array == null || array.length <= 1) {
            return;
        }

        int size = array.length;
        Random random = new Random();
        for (int currentIndex = 0; currentIndex < size - 1; currentIndex++) {
            // 生成一个位于 [currentIndex+1，size-1］范围内的随机数
            int randomIndex = random.nextInt(currentIndex+1, size);

            // 交换 currentIndex、randomIndex 位置上的元素
            String temp = array[currentIndex];
            array[currentIndex] = array[randomIndex];
            array[randomIndex] = temp;
        }
    }

    public static void main(String[] args) {
        String[] array = new String[]{"A","D","E","C","B"};
        System.out.println("array before shuffle: "+ Arrays.toString(array));
        shuffle(array);
        System.out.println("array after shuffle: "+ Arrays.toString(array));
    }
}

事实上，该算法的排列结果是一个包含所有元素的单循环排列。例如，就上面的测试结果而言：
洗牌前：A, D, E, C, B
洗牌后：E, A, C, B, D

对于同一个位置而言，根据排列前后的元素建立映射关系：
A —>> E
D —>> A
E —>> C
C —>> B
B —>> D

我们随机挑选一个起始元素，按照上述的映射来进行跳转。会看到其不仅最终会回到起始元素，而且所有元素都会被遍历到。例如，我们挑选元素E作为起始元素，不难有：E ->> C ->> B —>> D —>> A —>> E

xyZGHio

洗牌算法之Fisher-Yates Shuffle/Sattolo算法

Fisher-Yates Shuffle算法

Sattolo 算法