Алгоритмы коллекций Java

Алгоритмы коллекций Java относятся кjava.util.Collections— набору статических методов, предоставляемых в классе Collections, используемых для выполнения общих операций, таких как сортировка, поиск, перемешивание, заполнение и т. д., над коллекциями (List, Set, Map и т. д.).

Эти алгоритмы встроены в JDK и хорошо оптимизированы. Разработчикам не нужно писать их с нуля; они могут просто вызывать их напрямую.

Обзор алгоритмов Collections

java.util.CollectionsCollections — это служебный класс; все его методы статические, подобно служебному классу Arrays для массивов.

В следующей таблице перечислены наиболее часто используемые алгоритмы коллекций и их назначение:

Категория алгоритма	Название метода	Описание
Сортировка	sort()	Сортирует List по возрастанию
Перемешивание	shuffle()	Случайным образом перемешивает порядок элементов в List
Обращение	reverse()	Изменяет порядок элементов в List на обратный
Бинарный поиск	binarySearch()	Выполняет бинарный поиск заданного элемента в отсортированном List
Заполнение	fill()	Заменяет все элементы в List на указанный элемент
Copy	copy()	Копирует элементы из одного List в другой List
Максимум/Минимум	max() / min()	Возвращает максимальный или минимальный элемент в коллекции
Подсчёт частоты	frequency()	Возвращает количество вхождений указанного элемента в коллекцию
Проверка на непересекаемость	disjoint()	Определяет, есть ли у двух коллекций общие элементы
Неизменяемая коллекция	unmodifiableXxx()	Возвращает представление коллекции только для чтения
Потокобезопасность	synchronizedXxx()	Возвращает потокобезопасную обёртку для коллекции

Сортировка

Collections.sort()Это наиболее часто используемый алгоритм для коллекций, упорядочивающий элементы в List по возрастанию.

Внутри он использует оптимизированную сортировку слиянием (TimSort) с временной сложностью O(n log n) и стабильной производительностью.

Процесс сортировки показан на следующем рисунке:

Сортировка в естественном порядке

Когда класс элемента реализует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("example");
names.add("EXAMPLE");
names.add("apple");
names.add("banana");

System.out.println("Before sorting: " + names);

// Сортировка в естественном порядке (по кодовым точкам Unicode)
Collections.sort(names);

System.out.println("После сортировки: " + names);
}
}

Результат вывода:

排序前: [example, EXAMPLE, apple, banana]
排序后: [EXAMPLE, apple, banana, example]

Сортировка с пользовательским Comparator

ИспользуяComparator,можно сортировать по любому пользовательскому правилу, не изменяя сам класс элемента.

Пример: сортировка по длине String

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("example");
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);
}
}

Результат вывода:

排序前: [example, java, algorithm, C]
按长度排序后: [C, java, example, algorithm]

Java 8+ может использовать лямбда-выражения для упрощения кода:

Пример: синтаксис лямбда-выражения

// Сортировка по длине с использованием лямбда-выражения
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());

Перемешивание

Collections.shuffle()Использует алгоритм Фишера-Йетса для случайного перемешивания порядка элементов в List.

Пример

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]

Бинарный поиск

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("example");
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);
}
}

Результат вывода:

字典序最大: example
字典序最小: 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("example");
items.add("java");
items.add("example");
items.add("python");
items.add("example");

// Подсчитать количество вхождений "example"
int count = Collections.frequency(items, "example");
System.out.println("\"example\""Вхождений: " + 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);
}
}

Результат вывода:

"example" 出现次数: 3
groupA 与 groupB 不相交: true

Неизменяемые коллекции и потокобезопасные обёртки

Collections предоставляет методы для обёртывания обычных коллекций в неизменяемые коллекции или потокобезопасные коллекции.

Неизменяемые коллекции (немодифицируемые)

ВызовCollections.unmodifiableList()и других методов позволяет создать представление только для чтения.

Любая операция модификации вызовет исключение UnsupportedOperationException.

Потокобезопасные коллекции (синхронизированные)

Вызов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("example");
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);
}
}
}
}

Результат вывода:

不可变视图: [example, java]
原始修改后: [example, 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 добавлен default-метод sort(Comparator).

list.sort(null) сортирует с использованием естественного порядка, что эквивалентно Collections.sort(list).

Оба имеют одну и ту же базовую реализацию, но list.sort() более краток по синтаксису.

Рекомендации по сравнению производительности:

Для небольших объёмов данных (менее 100 элементов) различия в производительности между различными алгоритмами незначительны.

Для больших объёмов данных binarySearch() намного превосходит линейный поиск indexOf().

Когда требуется часто выполнять поиск, рассмотрите возможность использования HashSet вместо List, так как сложность запроса составляет O(1).

Другие расширения

Java Объектно-ориентированное программирование

Java Продвинутое руководство

Алгоритмы коллекций Java

Обзор алгоритмов Collections

Сортировка

Сортировка в естественном порядке

Пример

Сортировка с пользовательским Comparator

Пример: сортировка по длине String

Пример: синтаксис лямбда-выражения

Перемешивание

Пример

Бинарный поиск

Пример

Максимум и минимум

Пример

Подсчёт частоты и проверка на непересекаемость

Пример

Неизменяемые коллекции и потокобезопасные обёртки

Неизменяемые коллекции (немодифицируемые)

Потокобезопасные коллекции (синхронизированные)

Пример

Краткий обзор распространённых алгоритмических операций

Примечания