Implementación de un programa en C para comparar las ventajas y desventajas de varios algoritmos de clasificación clásicos
1. Algoritmo de clasificación de bajo nivel
1. Clasificación por selección
(1) Proceso de clasificación
Dado un conjunto numérico, bucle a través de Set, cada vez que lo recorra, seleccione el elemento más pequeño o más grande del conjunto y colóquelo al principio o al final del conjunto. El siguiente bucle atravesará el conjunto de elementos restante para encontrar el más pequeño y operar como se indicó anteriormente. , se recorrerán todos los elementos del conjunto original. Listo, la clasificación ha terminado.
(2) Código de implementación
//Método de clasificación de selección
plantilla
void Sort::SelectSort (T* array, int tamaño)
{
int minIndex;
for (int i = 0; i lt; tamaño; i )
{
minIndex = i;
for (int j = i 1; j lt; tamaño; j )
{
if (matriz [minIndex] gt; matriz[j])
{
minIndex = j;
}
}
if (minIndex != i)
{
Intercambiar (matriz, i, minIndex);
}
}
}
(3) Resumen del análisis
La complejidad temporal de la clasificación de la selección es relativamente alta, alcanza O (n ^ 2), y cada selección debe atravesarse una vez Intervalo desordenado. La clasificación por selección tiene buena eficiencia para un tipo importante de secuencia de elementos, es decir, el tamaño del elemento es grande, pero el código de clasificación es relativamente pequeño. Otra cosa a tener en cuenta es que la clasificación por selección es un método de clasificación inestable.
2. Clasificación de burbujas
(1) Proceso de clasificación
El proceso de clasificación de burbujas es, como su nombre indica, comparar dos elementos adyacentes en secuencia. , teniendo prioridad. Los elementos de nivel superior (más grandes o más pequeños) retroceden hasta llegar al final de la secuencia y el intervalo desordenado se reduce en consecuencia. La próxima vez, la operación de burbujeo se realiza desde el intervalo desordenado y el ciclo se repite hasta que el intervalo desordenado llega a 1 y finaliza la clasificación.
(2) Código de implementación
//Método de clasificación de burbujas
plantilla
void Sort::BubbleSort(T* array, int tamaño)
{
para (int i = 0; i lt; tamaño; i )
{
para (int j = 1; j lt; tamaño - i; j )
{
si (matriz[j] lt; matriz[j - 1])
{
Intercambiar(matriz, j, j - 1);
}
}
}
}
(3) Resumen del análisis
La complejidad temporal de la clasificación de burbujas también es relativamente alta, alcanzando O (n ^ 2). Cada vez que atraviesa el intervalo desordenado, la prioridad será. Los elementos altos se mueven al final del rango desordenado. La clasificación por burbujas es un método de clasificación estable.
2. Algoritmo de clasificación avanzado
(1) Proceso de clasificación
El principio de clasificación por fusión es relativamente simple y también se basa en la idea de dividir y conquistar. Divide la secuencia de elementos que se van a ordenar en dos subsecuencias de igual longitud, clasifica cada subsecuencia y luego las fusiona en una sola secuencia.
(2) Código de implementación
//Merge sort
plantilla
void Sort::MergeSort(T* array, int left , int derecha)
{
if (izquierda lt; derecha)
{
int mid = (izquierda derecha) / 2 ;
MergeSort(matriz, izquierda, mitad);
MergeSort(matriz, mitad 1, derecha);
Fusionar(matriz, izquierda, mitad, derecha) );
}
}
//Fusionar dos subcadenas ordenadas
plantilla
void Sort ::Fusionar (T* matriz, int izquierda, int media, int derecha)
{
T* temp = new T[derecha - izquierda 1];
int i = izquierda, j = mid 1, m = 0;
mientras (i lt; = mid amp; amp; j lt; = derecha)
{
if (matriz[i] lt; matriz[j])
{
temp[m] = matriz[i];
}
else
{
temp[m ] = matriz[j ];
}
}
mientras (i lt; = mid)
{
temp[m] = matriz[i];
}
mientras (j lt; = derecha)
{
temp[m] = matriz[j];
}
for (int n = izquierda, m = 0; n lt; = derecha; n, m)
{
array[n] = temp[ m];
}
eliminar temp;
}
(3) Resumen del análisis
Fusionar ordenar Lo mejor, lo peor y la complejidad del tiempo promedio son todas O (nlogn), que es un algoritmo de clasificación estable.