Java Collections 工具類核心算法全景解析：查找、排序、順序調整與批量操作

Java Collections 工具類核心算法全景解析

java.util.Collections 作為 Java 集合框架的「瑞士軍刀」，提供了 30+ 個針對 Collection/List 接口的靜態工具方法。本文將其核心算法分為查找替換、排序調序、批量修改三大類，結合源碼與性能分析，揭示面向接口編程的經典實踐。

算法分類總覽

查找替換算法深度剖析

二分查找：RandomAccess 優化策略

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size() < BINARYSEARCH_THRESHOLD)
        return indexedBinarySearch(list, key);  // 索引直接訪問 O(log n)
    else
        return iteratorBinarySearch(list, key); // 迭代器逐步移動 O(n)
}

• RandomAccess 標記介面：ArrayList/Vector/CopyOnWriteArrayList 實現，LinkedList 未實現
• 閾值 BINARYSEARCH_THRESHOLD = 5000：小列表索引訪問更快
• 索引版：list.get(mid) 直接定位，O(log n)
• 迭代器版：ListIterator 逐步 next()/previous() 移動，比較次數 O(log n) 但移動次數 O(n)

極值查找：線性掃描

public static <T extends Comparable<? super T>> T max(Collection<? extends T> coll) {
    Iterator<? extends T> i = coll.iterator();
    T candidate = i.next();
    while (i.hasNext()) {
        T next = i.next();
        if (next.compareTo(candidate) > 0) candidate = next;
    }
    return candidate;
}

單次遍歷，O(n)，支援自定義 Comparator。

子列表查找：暴力匹配

public static int indexOfSubList(List<?> source, List<?> target) {
    int sourceSize = source.size(), targetSize = target.size();
    if (targetSize == 0) return 0;
    if (targetSize > sourceSize) return -1;
    for (int i = 0; i <= sourceSize - targetSize; i++) {
        boolean match = true;
        for (int j = 0; j < targetSize; j++)
            if (!eq(source.get(i+j), target.get(j))) { match = false; break; }
        if (match) return i;
    }
    return -1;
}

類似字符串 indexOf，O(n*m) 暴力算法，大數據量建議 KMP/BM 轉換為字符串處理。

交集判斷：智能選擇遍歷方向

public static boolean disjoint(Collection<?> c1, Collection<?> c2) {
    if (c1 instanceof Set && c2 instanceof Set) {
        // 遍歷較小集合，在較大集合 contains 查找
        return (c1.size() <= c2.size()) ? 
            c1.stream().noneMatch(c2::contains) : 
            c2.stream().noneMatch(c1::contains);
    }
    // 非 Set 退化為雙重循環
    ...
}

排序與順序調整算法

排序：轉數組借力 Arrays.sort

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j = 0; j < a.length; j++) { i.next(); i.set((T)a[j]); }
}

• 時空複雜度：O(n log n) 時間，O(n) 額外空間
• 穩定性：JDK 8+ Arrays.sort 對象數組用 TimSort (歸併+插入)，穩定排序

翻轉：雙指針交換 + RandomAccess 優化

public static void reverse(List<?> list) {
    int size = list.size();
    if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
        for (int i = 0, mid = size >> 1, j = size - 1; i < mid; i++, j--)
            swap(list, i, j); // 索引直接交換
    } else {
        ListIterator fwd = list.listIterator();
        ListIterator rev = list.listIterator(size);
        for (int i = 0, mid = size >> 1; i < mid; i++) {
            Object tmp = fwd.next(); fwd.set(rev.previous()); rev.set(tmp);
        }
    }
}

隨機洗牌：Fisher-Yates 洗牌算法

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)); // [0, i-1] 隨機選一個換到 i-1
    } else {
        Object[] arr = list.toArray();
        for (int i = size; i > 1; i--)
            swap(arr, i-1, rnd.nextInt(i));
        ListIterator it = list.listIterator();
        for (int i = 0; i < arr.length; i++) { it.next(); it.set(arr[i]); }
    }
}

數學證明：每個排列出現概率均為 1/n!，均勻隨機。

循環旋轉：三次翻轉法 (編程珠玑 經典算法)

目標：[8,5,3,6,2] 右旋 2 → [6,2,8,5,3]

等價於將數組分為 A=[8,5,3]、B=[6,2] 兩段，交換順序為 B+A：

1. 翻轉 A → [3,5,8,6,2]
2. 翻轉 B → [3,5,8,2,6]
3. 翻轉整體 → [6,2,8,5,3] ✓

private static void rotate2(List<?> list, int distance) {
    int size = list.size(); if (size == 0) return;
    int mid = -distance % size; if (mid < 0) mid += size; if (mid == 0) return;
    reverse(list.subList(0, mid));
    reverse(list.subList(mid, size));
    reverse(list);
}

子列表旋轉技巧：Collections.rotate(list.subList(j, k+1), -1) 實現「剪切 [j,k] 粘貼到 k+1」效果，O(k-j) 時間原地完成。

批量修改操作

// 批量添加：可變參數 + 數組均支援
Collections.addAll(list, "a", "b", "c");
Collections.addAll(list, stringArray);

// 批量填充：全部替換為同一對象引用
Collections.fill(list, defaultValue);

// 批量拷貝：dest 長度 >= src，覆蓋對應位置
Collections.copy(destList, srcList);

性能選型速查表

總結

Collections 以面向接口編程為核心設計，所有算法針對 Collection/List 接口而非具體實現，體現了「依賴抽象不依賴具體」原則。關鍵亮點：

• RandomAccess 分流策略：根據數據結構特性動態選擇最優算法路徑
• 經典算法工程化：三次翻轉旋轉、Fisher-Yates 洗牌、TimSort 排序，將教科書算法轉化為生產級工具
• 空間換時間權衡：排序/洗牌/旋轉非 RandomAccess 列表時，toArray() 付出 O(n) 空間換取 O(n) 時間優勢

掌握這些算法的適用邊界與性能特徵，能指導日常集合操作選型，也是面試高頻考點與造輪子的靈感來源。