JDK Collections.shuffle(List<?> list, Random

Aomine 發(fā)布于2019-08-15 14:48 / 1352人閱讀

摘要：的源碼如下一首先是判斷要打亂的的屬性的和是否實(shí)現(xiàn)接口如果的小于或者實(shí)現(xiàn)了接口，則直接交換內(nèi)元素的位置。以上內(nèi)容如有不正確的地方，歡迎支持。

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和是否實(shí)現(xiàn)RandomAccess接口
如果list的size小于SHUFFLE_THRESHOLD(5) 或者 list實(shí)現(xiàn)了RandomAccess接口，則直接交換list內(nèi)元素的位置。具體的交換策略如下：
令list的size為n, 從n-1位開始，將該位的元素與其前面某一位(隨機(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 = listIterator(index);
            E oldVal = e.next();
            e.set(element);    
            return oldVal;      //將index的值設(shè)置為element，并返回原來的值
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
}
二、如果list沒有實(shí)現(xiàn)RandomAccess接口且長(zhǎng)度大于SHUFFLE_THRESHOLD(5)
這時(shí)候首先要做的是將list轉(zhuǎn)化成數(shù)組，這個(gè)和RandomAccess有關(guān)
/**
 * 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用于標(biāo)識(shí)ist的實(shí)現(xiàn)類是否支持快速地隨機(jī)訪問(一般是O(1)的時(shí)間復(fù)雜度)，例如ArraryList實(shí)現(xiàn)了RandomAccess接口，隨機(jī)訪問一個(gè)元素(get(i))所花費(fèi)的時(shí)間復(fù)雜度是O(1)，而LinkedList卻沒有實(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(n²)的時(shí)間復(fù)雜度。
如在shuffle()的else代碼段中，就先將沒有實(shí)現(xiàn)RandomAccess接口的list轉(zhuǎn)換成數(shù)組，然后在執(zhí)行交換策略，這樣避免O(n²)的時(shí)間復(fù)雜度。

以上內(nèi)容如有不正確的地方，歡迎支持。