Collections.shuffle(List)

Java 中 Collections.shuffle(List<?>) 方法的实现基于 Fisher–Yates shuffle 算法，核心的思想用几行代码即可表述：

for (int i = size; i > 1; i--){
  swap(arr, i - 1, rnd.nextInt(i));
}

在 Collections.shuffle(List<?>) 方法实现中对不支持随机访问的数据结构进行了适配，如当前 List<?> 实现为链表时，在元素个数大于等于 5 个时，先将链表转换为支持随机访问的数据结构：数组，然后再对每个索引上的元素进行交换，最后再转换回链表，以保证算法运行时间为线性时间。

附 Collections.shuffle(List<?>) 源码：

/*
 * Tuning parameters for algorithms - Many of the List algorithms have
 * two implementations, one of which is appropriate for RandomAccess
 * lists, the other for "sequential."  Often, the random access variant
 * yields better performance on small sequential access lists.  The
 * tuning parameters below determine the cutoff point for what constitutes
 * a "small" sequential access list for each algorithm.  The values below
 * were empirically determined to work well for LinkedList. Hopefully
 * they should be reasonable for other sequential access List
 * implementations.  Those doing performance work on this code would
 * do well to validate the values of these parameters from time to time.
 * (The first word of each tuning parameter name is the algorithm to which
 * it applies.)
 */
private static final int SHUFFLE_THRESHOLD        =    5;

/**
 * Randomly permutes the specified list using a default source of
 * randomness.  All permutations occur with approximately equal
 * likelihood.
 *
 * <p>The hedge "approximately" is used in the foregoing description because
 * default source of randomness is only approximately an unbiased source
 * of independently chosen bits. If it were a perfect source of randomly
 * chosen bits, then the algorithm would choose permutations with perfect
 * uniformity.
 *
 * <p>This implementation traverses the list backwards, from the last
 * element up to the second, repeatedly swapping a randomly selected element
 * into the "current position".  Elements are randomly selected from the
 * portion of the list that runs from the first element to the current
 * position, inclusive.
 *
 * <p>This method runs in linear time.  If the specified list does not
 * implement the {@link RandomAccess} interface and is large, this
 * implementation dumps the specified list into an array before shuffling
 * it, and dumps the shuffled array back into the list.  This avoids the
 * quadratic behavior that would result from shuffling a "sequential
 * access" list in place.
 *
 * @param  list the list to be shuffled.
 * @throws UnsupportedOperationException if the specified list or
 *         its list-iterator does not support the <tt>set</tt> operation.
 */
public static void shuffle(List<?> list) {
    Random rnd = r;
    if (rnd == null)
        r = rnd = new Random(); // harmless race.
    shuffle(list, rnd);
}

private static Random r;

/**
 * Randomly permute the specified list using the specified source of
 * randomness.  All permutations occur with equal likelihood
 * assuming that the source of randomness is fair.<p>
 *
 * This implementation traverses the list backwards, from the last element
 * up to the second, repeatedly swapping a randomly selected element into
 * the "current position".  Elements are randomly selected from the
 * portion of the list that runs from the first element to the current
 * position, inclusive.<p>
 *
 * This method runs in linear time.  If the specified list does not
 * implement the {@link RandomAccess} interface and is large, this
 * implementation dumps the specified list into an array before shuffling
 * it, and dumps the shuffled array back into the list.  This avoids the
 * quadratic behavior that would result from shuffling a "sequential
 * access" list in place.
 *
 * @param  list the list to be shuffled.
 * @param  rnd the source of randomness to use to shuffle the list.
 * @throws UnsupportedOperationException if the specified list or its
 *         list-iterator does not support the <tt>set</tt> operation.
 */
@SuppressWarnings({"rawtypes", "unchecked"})
public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object[] arr = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        // instead of using a raw type here, it's possible to capture
        // the wildcard but it will require a call to a supplementary
        // private method
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

Reference

384. 打乱数组