jdk的源码如下
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
一、首先是判断要打乱的list的属性:list的size和是否实现RandomAccess接口
如果list的size小于SHUFFLE_THRESHOLD(5) 或者 list实现了RandomAccess接口,则直接交换list内元素的位置。具体的交换策略如下:
令list的size为n, 从n-1位开始,将该位的元素与其前面某一位(随机得到)元素交换,直到第1位结束。
使用的函数:
- swap(List<?> list, int i, int j)
public static void swap(List list, int i, int j) { // 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 final List l = list; l.set(i, l.set(j, l.get(i))); //将j位置的值和i位置的值进行交换}
- E set(int index, E element)接口
/** * Replaces the element at the specified position in this list with the * specified element (optional operation). * * @param index index of the element to replace * @param element element to be stored at the specified position */ E set(int index, E element)
- E set(int index, E element)某一实现
public E set(int index, E element) { try { ListIteratore = listIterator(index); E oldVal = e.next(); e.set(element); return oldVal; //将index的值设置为element,并返回原来的值 } catch (NoSuchElementException exc) { throw new IndexOutOfBoundsException("Index: "+index); }}
二、如果list没有实现RandomAccess接口且长度大于SHUFFLE_THRESHOLD(5)
这时候首先要做的是将list转化成数组,这个和RandomAccess有关
/** * Marker interface used by List implementations to indicate that * they support fast (generally constant time) random access. The primary * purpose of this interface is to allow generic algorithms to alter their * behavior to provide good performance when applied to either random or * sequential access lists. * *The best algorithms for manipulating random access lists (such as * ArrayList) can produce quadratic behavior when applied to * sequential access lists (such as LinkedList). Generic list * algorithms are encouraged to check whether the given list is an * instanceof this interface before applying an algorithm that would * provide poor performance if it were applied to a sequential access list, * and to alter their behavior if necessary to guarantee acceptable * performance. *......public interface RandomAccess {}
RandomAccess用于标识ist的实现类是否支持快速地随机访问(一般是O(1)的时间复杂度),例如ArraryList实现了RandomAccess接口,随机访问一个元素(get(i))所花费的时间复杂度是O(1),而LinkedList却没有实现这个接口,所以随机一个元素的时间复杂度是O(n)(最坏情况)。所以在遍历一个list时,可以先判断它是否实现了RandomAccess接口,根据数据结构的不同先进行相应的处理,避免出现O(n2)的时间复杂度。
如在shuffle()的else代码段中,就先将没有实现RandomAccess接口的list转换成数组,然后在执行交换策略,这样避免O(n2)的时间复杂度。以上内容如有不正确的地方,欢迎支持。