Explicación detallada del tipo de combinación
Fusionar subsecuencias ordenadas para obtener una secuencia completamente ordenada; es decir, ordenar cada subsecuencia primero y luego ordenar entre fragmentos de subsecuencia. Fusionar dos listas ordenadas en una lista ordenada se denomina fusión bidireccional.
Trate la secuencia R[0.....n-1] a ordenar como n secuencias ordenadas de longitud 1, combine listas ordenadas adyacentes en pares y obtenga una longitud de 2 n/2 ordenadas listas; luego combine estas secuencias ordenadas para obtener n/4 secuencias ordenadas de longitud 4 y así sucesivamente, finalmente obtenga una secuencia ordenada de longitud n;
Para fusionar, necesitas hacer dos cosas:
1) Descomponer: dividir la secuencia en dos partes a la vez
2) Fusionar: dividir la secuencia secuencia en dos Fusionar las partes divididas en pares y luego ordenarlas
¿Cómo fusionar?
Durante cada proceso de fusión, se fusionan y luego se ordenan dos fragmentos de secuencia ordenados. Los dos segmentos de secuencia ordenados son R [bajo, medio] y R [medio 1, alto]. Primero se fusionan en una matriz temporal localizada R2 y luego se copia R2 a R una vez completada la fusión.
Tome un registro de los dos segmentos para comparar claves a la vez, luego coloque el registro más pequeño en R2 y finalmente copie el resto de cada segmento directamente en R2. Después de este proceso, R2 es una secuencia ordenada, que luego se copia nuevamente a R.
En una determinada fusión, suponiendo que la longitud de cada subtabla es un espacio, entonces hay sublistas ordenadas con n/espacio en R[0....n-1] antes de la fusión. Tabla: R[0... .gap-1], R[gap... .2*gap-1], ..., R[(n/gap)*gap...n-1].
Al fusionar subtablas adyacentes, se deben manejar casos especiales de tablas:
1) Si el número de subtablas es impar, la última subtabla no no es necesario fusionarlo con otras subtablas (es decir, la ronda de procesamiento de este itinerario está vacía);
2) Si el número de subtablas es un número par, el límite superior de la el intervalo desde la última subtabla hasta el último par de subtablas en el par de subtablas es n-1;
Complejidad temporal: la forma de clasificación por subfusión es un árbol binario. de recorridos requeridos es la profundidad del árbol binario y la complejidad del tiempo es O (nlogn).
Complejidad del espacio: este algoritmo requiere un espacio de almacenamiento temporal de tamaño n para guardar la secuencia fusionada.
Estabilidad del algoritmo: en la ordenación por fusión, el orden de los elementos iguales no cambia, por lo que es un algoritmo estable.
Resumen:
1) Complejidad temporal: O(nlogn)
2) Complejidad espacial: O(n)
3) Estabilidad: Estable
4) Complejidad: Más compleja
1) Consideraciones sobre la complejidad del espacio: Seleccione prioridades para [Heap Sort gt; Quick Sort gt;
2) Consideraciones de estabilidad: se debe elegir la clasificación por combinación, ya que tanto la clasificación en montón como la clasificación rápida son inestables.
3) Considerando la velocidad media de clasificación: Se debe seleccionar Clasificación rápida.
import java.util.Arrays
/**
* Ordenar por fusión
* La eficiencia es O(nlogn), merge No hay diferencia en eficiencia entre los mejores, promedio y peores casos de uso y es adecuado para ordenar listas grandes basadas en particiones.
*/
public class MergeSort {
public static void main(String[] args) {
int[] array = {9, 1, 5, 3, 4, 2, 6, 8, 7};
MergeSort merge = new MergeSort();
System.out.println("Antes ordenando: " Arrays.toString(array));
merge.sort(array);
System.out.println("Después de ordenar: " Arrays.toString(array)) ;
}
private static int[] sort(int[] list){
for(int gap = 1; gap lt; list.length; espacio = 2*espacio){
MergePass(lista, espacio, lista.longitud);
System.out.println("espacio=" espacio "：" Arrays.toString( lista));
}
lista de retorno
}
vacío estático privado MergePass(int[] arr, int gap, int length){
int i=0;
// Fusiona dos sublistas de longitud de espacio adyacentes
for(i= 0; i 2*gap-1 lt; longitud; i = i 2*espacio){
Fusionar(arr, i, i espacio - 1, i 2 * espacio - 1);
}
// Las dos subtablas restantes, la longitud de esta última es menor que el espacio
if (i espacio - 1 lt; longitud) {
Merge(arr , i, i espacio - 1, longitud - 1);
}
}
}
fusión estática privada privada (int [ ] arr, int low, int mid, int high){
int i = low; // i es el subíndice de la primera secuencia
int j = mid 1; j es el subíndice de la segunda secuencia
int k = 0; // k es el subíndice del espacio de almacenamiento temporal de la secuencia fusionada
int[] array2 = new int[ high - low 1]; // array2 es el índice de la secuencia fusionada temporal
// Escanea la primera y segunda secuencia hasta que una de las secuencias finalice
while (i lt; = mid & j lt;= high) {
// Determina qué número tomado de la primera y segunda secuencia es más pequeño, colócalo en la secuencia fusionada y luego continúa escaneando hacia abajo
if (arr[i] lt; = arr[j]) {
matriz2[k]
= arr[i];
i
k
} más {
matriz2[k] = arr[j] ;
j ;
k ;
p> }
}
// Si el primer If la secuencia no ha sido escaneada, cópiela toda en la secuencia fusionada
while(i lt; = mid){
array2[k] = arr[i];
p>i ;
k ;
}
// Si la segunda secuencia aún no ha sido escaneada, cópiala toda para fusionarla. secuencia
while(j lt; = alto){
array2[k] = arr[j];
j;
k ;
}
// Copia la secuencia fusionada en la secuencia original
para (k = 0, i = bajo; i lt; = alto; i, k) {
arr[i] = array2[k];
}
}
Resultados en ejecución:
Antes de ordenar: 915342687?
gap?=?1: 193524687?
gap?=?2: 135924687?
gap?= ?4: 123456897?
¿brecha?=?8: 123456789?
Después de ordenar: 123456789?