Algoritmos de colecciones de Java

Los algoritmos de colecciones de Java se refieren ajava.util.Collectionsun conjunto de métodos estáticos proporcionados por la clase, utilizados para realizar operaciones comunes como ordenamiento, búsqueda, barajado, relleno, etc., sobre colecciones (List, Set, Map, etc.).

Estos algoritmos están implementados de forma incorporada en el JDK y altamente optimizados; los desarrolladores no necesitan escribirlos desde cero, solo llamarlos directamente.

Resumen de algoritmos de Collections

java.util.Collectionses una clase de utilidad, todos los métodos son estáticos, similar a la clase de utilidad Arrays para operar con arreglos.

La tabla siguiente enumera los algoritmos de colecciones más comunes y sus usos:

Categoría de algoritmo	Nombre del método	Descripción de la función
Ordenamiento	sort()	Ordena una List en orden ascendente
Barajado	shuffle()	Mezcla aleatoriamente el orden de los elementos en una List
Inversión	reverse()	Invierte el orden de los elementos en una List
Búsqueda binaria	binarySearch()	Busca binariamente un elemento especificado en una List ordenada
Relleno	fill()	Reemplaza todos los elementos de una List con un elemento especificado
Copia	copy()	Copia los elementos de una List a otra List
Máximo/Mínimo	max() / min()	Devuelve el elemento máximo o mínimo de una colección
Conteo de frecuencia	frequency()	Devuelve el número de veces que aparece un elemento especificado en la colección
Verificación de disyunción	disjoint()	Determina si dos colecciones tienen elementos en común
Colección inmutable	unmodifiableXxx()	Devuelve una vista de solo lectura de la colección
Seguridad para hilos	synchronizedXxx()	Devuelve un envoltorio de colección seguro para hilos

Ordenamiento (Sorting)

Collections.sort()Es el algoritmo de colecciones más utilizado; ordena los elementos de una List en orden ascendente.

En su interior utiliza una variante optimizada de ordenamiento por mezcla (TimSort), con complejidad temporal O(n log n) y rendimiento estable.

El proceso de ordenamiento se muestra en la siguiente figura:

Ordenamiento por orden natural

La clase de elementos implementaComparablela interfaz, y luego se puede llamar directamente a sort() para ordenar según el orden natural.

Ejemplo

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("ejemplo");
names.add("EJEMPLO");
names.add("apple");
names.add("banana");

System.out.println(Antes de ordenar: + names);

// Ordenamiento por orden natural (según puntos de código Unicode)
Collections.sort(names);

System.out.println(Después de ordenar: + names);
}
}

Resultado de salida:

排序前: [ejemplo, EJEMPLO, apple, banana]
排序后: [EJEMPLO, apple, banana, ejemplo]

Ordenamiento con Comparator personalizado

UsandoComparatorse puede ordenar según cualquier regla personalizada sin necesidad de modificar la propia clase de elementos.

Ejemplo: ordenar por longitud de cadena

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("ejemplo");
words.add("java");
words.add("algorithm");
words.add("C");

System.out.println(Antes de ordenar: + words);

// Ordenar por longitud de cadena en orden ascendente
Collections.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});

System.out.println(Después de ordenar por longitud: + words);
}
}

Resultado de salida:

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

Java 8+ puede usar expresiones Lambda para simplificar la escritura:

Ejemplo: sintaxis Lambda

// Expresión Lambda para ordenar por longitud
Collections.sort(words, (s1, s2) -> s1.length() - s2.length());

// O usar Comparator.comparingInt
Collections.sort(words, Comparator.comparingInt(String::length));

// Ordenamiento inverso
Collections.sort(words, Comparator.reverseOrder());

// Ordenar por longitud en orden inverso
Collections.sort(words, Comparator.comparingInt(String::length).reversed());

Barajado (Shuffling)

Collections.shuffle()Utiliza el algoritmo de Fisher-Yates para mezclar aleatoriamente el orden de los elementos en una List.

Ejemplo

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(Lista original: + numbers);

// Mezclar aleatoriamente el orden
Collections.shuffle(numbers);
System.out.println(Primer barajado: + numbers);

