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<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
一、首先是判斷要打亂的list的屬性：list的size和是否實(shí)現(xiàn)RandomAccess接口
如果list的size小于SHUFFLE_THRESHOLD(5) 或者 list實(shí)現(xiàn)了RandomAccess接口析桥，則直接交換list內(nèi)元素的位置司草。具體的交換策略如下：
令list的size為n, 從n-1位開(kāi)始，將該位的元素與其前面某一位(隨機(jī)得到)元素交換泡仗，直到第1位結(jié)束埋虹。
使用的函數(shù)：
- 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位置的值進(jìn)行交換
}
- 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)某一實(shí)現(xiàn)
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal; //將index的值設(shè)置為element，并返回原來(lái)的值
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
二娩怎、如果list沒(méi)有實(shí)現(xiàn)RandomAccess接口且長(zhǎng)度大于SHUFFLE_THRESHOLD(5)
這時(shí)候首先要做的是將list轉(zhuǎn)化成數(shù)組搔课，這個(gè)和RandomAccess有關(guān)
/**
* Marker interface used by <tt>List</tt> 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.
*
* <p>The best algorithms for manipulating random access lists (such as
* <tt>ArrayList</tt>) can produce quadratic behavior when applied to
* sequential access lists (such as <tt>LinkedList</tt>). Generic list
* algorithms are encouraged to check whether the given list is an
* <tt>instanceof</tt> 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用于標(biāo)識(shí)ist的實(shí)現(xiàn)類是否支持快速地隨機(jī)訪問(wèn)(一般是O(1)的時(shí)間復(fù)雜度)，例如ArraryList實(shí)現(xiàn)了RandomAccess接口截亦，隨機(jī)訪問(wèn)一個(gè)元素(get(i))所花費(fèi)的時(shí)間復(fù)雜度是O(1)爬泥，而LinkedList卻沒(méi)有實(shí)現(xiàn)這個(gè)接口，所以隨機(jī)一個(gè)元素的時(shí)間復(fù)雜度是O(n)(最壞情況)崩瓤。所以在遍歷一個(gè)list時(shí)袍啡，可以先判斷它是否實(shí)現(xiàn)了RandomAccess接口，根據(jù)數(shù)據(jù)結(jié)構(gòu)的不同先進(jìn)行相應(yīng)的處理却桶，避免出現(xiàn)O(n2)的時(shí)間復(fù)雜度境输。
如在shuffle()的else代碼段中，就先將沒(méi)有實(shí)現(xiàn)RandomAccess接口的list轉(zhuǎn)換成數(shù)組肾扰，然后在執(zhí)行交換策略畴嘶，這樣避免O(n2)的時(shí)間復(fù)雜度。
感謝堂爺的幫助集晚！
以上內(nèi)容如有不正確的地方窗悯，歡迎支持。
