Descripción general del algoritmo/Ideas
La clasificación de fusión se basa en una estrategia llamada "Divide y conquista". La idea básica es la siguiente:
1. Para dos matrices ordenadas, para fusionarlas en una matriz ordenada, podemos escribir fácilmente el siguiente código:
// tanto A como B es ascend.public void fusion (int [] a, int [] b, int [] c) {int i = 0, j = 0, k = 0; while (i <= A.Length && j <= B.Length) {if (a [i] <= b [i]) {c [k ++] = a [i ++]; } else {c [k ++] = b [j ++]; }} while (i <= a.length) {c [k ++] = a [i ++]; }} Es fácil ver que tal algoritmo de fusión es eficiente y su complejidad de tiempo puede llegar a O (N).
2. Si hay una matriz desordenada que necesita ser ordenada, pero sus dos subarrays completamente divididos se ordenan por separado, también podemos implementarlos fácilmente con la ayuda del código anterior;
3. Entonces, ¿qué debo hacer si A y B están desordenados? Puedes dividirlos en matrices más pequeñas.
4. Si lo divide hasta el más pequeño, cada subarría solo tiene un elemento, se puede considerar como una matriz ordenada.
5. Comience con estas matrices más pequeñas, fusionas con los pasos anteriores, y se organiza toda la matriz.
En resumen, la clasificación de fusiones es usar la recursión, primero descomponer la matriz en una subarray y luego fusionar la matriz.
ejemplo
Aquí hay un ejemplo. Si desea ordenar la matriz a = {2,1,3,5,2,3}, divida la matriz en dos subarrays: {2,1,3} y {5,2,3}. Después de clasificar estas dos subarrías, se convierten en {1,2,3} y {2,3,5}, y luego fusionan las dos matrices para obtener la matriz ordenada final. La implementación del código es la siguiente:
void sort (int [] a) {int [] aux = new int [a.length]; // aux matriz mergesort (a, 0, a.length - 1, aux);} void Mergesort (int [] a, int lo, int hi, int [] aux) {if (hi <= lo) return; int mid = lo + (hi - lo) / 2; Mergesort (a, lo, mid, aux); Mergesort (a, mediano + 1, hola, aux); fusion (a, lo, mid, hi, aux);} void fusion (int [] a, int lo, int mid, int hi, int [] aux) {int i = lo, j = medid + 1; para (int k = lo; k <= hi; k ++) {aux [k] = a [k]; } para (int k = lo; k <= hi; k ++) {if (i> mid) a [k] = aux [j ++]; else if (j> hi) a [k] = aux [i ++]; else if (aux [i] <= aux [j]) a [k] = aux [i ++]; else A [k] = aux [j ++]; }} Otra implementación: clasificación de fusión de abajo hacia arriba
En la implementación anterior, es equivalente a dividir un gran problema en pequeños problemas y resolverlos por separado, y luego usar las respuestas a todos los pequeños problemas para resolver todo el gran problema. Dividir el tipo de matriz grande en una pequeña matriz El tipo de tipo es de arriba hacia abajo. Hay otra implementación que es la clasificación de abajo hacia arriba, es decir, primero fusionar dos y luego fusionar cuatro y cuatro ... La implementación del código es la siguiente:
sort void (int [] a) {int n = a.length; int [] aux = new int [n]; for (int sz = 1; sz < N; sz += sz) { for (int lo = 0; lo < N - sz; lo += sz + sz) { //In each round of merge, the second sub-array that was merged the last time may be smaller than the first sub-array merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux); }}}