Collections.shuffle(numbers);
System.out.println(Segundo barajado: + numbers);
}
}

Resultado de salida:

原始列表: [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]

Búsqueda binaria (Binary Search)

Collections.binarySearch()Utiliza el algoritmo de búsqueda binaria para localizar un elemento objetivo en una List ordenada.

La complejidad temporal es O(log n), muy superior a la O(n) del recorrido lineal.

Requisito importante: la List debe estar ordenada en orden ascendente; de lo contrario, el resultado no es determinista.

Ejemplo

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);

// Primero debe estar ordenada
Collections.sort(numbers);
System.out.println(Lista después de ordenar: + numbers);

// Búsqueda binaria: el valor devuelto es el índice (>= 0 indica que se encontró)
int index = Collections.binarySearch(numbers, 30);
System.out.println(Posición del índice de 30: + index);

// Buscar un elemento inexistente: devuelve un valor negativo = -(punto de inserción) - 1
int notFound = Collections.binarySearch(numbers, 25);
System.out.println(Valor devuelto para 25 (inexistente): + notFound);
// Punto de inserción = -(notFound + 1) = 2, debería insertarse en el índice 2
}
}

Resultado de salida:

排序后列表: [10, 20, 30, 40, 50]
30 的索引位置: 2
25 的返回值（不存在）: -3

Cuando binarySearch() no encuentra el elemento, devuelve un valor negativo; la fórmula es-(punto de inserción) - 1El punto de inserción es el índice en el que debería ubicarse el elemento si existiera. Lo ingenioso de este diseño es que si el elemento existe se devuelve un índice no negativo, y si no existe se devuelve inevitablemente un valor negativo, sin ambigüedad.

Valores máximo y mínimo

Collections.max()yCollections.min()Devuelve el elemento máximo/mínimo de una colección según el orden natural o un comparador especificado.

Ejemplo

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("ejemplo");
words.add("algorithm");
words.add("java");
words.add("code");

// Tomar máximo y mínimo según el orden natural (lexicográfico)
String maxWord = Collections.max(words);
String minWord = Collections.min(words);
System.out.println(Máximo lexicográfico: + maxWord);
System.out.println(Mínimo lexicográfico: + minWord);

// Tomar máximo y mínimo por longitud de cadena
String longest = Collections.max(words,
Comparator.comparingInt(String::length));
String shortest = Collections.min(words,
Comparator.comparingInt(String::length));
System.out.println(De mayor longitud: + longest);
System.out.println(De menor longitud: + shortest);
}
}

Resultado de salida:

字典序最大: ejemplo
字典序最小: algorithm
长度最长: algorithm
长度最短: code

Conteo de frecuencia y verificación de disyunción

Collections.frequency()Cuenta el número de veces que aparece un elemento especificado en la colección.

Collections.disjoint()Determina si dos colecciones no tienen ningún elemento en común.

Ejemplo

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("ejemplo");
items.add("java");
items.add("ejemplo");
items.add("python");
items.add("ejemplo");

// Contar cuántas veces aparece "ejemplo"
int count = Collections.frequency(items, "ejemplo");
System.out.println("\"ejemplo\"Número de apariciones: + count);

// Determinar si dos colecciones son disjuntas
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 y groupB son disjuntas: + noCommon);
}
}

Resultado de salida:

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

Colecciones inmutables y envoltorios seguros para hilos

Collections proporciona métodos para envolver colecciones ordinarias como colecciones inmutables o colecciones seguras para hilos.

Colecciones inmutables (Unmodifiable)

Al llamarCollections.unmodifiableList()a métodos como estos, se puede crear una vista de solo lectura.

Cualquier operación de modificación lanzará una UnsupportedOperationException.

Colecciones seguras para hilos (Synchronized)

Llamando aCollections.synchronizedList()métodos como estos, se puede crear un envoltorio seguro para hilos.

En un entorno multihilo, las llamadas a métodos individuales de estas colecciones son seguras, pero las operaciones compuestas aún requieren sincronización externa.

Ejemplo

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("ejemplo");
original.add("java");

