Java 中 Collections.shuffle(List<?>)
方法的实现基于 Fisher–Yates shuffle 算法,核心的思想用几行代码即可表述:
1 | for (int i = size; i > 1; i--){ |
在 Collections.shuffle(List<?>)
方法实现中对不支持随机访问的数据结构进行了适配,如当前 List<?>
实现为链表时,在元素个数大于等于 5 个时,先将链表转换为支持随机访问的数据结构:数组,然后再对每个索引上的元素进行交换,最后再转换回链表,以保证算法运行时间为线性时间。
附 Collections.shuffle(List<?>)
源码:
1 | /* |