之前幾節介紹了各種具體容器類和抽象容器類，上節我們提到，Java中有一個類Collections，提供了很多針對容器接口的通用功能，這些功能都是以靜態方法的方式提供的。
都有哪些功能呢？大概可以分為兩類：
對於第一類，操作大概可以分為三組：
對於第二類，大概可以分為兩組：
它們都是圍繞容器接口對象的，第一類是針對容器接口的通用操作，這是我們之前在接口的本質一節介紹的面向接口編程的一種體現，是接口的典型用法，第二類是為了使更多類型的數據更為方便和安全的參與到容器類協作體系中。
由於內容比較多，我們分為兩節，本節討論第一類，下節我們討論第二類。下面我們分組來看下第一類中的算法。
查找和替換
查找和替換包含多組方法，我們分別來看下。
二分查找
我們在剖析Arrays類的時候介紹過二分查找，Arrays類有針對數組對象的二分查找方法，Collections提供了針對List接口的二分查找，如下所示：
public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
從方法參數，容易理解，一個要求List的每個元素實現Comparable接口，另一個不需要，但要求提供Comparator。
二分查找假定List中的元素是從小到大排序的。如果是從大到小排序的，也容易，傳遞一個逆序Comparator對象，Collections提供了返回逆序Comparator的方法，之前我們也用過：
public static <T> Comparator<T> reverseOrder() public static <T> Comparator<T> reverseOrder(Comparator<T> cmp)
比如，可以這麼用：
List<Integer> list = new ArrayList<>(Arrays.asList(new Integer[]{
35, 24, 13, 12, 8, 7, 1
}));
System.out.println(Collections.binarySearch(list, 7, Collections.reverseOrder()));
輸出為：
5
List的二分查找的基本思路與Arrays中的是一樣的，但，數組可以根據索引直接定位任意元素，實現效率很高，但List就不一定了，我們來看它的實現代碼：
public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key);
else
return Collections.iteratorBinarySearch(list, key);
}
分為兩種情況，如果List可以隨機訪問(如數組)，即實現了RandomAccess接口，或者元素個數比較少，則實現思路與Arrays一樣，調用indexedBinarySearch根據索引直接訪問中間元素進行查找，否則調用iteratorBinarySearch使用迭代器的方式訪問中間元素進行查找。
indexedBinarySearch的代碼為：
private static <T>
int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
int low = 0;
int high = list.size()-1;
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = list.get(mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
調用list.get(mid)訪問中間元素。
iteratorBinarySearch的代碼為：
private static <T>
int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key)
{
int low = 0;
int high = list.size()-1;
ListIterator<? extends Comparable<? super T>> i = list.listIterator();
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid; // key found
}
return -(low + 1); // key not found
}
調用get(i, mid)尋找中間元素，get方法的代碼為：
private static <T> T get(ListIterator<? extends T> i, int index) {
T obj = null;
int pos = i.nextIndex();
if (pos <= index) {
do {
obj = i.next();
} while (pos++ < index);
} else {
do {
obj = i.previous();
} while (--pos > index);
}
return obj;
}
通過迭代器方法逐個移動到期望的位置。
我們來分析下效率，如果List支持隨機訪問，效率為O(log2(N))，如果通過迭代器，比較的次數為O(log2(N))，但遍歷移動的次數為O(N)，N為列表長度。
查找最大值/最小值
Collections提供了如下查找最大最小值的方法：
public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)
含義和用法都很直接，實現思路也很簡單，就是通過迭代器進行比較，比如，其中一個方法的代碼為：
public static <T extends Object & 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;
}
其他方法就不贅述了。
查找元素出現次數
方法為：
public static int frequency(Collection<?> c, Object o)
返回元素o在容器c中出現的次數，o可以為null。含義很簡單，實現思路也是，就是通過迭代器進行比較計數。
查找子List
在剖析String類一節，我們介紹過，String類有查找子字符串的方法：
public int indexOf(String str) public int lastIndexOf(String str)
對List接口對象，Collections提供了類似方法，在source List中查找target List的位置：
public static int indexOfSubList(List<?> source, List<?> target) public static int lastIndexOfSubList(List<?> source, List<?> target)
indexOfSubList從開頭找，lastIndexOfSubList從結尾找，沒找到返回-1，找到返回第一個匹配元素的索引位置，比如：
List<Integer> source = Arrays.asList(new Integer[]{
35, 24, 13, 12, 8, 24, 13, 7, 1
});
System.out.println(Collections.indexOfSubList(source, Arrays.asList(new Integer[]{24, 13})));
System.out.println(Collections.lastIndexOfSubList(source, Arrays.asList(new Integer[]{24, 13})));
輸出為：
1 5
這兩個方法的實現都是屬於"暴力破解"型的，將target列表與source從第一個元素開始的列表逐個元素進行比較，如果不匹配，則與source從第二個元素開始的列表比較，再不匹配，與source從第三個元素開始的列表比較，依次類推。
查看兩個集合是否有交集
方法為：
public static boolean disjoint(Collection<?> c1, Collection<?> c2)
如果c1和c2有交集，返回值為false，沒有交集，返回值為true。
實現原理也很簡單，遍歷其中一個容器，對每個元素，在另一個容器裡通過contains方法檢查是否包含該元素，如果包含，返回false，如果最後不包含任何元素返回true。這個方法的代碼會根據容器是否為Set以及集合大小進行性能優化，即選擇哪個容器進行遍歷，哪個容器進行檢查，以減少總的比較次數，具體我們就不介紹了。
替換
替換方法為：
public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)
將List中的所有oldVal替換為newVal，如果發生了替換，返回值為true，否則為false。用法和實現都比較簡單，就不贅述了。
排序和調整順序
針對List接口對象，Collections除了提供基礎的排序，還提供了若干調整順序的方法，包括交換元素位置、翻轉列表順序、隨機化重排、循環移位等，我們逐個來看下。
排序
Arrays類有針對數組對象的排序方法，Collections提供了針對List接口的排序方法，如下所示：
public static <T extends Comparable<? super T>> void sort(List<T> list) public static <T> void sort(List<T> list, Comparator<? super T> c)
使用很簡單，就不舉例了，內部它是通過Arrays.sort實現的，先將List元素拷貝到一個數組中，然後使用Arrays.sort，排序後，再拷貝回List。代碼如下所示：
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]);
}
}
交換元素位置
方法為：
public static void swap(List<?> list, int i, int j)
交換list中第i個和第j個元素的內容。實現代碼為：
public static void swap(List<?> list, int i, int j) {
final List l = list;
l.set(i, l.set(j, l.get(i)));
}
翻轉列表順序
方法為：
public static void reverse(List<?> list)
將list中的元素順序翻轉過來。實現思路就是將第一個和最後一個交換，第二個和倒數第二個交換，依次類推直到中間兩個元素交換完畢。
如果list實現了RandomAccess接口或列表比較小，根據索引位置，使用上面的swap方法進行交換，否則，由於直接根據索引位置定位元素效率比較低，使用一前一後兩個listIterator定位待交換的元素。具體代碼為：
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=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
}
}
隨機化重排
我們在隨機一節介紹過洗牌算法，Collections直接提供了對List元素洗牌的方法：
public static void shuffle(List<?> list) public static void shuffle(List<?> list, Random rnd)
實現思路與隨機一節介紹的是一樣的，從後往前遍歷列表，逐個給每個位置重新賦值，值從前面的未重新賦值的元素中隨機挑選。如果列表實現了RandomAccess接口，或者列表比較小，直接使用前面swap方法進行交換，否則，先將列表內容拷貝到一個數組中，洗牌，再拷貝回列表。代碼如下：
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
ListIterator it = list.listIterator();
for (int i=0; i<arr.length; i++) {
it.next();
it.set(arr[i]);
}
}
}
循環移位
我們解釋下循環移位的概念，比如列表為：
[8, 5, 3, 6, 2]
循環右移2位，會變為：
[6, 2, 8, 5, 3]
如果是循環左移2位，會變為：
[3, 6, 2, 8, 5]
因為列表長度為5，循環左移3位和循環右移2位的效果是一樣的。
循環移位的方法是：
public static void rotate(List<?> list, int distance)
distance表示循環移位個數，一般正數表示向右移，負數表示向左移，比如：
List<Integer> list1 = Arrays.asList(new Integer[]{
8, 5, 3, 6, 2
});
Collections.rotate(list1, 2);
System.out.println(list1);
List<Integer> list2 = Arrays.asList(new Integer[]{
8, 5, 3, 6, 2
});
Collections.rotate(list2, -2);
System.out.println(list2);
輸出為：
[6, 2, 8, 5, 3] [3, 6, 2, 8, 5]
這個方法很有用的一點是，它也可以用於子列表，可以調整子列表內的順序而不改變其他元素的位置。比如，將第j個元素向前移動到k (k>j)，可以這麼寫：
Collections.rotate(list.subList(j, k+1), -1);
再舉個例子：
List<Integer> list = Arrays.asList(new Integer[]{
8, 5, 3, 6, 2, 19, 21
});
Collections.rotate(list.subList(1, 5), 2);
System.out.println(list);
輸出為：
[8, 6, 2, 5, 3, 19, 21]
這個類似於列表內的"剪切"和"粘貼"，將子列表[5, 3]"剪切"，"粘貼"到2後面。如果需要實現類似"剪切"和"粘貼"的功能，可以使用rotate方法。
循環移位的內部實現比較巧妙，根據列表大小和是否實現了RandomAccess接口，有兩個算法，都比較巧妙，兩個算法在《編程珠玑》這本書的2.3節有描述。
篇幅有限，我們只解釋下其中的第二個算法，它將循環移位看做是列表的兩個子列表進行順序交換。再來看上面的例子，循環左移2位：
[8, 5, 3, 6, 2] -> [3, 6, 2, 8, 5]
就是將[8, 5]和[3, 6, 2]兩個子列表的順序進行交換。
循環右移兩位：
[8, 5, 3, 6, 2] -> [6, 2, 8, 5, 3]
就是將[8, 5, 3]和[6, 2]兩個子列表的順序進行交換。
根據列表長度size和移位個數distance，可以計算出兩個子列表的分隔點，有了兩個子列表後，兩個子列表的順序交換可以通過三次翻轉實現，比如有A和B兩個子列表，A有m個元素，B有n個元素：
要變為：
可經過三次翻轉實現：
1. 翻轉子列表A
2. 翻轉子列表B
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);
}
mid為兩個子列表的分割點，調用了三次reverse以實現子列表順序交換。
添加和修改
Collections也提供了幾個批量添加和修改的方法，邏輯都比較簡單，我們看下。
批量添加
方法為：
public static <T> boolean addAll(Collection<? super T> c, T... elements)
elements為可變參數，將所有元素添加到容器c中。這個方法很方便，比如，可以這樣：
List<String> list = new ArrayList<String>();
String[] arr = new String[]{"深入", "淺出"};
Collections.addAll(list, "hello", "world", "老馬", "編程");
Collections.addAll(list, arr);
System.out.println(list);
輸出為：
[hello, world, 老馬, 編程, 深入, 淺出]
批量填充固定值
方法為：
public static <T> void fill(List<? super T> list, T obj)
這個方法與Arrays類中的fill方法是類似的，給每個元素設置相同的值。
批量拷貝
方法為：
public static <T> void copy(List<? super T> dest, List<? extends T> src)
將列表src中的每個元素拷貝到列表dest的對應位置處，覆蓋dest中原來的值，dest的列表長度不能小於src，dest中超過src長度部分的元素不受影響。
小結
本節介紹了類Collections中的一些通用算法，包括查找、替換、排序、調整順序、添加、修改等，這些算法操作的都是容器接口對象，這是面向接口編程的一種體現，只要對象實現了這些接口，就可以使用這些算法。
在與容器類和Collections中的算法進行協作時，經常需要將其他類型的數據轉換為容器接口對象，為此，Collections同樣提供了很多方法。都有哪些方法？有什麼用？體現了怎樣的設計模式和思維？讓我們在下一節繼續探索。
----------------
未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心原創，保留所有版權。