// Crear una vista inmutable
List<String> readOnly = Collections.unmodifiableList(original);
System.out.println(Vista inmutable: + readOnly);

// readOnly.add("error"); // La ejecución lanzará una excepción

// Después de modificar la lista original, la vista inmutable también reflejará los cambios
original.add("python");
System.out.println(Después de modificar la original: + readOnly);

// Crear un envoltorio seguro para hilos
List<String> syncList = Collections.synchronizedList(
new ArrayList<>());
syncList.add("thread-safe");

// Al iterar, se necesita sincronización manual
synchronized (syncList) {
for (String item : syncList) {
System.out.println(item);
}
}
}
}

Resultado de salida:

不可变视图: [ejemplo, java]
原始修改后: [ejemplo, java, python]
thread-safe

La vista inmutable solo impide modificar la colección a través de esa vista; la colección subyacente sigue siendo mutable. Si se necesita una colección verdaderamente inmutable, use los métodos de Java 9+List.of()、Set.of()como estos.

Resumen de operaciones de algoritmos comunes

A continuación se resumen los métodos de llamada y la complejidad temporal de los algoritmos comunes en Collections:

Operación	Llamada al método	Complejidad temporal	Requisitos previos
Ordenación	Collections.sort(list)	O(n log n)	Los elementos implementan Comparable
Ordenación personalizada	Collections.sort(list, comp)	O(n log n)	Proporcionar un Comparator
Inversión	Collections.reverse(list)	O(n)	Ninguno
Barajado	Collections.shuffle(list)	O(n)	Ninguno
Búsqueda binaria	Collections.binarySearch(list, key)	O(log n)	La lista está ordenada
Relleno	Collections.fill(list, obj)	O(n)	Ninguno
Copia	Collections.copy(dest, src)	O(n)	dest.size() >= src.size()
Máximo	Collections.max(coll)	O(n)	Los elementos implementan Comparable
Mínimo	Collections.min(coll)	O(n)	Los elementos implementan Comparable
Frecuencia	Collections.frequency(coll, obj)	O(n)	Ninguno
Intercambio de elementos	Collections.swap(list, i, j)	O(1)	Índice válido
Rotación	Collections.rotate(list, distance)	O(n)	Ninguno

Notas

binarySearch() debe llamarse sobre una lista ya ordenada; el resultado devuelto para una lista no ordenada no está definido. Si la lista contiene elementos duplicados, no se garantiza cuál de ellos se encontrará.

Los envoltorios devueltos por synchronizedXxx() solo garantizan atomicidad a nivel de una única llamada al método. Las operaciones compuestas (como if(!list.contains(x)) list.add(x)) aún requieren un bloque synchronized externo.

Diferencias entre sort() y List.sort():

Desde Java 8, la interfaz List añadió el método predeterminado sort(Comparator).

list.sort(null) ordena usando el orden natural, equivalente a Collections.sort(list).

Ambos tienen la misma implementación subyacente, pero list.sort() es más conciso de escribir.

Recomendaciones de comparación de rendimiento:

Para cantidades pequeñas de datos (< 100 elementos), las diferencias de rendimiento entre los algoritmos son despreciables.

Para cantidades grandes de datos, binarySearch() es muy superior a la búsqueda lineal de indexOf().

Si se necesitan búsquedas frecuentes, considere usar HashSet en lugar de List; la complejidad de consulta es O(1).

Otras extensiones

Java Orientado a objetos

Java Tutorial avanzado

Algoritmos de colecciones de Java

Resumen de algoritmos de Collections

Ordenamiento (Sorting)

Ordenamiento por orden natural

Ejemplo

Ordenamiento con Comparator personalizado

Ejemplo: ordenar por longitud de cadena

Ejemplo: sintaxis Lambda

Barajado (Shuffling)

Ejemplo

Búsqueda binaria (Binary Search)

Ejemplo

Valores máximo y mínimo

Ejemplo

Conteo de frecuencia y verificación de disyunción

Ejemplo

Colecciones inmutables y envoltorios seguros para hilos

Colecciones inmutables (Unmodifiable)

Colecciones seguras para hilos (Synchronized)

Ejemplo

Resumen de operaciones de algoritmos comunes

Notas