Ordenación por combinación, algoritmo de ordenación por combinación
La clasificación por fusión es un algoritmo de clasificación eficaz y estable basado en operaciones de fusión. Utiliza un método muy clásico de dividir y conquistar (dividir y conquistar puede entenderse en términos generales como dividir un territorio en varias partes pequeñas y luego ocuparlas). y conquistarlas una por una. Las pequeñas partes descompuestas son diferentes facciones políticas u otras cosas, y luego alejarlas entre sí. La idea de clasificación por fusión es muy simple. La idea de ordenar es simple y la velocidad es tan buena como la de ordenación rápida.
Idea básica:
Paso uno: Divide los números de la secuencia a ordenar en varios grupos, uno para cada número.
Paso 2: Fusiona varios grupos de dos en dos para asegurarte de que todos los grupos fusionados estén en orden.
Paso 3: Repite el paso 2 hasta que quede el último conjunto de secuencias ordenadas.
Pasos detallados:
Primero, ordene los números de la matriz en varios grupos, cada número es un grupo.
Compare y combine los dos grupos adyacentes para garantizar que el resultado combinado sea una matriz ordenada i (número 8) > j (número 4) necesita intercambiar posiciones (presentando finalmente una matriz ascendente), comparar y fusionar Los dos últimos números se convierten en un puntero nulo.
Los demás grupos se fusionan de esta forma, pasando de 8 grupos a 4 grupos.
Continúa fusionando dos grupos adyacentes.
Defina dos variables i y j, que representan el primer valor en P1 (4) y el primer valor en P2 (5) respectivamente. Compare i y j, es decir, i < j (4 <5), mueva el número 4 a p y retroceda i una posición.
Compare i y j, i>j (8>5), mueva el número 5 a p (un dígito después de 4) y j un dígito atrás.
i y j continúan comparando, i>j (8>7), mueve el número 7 a p (un lugar detrás de 5), no hay ningún número para ordenar en p2, por lo que la comparación finaliza, p1 Los dígitos restantes se mueven a p (un dígito después de 7) y finaliza la fusión. Se fusionan dos secuencias adyacentes de la misma manera y finalmente se obtienen dos secuencias ordenadas, que continúan fusionándose de la manera anterior.
Comparando i y j, i>j (4>1), i no se mueve, el número 1 en p2 se mueve a p y j retrocede una posición.
i continúa comparándose con j, i>j (4>2), el número 2 se mueve a p (un dígito después de 1) y j se mueve un dígito detrás.
i continúa comparándose con j, i>j (4>3), el número 3 se mueve a p (el segundo dígito de 2) y j se mueve una posición hacia atrás.
i continúa comparándose con j, i< j (4<6), el número 4 pasa a p (el último dígito de 3) y i retrocede una posición.
i continúa comparándose con j, i< j (5<6), el número 5 pasa a p (el último dígito de 4) y i retrocede una posición.
i continúa comparándose con j, i>j (7>6), el número 6 se mueve a p (un lugar después de 5), no hay más números para ordenar en p2, por lo que la comparación termina, en p1 Los dígitos restantes de se mueven a p (un dígito después de 6).
El resultado final es una secuencia ordenada y se completa la clasificación sumergida.
El código fuente es el siguiente:
#include
#include
void G_qsort (int*a, int primero, int mid, int last, int*temp).
{
int n= mid, m= last.
int k=0.
int i= primero, j= mid+1.
while (i<=n&&j<=m)// Ordenar ambos lados en el mismo tiempo.
{
si (a[i]<=a[j])//i y j se comparan.
{
temp[k++]=a[i++]; //si i<=j, el valor de i se mueve a temp.
}
else.
{
temp[k++]=a[j++] //Si i> j, entonces El valor de j se mueve dentro de temp.
}
}
mientras (i<=n).
{
temp[k++] =a[i++].
}
mientras (j<=m).
{
temp[k++]=a [j++].
}
para (i=0; i< k; i++).
{
a[primero +i]=temp[i].
}
}
void G_sort (int*a, int primero, int último, int*temp).
{
if (primero <último)// Finaliza el juicio cuando se alcanza un número al mismo tiempo.
{
int mid=(first+last)/2; //Encuentra el valor medio.
G_sort(a, first, mid, temp); // Función recursiva izquierda.
G_sort(a, mid+1, last, temp); //derecha.
G_qsort(a, primero, medio, último, temporal); // Ordenar.
}
}
int sort (int*a, int n).
{
int*p= malloc(n); // Asignar tamaño de memoria.
if (p==NULL)
{
return-1.
}
else.
{
free(p).
G_sort(a, 0, n-1, p); // Llama a la función pasando los parámetros, 0 y n-1 es el primer y último subíndice numérico.
p= NULL.
return1.
}
}
int main().
p>
{
int a[8]={8, 4, 5, 7, 1, 3, 6, 2}.
int i;
sort(a, 8); // Llama a la función pasando parámetros.
for (i=0; i<8; i++).
{
printf("%d", a[i]).
p>
}
printf("\n").
return0.
}