Java 集合算法
Java 集合算法是指 java.util.Collections 类中提供的一组静态方法，用于对集合（List、Set、Map 等）执行排序、查找、混排、填充等常见操作。
这些算法由 JDK 内置实现，经过高度优化，开发者无需从零编写，直接调用即可。
Collections 算法概览
java.util.Collections 是一个工具类，所有方法均为 static，类似于操作数组的 Arrays 工具类。
下表列出了最常用的集合算法及其用途：
| 算法分类 | 方法名 | 功能描述 |
|---|---|---|
| 排序 | sort() | 对 List 进行升序排序 |
| 混排 | shuffle() | 随机打乱 List 中元素的顺序 |
| 反转 | reverse() | 反转 List 中元素的顺序 |
| 二分查找 | binarySearch() | 在有序 List 中二分查找指定元素 |
| 填充 | fill() | 用指定元素替换 List 中的所有元素 |
| 复制 | copy() | 将一个 List 的元素复制到另一个 List |
| 最大/最小值 | max() / min() | 返回集合中的最大或最小元素 |
| 统计频次 | frequency() | 返回指定元素在集合中出现的次数 |
| 不相交判断 | disjoint() | 判断两个集合是否有公共元素 |
| 不可变集合 | unmodifiableXxx() | 返回集合的只读视图 |
| 线程安全 | synchronizedXxx() | 返回线程安全的集合包装 |
排序（Sorting）
Collections.sort() 是最常用的集合算法，对 List 中的元素进行升序排列。
底层使用的是优化过的归并排序（TimSort），时间复杂度为 O(n log n)，性能稳定。
排序流程如下图所示：
自然顺序排序
元素类实现 Comparable 接口后，可直接调用 sort() 按自然顺序排列。
实例
import java.util.Collections;
import java.util.List;
public class SortExample {
public static void main(String[] args) {
List<String> names = new ArrayList<>();
names.add("runoob");
names.add("RUNOOB");
names.add("apple");
names.add("banana");
System.out.println("排序前: " + names);
// 自然顺序排序（按 Unicode 码点）
Collections.sort(names);
System.out.println("排序后: " + names);
}
}
输出结果：
排序前: [runoob, RUNOOB, apple, banana] 排序后: [RUNOOB, apple, banana, runoob]
自定义 Comparator 排序
使用 Comparator 可以按任意自定义规则排序，而不需要修改元素类本身。
实例：按字符串长度排序
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class CustomSortExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("runoob");
words.add("java");
words.add("algorithm");
words.add("C");
System.out.println("排序前: " + words);
// 按字符串长度升序排序
Collections.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});
System.out.println("按长度排序后: " + words);
}
}
输出结果：
排序前: [runoob, java, algorithm, C] 按长度排序后: [C, java, runoob, algorithm]
Java 8+ 可以使用 Lambda 表达式简化写法：
实例：Lambda 写法
Collections.sort(words, (s1, s2) -> s1.length() - s2.length());
// 或者使用 Comparator.comparingInt
Collections.sort(words, Comparator.comparingInt(String::length));
// 反向排序
Collections.sort(words, Comparator.reverseOrder());
// 按长度反向排序
Collections.sort(words, Comparator.comparingInt(String::length).reversed());
混排（Shuffling）
Collections.shuffle() 使用 Fisher-Yates 算法随机打乱 List 中的元素顺序。
实例
import java.util.Collections;
import java.util.List;
public class ShuffleExample {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
numbers.add(i);
}
System.out.println("原始列表: " + numbers);
// 随机打乱顺序
Collections.shuffle(numbers);
System.out.println("第一次混排: " + numbers);
Collections.shuffle(numbers);
System.out.println("第二次混排: " + numbers);
}
}
输出结果：
原始列表: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 第一次混排: [7, 3, 9, 1, 5, 10, 8, 2, 4, 6] 第二次混排: [4, 10, 1, 8, 6, 3, 2, 9, 5, 7]
二分查找（Binary Search）
Collections.binarySearch() 在有序 List 中使用二分查找算法定位目标元素。
时间复杂度为 O(log n)，远优于线性遍历的 O(n)。
重要前提：List 必须已按升序排序，否则结果不确定。
实例
import java.util.Collections;
import java.util.List;
public class BinarySearchExample {
public static void main(String[] args) {
List<Integer> numbers = new ArrayList<>();
numbers.add(10);
numbers.add(30);
numbers.add(20);
numbers.add(50);
numbers.add(40);
// 必须先排序
Collections.sort(numbers);
System.out.println("排序后列表: " + numbers);
// 二分查找：返回值为索引（>= 0 表示找到）
int index = Collections.binarySearch(numbers, 30);
System.out.println("30 的索引位置: " + index);
// 查找不存在的元素：返回负值 = -(插入点) - 1
int notFound = Collections.binarySearch(numbers, 25);
System.out.println("25 的返回值（不存在）: " + notFound);
// 插入点 = -(notFound + 1) = 2，应插入到索引 2 处
}
}
输出结果：
排序后列表: [10, 20, 30, 40, 50] 30 的索引位置: 2 25 的返回值（不存在）: -3
binarySearch() 找不到元素时返回负值，公式为 -(插入点) - 1。插入点是该元素如果存在应该位于的索引。这一设计的巧妙之处在于：如果元素存在则返回非负索引，如果不存在则必然返回负值，不会产生歧义。
最大值与最小值
Collections.max() 和 Collections.min() 返回集合中按自然顺序或指定比较器的最大/最小元素。
实例
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class MaxMinExample {
public static void main(String[] args) {
List<String> words = new ArrayList<>();
words.add("runoob");
words.add("algorithm");
words.add("java");
words.add("code");
// 按自然顺序（字典序）取最大和最小
String maxWord = Collections.max(words);
String minWord = Collections.min(words);
System.out.println("字典序最大: " + maxWord);
System.out.println("字典序最小: " + minWord);
// 按字符串长度取最大和最小
String longest = Collections.max(words,
Comparator.comparingInt(String::length));
String shortest = Collections.min(words,
Comparator.comparingInt(String::length));
System.out.println("长度最长: " + longest);
System.out.println("长度最短: " + shortest);
}
}
输出结果：
字典序最大: runoob 字典序最小: algorithm 长度最长: algorithm 长度最短: code
统计频次与不相交判断
Collections.frequency() 统计指定元素在集合中出现的次数。
Collections.disjoint() 判断两个集合是否完全没有公共元素。
实例
import java.util.Collections;
import java.util.List;
public class FrequencyDisjointExample {
public static void main(String[] args) {
List<String> items = new ArrayList<>();
items.add("runoob");
items.add("java");
items.add("runoob");
items.add("python");
items.add("runoob");
// 统计 "runoob" 出现的次数
int count = Collections.frequency(items, "runoob");
System.out.println("\"runoob\" 出现次数: " + count);
// 判断两个集合是否不相交
List<String> groupA = new ArrayList<>();
groupA.add("java");
groupA.add("python");
List<String> groupB = new ArrayList<>();
groupB.add("C++");
groupB.add("go");
boolean noCommon = Collections.disjoint(groupA, groupB);
System.out.println("groupA 与 groupB 不相交: " + noCommon);
}
}
输出结果：
"runoob" 出现次数: 3 groupA 与 groupB 不相交: true
不可变集合与线程安全包装
Collections 提供了将普通集合包装为不可变集合或线程安全集合的方法。
不可变集合（Unmodifiable）
调用 Collections.unmodifiableList() 等方法可以创建一个只读视图。
任何修改操作都会抛出 UnsupportedOperationException。
线程安全集合（Synchronized）
调用 Collections.synchronizedList() 等方法可以创建一个线程安全的包装器。
多线程环境下对这些集合的单个方法调用是安全的，但复合操作仍需外部同步。
实例
import java.util.Collections;
import java.util.List;
public class WrapperExample {
public static void main(String[] args) {
List<String> original = new ArrayList<>();
original.add("runoob");
original.add("java");
// 创建不可变视图
List<String> readOnly = Collections.unmodifiableList(original);
System.out.println("不可变视图: " + readOnly);
// readOnly.add("error"); // 执行会抛出异常
// 原始列表修改后，不可变视图也会反映变化
original.add("python");
System.out.println("原始修改后: " + readOnly);
// 创建线程安全包装
List<String> syncList = Collections.synchronizedList(
new ArrayList<>());
syncList.add("thread-safe");
// 遍历时需要手动同步
synchronized (syncList) {
for (String item : syncList) {
System.out.println(item);
}
}
}
}
输出结果：
不可变视图: [runoob, java] 原始修改后: [runoob, java, python] thread-safe
不可变视图只是阻止通过该视图修改集合，底层集合仍然可变。如果需要真正不可变的集合，使用 Java 9+ 的 List.of()、Set.of() 等方法。
常用算法操作一览
以下汇总了 Collections 中常用算法的调用方式和时间复杂度：
| 操作 | 方法调用 | 时间复杂度 | 前提条件 |
|---|---|---|---|
| 排序 | Collections.sort(list) | O(n log n) | 元素实现 Comparable |
| 自定义排序 | Collections.sort(list, comp) | O(n log n) | 提供 Comparator |
| 反转 | Collections.reverse(list) | O(n) | 无 |
| 混排 | Collections.shuffle(list) | O(n) | 无 |
| 二分查找 | Collections.binarySearch(list, key) | O(log n) | 列表已排序 |
| 填充 | Collections.fill(list, obj) | O(n) | 无 |
| 复制 | Collections.copy(dest, src) | O(n) | dest.size() >= src.size() |
| 最大值 | Collections.max(coll) | O(n) | 元素实现 Comparable |
| 最小值 | Collections.min(coll) | O(n) | 元素实现 Comparable |
| 统计频次 | Collections.frequency(coll, obj) | O(n) | 无 |
| 交换元素 | Collections.swap(list, i, j) | O(1) | 索引有效 |
| 旋转 | Collections.rotate(list, distance) | O(n) | 无 |
注意事项
binarySearch() 必须在已排序的列表上调用，未排序列表的返回结果是未定义的。如果列表包含重复元素，不保证找到哪一个。
synchronizedXxx() 返回的包装器只在单个方法调用层面保证原子性。复合操作（如 if(!list.contains(x)) list.add(x)）仍需要外部 synchronized 块。
sort() 与 List.sort() 的区别：
Java 8 之后，List 接口新增了 sort(Comparator) 默认方法。
list.sort(null) 使用自然顺序排序，等价于 Collections.sort(list)。
两者底层实现相同，但 list.sort() 写法更简洁。
性能对比建议：
对于小数据量（< 100 个元素），各种算法的性能差异可忽略不计。
对于大数据量，binarySearch() 远优于 indexOf() 的线性查找。
需要频繁查找时，考虑使用 HashSet 替代 List，查询复杂度为 O(1)。