Algoritmos de Búsqueda y Ordenación en Java: Binaria, Selección, Inserción y Fusión

Algoritmos de búsqueda y ordenación en Java

Búsqueda binaria (O(log n))

public static int buscar(int[] vector, int x) {
int inicio = 0;
int fin = vector.length - 1;
while (inicio <= fin) {
int medio = (inicio + fin) / 2;
if (vector[medio] < x)
inicio = medio + 1; // Examinar mitad derecha
else if (vector[medio] > x)
fin = medio - 1; // Examinar mitad izquierda
else // Encontrado
return medio;
}
return -1; // No está
}

Ordenación por selección (O(n²))

public static void ordenarSelección(int[] vector) {
for (int i = 0; i < vector.length - 1; i++) {
// Buscar posición del menor elemento entre i y el final
int posMenor = i;
for (int j = i + 1; j < vector.length; j++) {
if (vector[j] < vector[posMenor])
posMenor = j;
}
// Intercambiar elementos en posiciones i y posMenor
int aux = vector[i];
vector[i] = vector[posMenor];
vector[posMenor] = aux;
}
}

Ordenación por inserción (O(n²))

public static void ordenarInserción(int[] vector) {
for (int i = 1; i < vector.length; i++) {
int temp = vector[i];
int j = i - 1;
while (j >= 0 && temp < vector[j]) {
vector[j + 1] = vector[j];
j--;
}
vector[j + 1] = temp;
}
}

Ordenación por fusión, 1.ª implementación (O(n log n))

public static void ordenarFusión(int[] v) {
if (v.length > 1) {
// Dividir el vector en dos mitades
int medio = v.length / 2;
int[] mitad1 = Arrays.copyOfRange(v, 0, medio);
int[] mitad2 = Arrays.copyOfRange(v, medio, v.length);
// Ordenar cada mitad por separado
ordenarFusión(mitad1);
ordenarFusión(mitad2);
// Mezclar las mitades ordenadas
int[] mezcla = mezclarVectores(mitad1, mitad2);
for (int i = 0; i < v.length; i++)
v[i] = mezcla[i];
}
}

Mezcla de vectores ordenados (O(n))

public static int[] mezclarVectores(int[] v1, int[] v2) {
int[] v3 = new int[v1.length + v2.length];
int i1 = 0, i2 = 0, i3 = 0;
// Repetir mientras queden datos en los dos vectores.
while (i1 < v1.length && i2 < v2.length) {
if (v1[i1] < v2[i2])
v3[i3++] = v1[i1++];
else
v3[i3++] = v2[i2++];
}
// Copiar los elementos que queden en v1 o en v2.
while (i1 < v1.length)
v3[i3++] = v1[i1++];
while (i2 < v2.length)
v3[i3++] = v2[i2++];
return v3;
}