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)，性能稳定。

排序流程如下图所示：

原始列表 5 2 8 1 9 sort() 排序后列表 1 2 5 8 9 自定义排序方式自然顺序 Comparable 接口自定义比较器 Comparator 接口反向排序 Comparator.reverseOrder()

自然顺序排序

元素类实现 Comparable 接口后，可直接调用 sort() 按自然顺序排列。

实例

import java.util.ArrayList;
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.ArrayList;
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 写法

// 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 中的元素顺序。

原始列表 A B C D shuffle() 混排后（随机） C D A B ? ? ? 每次执行结果不同 shuffle(list, new Random(42)) 可以传入固定种子，使混排结果可复现

实例

import java.util.ArrayList;
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.ArrayList;
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.ArrayList;
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.ArrayList;
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.ArrayList;
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)。