Introducción
La complejidad de Mergesort para las entradas que se han ordenado en reversa es O (n^2), y Timsort se genera optimizando la mergesort para esta situación. La complejidad promedio es n*o (log n), el mejor caso es o (n), y el peor de los casos es n*o (log n). Y Timsort es un tipo de estabilidad. La idea es dividir primero la columna ordenada, y luego fusionar las particiones, que se ve igual que el paso de Mergesort, pero hay algunas optimizaciones para los datos inversos y a gran escala.
Idea de optimización de clasificación de fusión
Existen varios métodos de optimización para la clasificación de fusiones:
Al igual que la clasificación rápida, puede usar la clasificación de insertos o seleccionar la clasificación para matrices pequeñas para evitar llamadas recursivas.
Antes de que se llame a la fusión (), puede determinar si un [Mid] es menor o igual a un [Mid+1]. Si es así, entonces no hay necesidad de fusionarse, la matriz ya está ordenada. La razón es muy simple. Dado que los dos subarrays ya están ordenados, un [Mid] es el valor máximo de la primera subarray, y un [Mid+1] es el valor mínimo de la segunda subarray. Cuando A [Mid] <= A [Mid+1], la matriz se ordena en su conjunto.
Para ahorrar tiempo para copiar elementos en la matriz auxiliar, los roles de la matriz original y la matriz auxiliar se pueden intercambiar en cada nivel de la llamada recursiva.
El proceso de fusión en el método Merge () debe determinar si I y J han cruzado el límite, es decir, la mitad del borde se ha utilizado. Otra forma de eliminar el código que detecta si la mitad del lado se ha agotado. El paso específico es copiar la segunda mitad de la matriz a [] a aux [] en orden descendente, y luego fusionarse desde ambos extremos. Para las matrices {1,2,3} y {2,3,5}, la primera subarray se copia como de costumbre, y el segundo se copia de detrás al frente, y el elemento final en aux [] es {1,2,3,5,3,2}. La desventaja de este método es que hace que la clasificación de fusión se convierta en una clasificación inestable. La implementación del código es la siguiente:
Void Merge (int [] a, int lo, int mid, int hi, int [] aux) {for (int k = lo; k <= mid; k ++) {aux [k] = a [k];} for (int k = mid+1; k <= hi; k ++) {aux [k] = a [hi -k+mid+1];} int i = lo, j = hi; Hi; // Desde los dos extremos al medio para (int k = lo; k <= hi; k ++) if (aux [i] <= aux [j]) a [k] = aux [i ++]; de lo contrario a [k] = aux [j--];}Pasos de Timsort
Dividir
La idea de partición es escanear la matriz una vez y usar la secuencia positiva continua (si se clasifica el orden ascendente, entonces la secuencia positiva es una secuencia ascendente) o [estrictamente] (para garantizar la estabilidad del algoritmo de clasificación) como una partición (ejecución). Si se trata de una secuencia inversa, revierta los elementos en la partición. Por ejemplo
1, 2, 3, 6, 4, 5, 8, 6, 4 Los resultados de la partición son
[1,2,3,6], [4,5,8], [6,4]
Luego revertir la secuencia inversa
[1,2,3,6], [4,5,8], [4,6]
unir
Considere un ejemplo extremo, por ejemplo, las longitudes de las particiones son 10000, 10, 1000, 10, 10 y 10, por supuesto, esperamos fusionar 10 10 en 20, 20 y 1000 en 1020 primero. Si nos fusionamos de izquierda a derecha, usaremos la matriz 10000 y la combinación de pequeños números cada vez, lo cual es demasiado costoso. Por lo tanto, podemos usar una estrategia para optimizar el orden de las fusiones.
Ejemplo
Tomando comparableTimSort.sort () en Java como ejemplo, se usa una pila de ejecución para determinar si debe fusionarse.
if (nremaining <min_merge) {int initrunlen = cournandmakeascending (a, lo, hi); binarysort (a, lo, hola, lo + initrunlen); devolver; }Ordenar menos que min_merge (32) y ordenar directamente con la inserción binaria después de la partición
int minrun = minrunLength (nrEemining); Do {// Encuentre la posición inicial de la siguiente partición, y también voltee la secuencia inversa int runlen = countrunandmakeascending (a, lo, hola); // Asegúrese de que las carreras en la pila de ejecuciones sean mayores que Minrun. Si la partición actual es demasiado pequeña, elimine los elementos de la espalda para compensar si (runlen <minrun) {int force = nremaining <= minrun? Nremeining: Minrun; binarysort (a, lo, lo + force, lo + runlen); runlen = force; } // colocar correr en la pila de ejecución ts.pushrun (lo, runlen); // juzga si debe fusionarse. Comienza desde la parte superior de la pila y sé que no se puede fusionar // 1. runlen [i - 3]> runlen [i - 2] + runlen [i - 1] // 2. runlen [i - 2]> runlen [i - 1] ts.mergecollapse (); lo += runlen; nremeining -= runlen; } while (nremeining! = 0); // fusionar todas las ejecuciones restantes para completar la clasificación de clasificación Afirmar lo == HI; // fusionar la ejecución restante ts.mergeforceColapse (); afirmar ts.stacksize == 1;Mirando una función más importante
/ *** Si las longitudes de las últimas 2 corridas se agregan más tiempo que la anterior, use la ejecución en la posición media y la ejecución con una longitud delantera y posterior más corta para fusionar*si las longitudes de las últimas 2 corridas se agregan más cortas que la anterior, luego fusione las dos ejecuciones*/ privado void mergolapse () if (n> 0 && runlen [n-1] <= runlen [n] + runlen [n + 1]) {if (runlen [n-1] <runlen [n + 1]) n--; MERIGUD (N); } else if (runlen [n] <= runlen [n + 1]) {MERGEAT (n); } else {break; // se establece invariante}}