Shuffle算法学习

Fisher–Yates Shuffle算法

  • 思想:算法思想就是从原始数组中随机抽取一个新的数字到新数组中
  • 复杂度:O(n^2)
  • 实现
    private static final int[] shuffledNums = new int[]{...};

	/**
     * Fisher-Yates Shuffle算法
     * @return
     */
    public static int[] shuffle() {
        Random random = new Random();
        List<Integer> list = new ArrayList<>();
        //1.初始化新数组
        for (int i = 0; i < shuffledNums.length; i++) {
            list.add(shuffledNums[i]);
        }

        int x, j = 0;
        //2.从还没处理的数组（假如还剩k个）中，随机产生一个[0, k)之间的数字p (假设数组从0开始)
        //3.剩下的k个数中把第p个数取出
        //重复2和3,直到数字取完
        for (int i = list.size() - 1; i >= 0; i = list.size() - 1) {
            x = random.nextInt(i + 1);
            shuffledNums[j++] = list.get(x);
            list.remove(x);
        }
        //返回的数组为打乱的数组
        return shuffledNums;
    }

Knuth-Durstenfeld Shuffle算法

  • 思想:Fisher–Yates Shuffle的改进,每次从未处理的数据中随机取出一个数字，然后把该数字放在数组的尾部，即数组尾部存放的是已经处理过的数字。在原始数组上对数字进行交互，省去了额外O(n)的空间。
  • 复杂度:O(n)
  • 实现
private static final int[] shuffledNums = new int[]{...};

    public static int[] shuffle() {
        Random random = new Random();
        int x, t;
        //1. 从未处理的数据中随机获取一个数字
        //2. 把该数字放在数组的尾部，即尾部的数据已被处理了
        //3. 从尾部开始处理，当处理完index=0的数据,得到洗牌后的数据
        for (int i = shuffledNums.length - 1; i > 0; i--) {
            x = random.nextInt(i + 1);
            t = shuffledNums[i];
            shuffledNums[i] = shuffledNums[x];
            shuffledNums[x] = t;
        }
        return shuffledNums;

    }