Clasificación interna (la clasificación en la memoria no requiere acceso a la memoria externa) Clasificación externa (la clasificación es muy grande y finalmente se completa leyendo y escribiendo por lotes en la memoria externa)
Clasificación estable y clasificación inestable Clasificación estable: vea si el orden relativo del mismo registro cambiará. Depende principalmente de si la comparación durante el proceso de clasificación son registros adyacentes. Si se trata de una comparación adyacente, debe ser de tipo estable. Si no es una comparación adyacente, es inestable.
Métodos de clasificación interna Hasta ahora, varios métodos de clasificación interna se pueden resumir en las siguientes cinco categorías:
(1) Clasificación por inserción (2) Clasificación por intercambio (3) Clasificación por selección; ; (4) Fusionar y ordenar; (5) Ordenar por base.
Clasificación por inserción: incluye ordenación por inserción directa y ordenación Hill.
Clasificación por inserción directa: (estable)
Descripción del algoritmo
Algoritmo void in sort (sqList & amp; l) para inserción directa y clasificación de archivos secuenciales F ∧
{ int i, j;
for(I = 2; i & lt= L.leni++) ∨ insertar n-1 registros ∨.
{
if(L.R[i].Key
{ L . R[0]= L . R[I]; ∑ registro a insertar Primero almacenado en la columna de monitoreo
Longitud R[I]= L
for(j = I-2; regla legal[0]. Clave
Longitud R[j+1]= L . 0]; ∨El R[i] original se inserta en la posición de j+1∨
}
}
}
<. p>Análisis de algoritmo.Supongamos que el número de comparaciones clave en la clasificación es C, el tiempo mínimo de C se registra como Cmin y el tiempo máximo se registra como Cmax. 1) En la secuencia original (secuencia positiva), cada inserción. Un R [i] solo necesita comparar la clave una vez, es decir:
(2) Cuando se invierte el orden original (claves grandes). a pequeño), cada R [i] insertado debe compararse con la clave en la subtabla i-1 para comparar, más la comparación con su propio R [0], el número de comparaciones es el mayor en este momento. , es decir:
(3) Registre el número total de movimientos m (el tiempo mínimo de m se registra como mmin, el registro de tiempo máximo es mmax)
En la secuencia positiva , los registros en la subtabla se eliminan, es decir:
En la secuencia inversa, insertar R [i] requiere mover toda la subtabla. El número de movimientos es 2+(i-1)=i+. 1. En este momento, el número de movimientos del banco de trabajo es el mayor, es decir:
La complejidad temporal de la clasificación está en el orden con mayor consumo de tiempo. Por lo tanto, T (n) = O. (n2) después de la clasificación por inserción directa.
La clasificación Shell (Hill) también se denomina clasificación de "incremento de contracción" (inestable): (clasificación por burbujas y clasificación rápida)
Descripción de. algoritmo de clasificación de burbujas
void bub sort(sqList & amp; l)
{ int i, flagflag es la bandera para el intercambio de registros
Vuelva a escribir temp
for(I = l . len; i>=2;I-) ∨n-1 como máximo ∨ /p>
{ flag = 0 //Registra si se produce intercambio en cada viaje
for(j = 1; j & lt= I-1; j++)∑ Una burbuja Ordenar ∧
if (L.R[j].key & gtL.R[j+1). ].
clave) ∥Comparación por pares∨
{ temp = L . r[j+1]∩
Longitud R[j]= L ;
Longitud r[j+1]= temp;
flag = 1;
}
if(flag = = 0)break;∑Cuando no se intercambian registros, se completa la clasificación
}
}
Análisis de algoritmos
Supongamos que la longitud de la cola es n y el número total de comparaciones clave en el algoritmo es c. No hay intercambio de registros en el primer paso. Salga del ciclo, Cmin = n-1 = O (n); si está en orden inverso, debe ordenarse n-1 veces y el número de comparaciones para cada clave es. i-1 (2≤i≤n), entonces:
Del mismo modo, el número máximo de movimientos registrados es:
Por lo tanto, la complejidad temporal de la clasificación de burbujas es T(n) =O(n2). Y es estable.
Clasificación rápida: (inestable, complejidad temporal O(nlogn)), sin espacio auxiliar, pero hay mejores y peores.
Algoritmo de partición
int partición (Sqlist y ampl, entero bajo, entero alto)
{ L . ;
pivotkey=L.R[bajo]. clave;
mientras(bajo
{ while(bajo=pivotkey)
-alto;
Longitud R[bajo]= L R[Alto];
Aunque (Bajo
++Nivel Bajo;
Longitud R[Alto] = L . R[Bajo];
p>
}
Retorno bajo;
}
Función de control principal:
void QSort(Sqlist & amp; l , entero bajo, entero alto)
{if (bajo
{
pivotloc=Partición(L, bajo, alto);
QSort(L, bajo, pivotloc-1);
QSort(L, pivotloc+1, alto);
}
}
Método de llamada: QSort(L, 1, L, length);
Si tiene preguntas sobre el examen de ingreso de posgrado, no sabe cómo resumir el contenido del centro de exámenes de ingreso de posgrado. o no conoce la política local para el registro de exámenes de ingreso de posgrado, haga clic en Consultar el sitio web oficial en la parte inferior para obtener materiales de revisión de forma gratuita:/xl/