Acerca de los problemas de clasificación del lenguaje c

Ordenar:

Hay 5 algoritmos de clasificación básicos que los programadores pueden utilizar:

·Ordenación por inserción (insertionsort.)

· exchangesOrt

·selectionsort (selectionsort)

·mergesort (mergesort)

·distributionsort (distributionsort)

Explicar visualmente cómo funciona cada algoritmo de clasificación funciona, veamos cómo se pueden usar estos métodos para ordenar una baraja de cartas barajada sobre la mesa. Las cartas deben ordenarse no sólo por palo (tréboles, diamantes, corazones y corazones negros), sino también por punto (del 2 al A).

El proceso de clasificación por inserción es: comience desde la parte superior de una pila de cartas, tome una carta a la vez y coloque las cartas en la posición correcta en su mano de acuerdo con el principio de clasificación. Después de tomar las cartas sobre la mesa, se clasifican las cartas que tienes en la mano.

El proceso de clasificación del intercambio es:

(1) Primero toma dos cartas y ponlas en tu mano. Si la carta de la izquierda se va a colocar detrás de la carta de la derecha, intercambie las posiciones de las dos cartas.

(2) Luego toma una carta, compara las dos cartas que están más a la derecha e intercambia las posiciones de las dos cartas si es necesario.

(3) Repite el paso (2) hasta tener todas las cartas en la mano.

(4) Si no es necesario intercambiar las posiciones de dos cartas en tu mano, significa que las cartas han sido ordenadas; de lo contrario, coloca las cartas en tu mano sobre la mesa y repite ( 1) a (4) ) pasos hasta que las cartas en la mano estén ordenadas.

El proceso de clasificación por selección es: busca la carta más pequeña entre las cartas de la mesa y mantenla en tu mano; repite esta operación hasta tener todas las cartas en tu mano.

El proceso de clasificación por combinación es: divide las cartas de la mesa en 52 montones, cada montón contiene una carta. Debido a que cada montón de cartas está ordenado (recuerde, solo hay una carta en cada montón en este momento), si combina dos montones adyacentes en un solo montón y ordena cada montón, obtendrá 26 montones de cartas ordenadas, que ahora contienen dos cartas. en cada pila. Repitiendo esta operación de fusión, puedes obtener 13 montones de cartas (cada montón tiene 4 cartas), 7 montones de cartas (hay 6 montones de 8 cartas y un montón de 4 cartas), y finalmente obtendrás 52 cartas de cartas. .

El proceso de clasificación por distribución (también llamado clasificación por base, es decir, clasificación por base) es: primero divida las cartas en 13 montones según sus puntos, y luego apile estos 13 montones de cartas en orden según sus puntos. ; Divida las cartas en 4 montones según el palo, y luego apile los 4 montones de cartas en orden del palo, y las cartas se ordenarán.

Al elegir un algoritmo de clasificación, también debe comprender los siguientes términos:

(1) Natural (natural)

Si un determinado algoritmo de clasificación es El La velocidad de clasificación de los datos ordenados es más rápida (la carga de trabajo se vuelve más pequeña), pero la velocidad de clasificación de los datos desordenados es más lenta (la variable de trabajo es grande). A este algoritmo de clasificación lo llamamos natural. Si los datos están casi ordenados, debe considerar el uso de un algoritmo de clasificación natural.

(2) Estable (estable)

Si un algoritmo de clasificación puede mantener el orden de los datos que considera iguales, llamamos a este algoritmo de clasificación estable.

Por ejemplo, existe la siguiente lista:

Mary Jones

Mary Smith

Tom Jones

Susie Cola

Si la lista anterior se ordena por apellido utilizando un algoritmo de clasificación estable, entonces "Mary Jones" y "Tom Jones" mantendrán el orden Jr original después de la clasificación, porque sus apellidos son los mismos.

El algoritmo de clasificación estable puede ordenar datos por palabras clave primarias y secundarias, como por apellido y nombre (en otras palabras, ordenar principalmente por apellido, pero los datos con el mismo apellido también deben ordenarse por nombre) ). En la implementación específica, primero se ordena por palabras clave secundarias y luego por palabras clave principales.

(3) Clasificación interna (clasificación interna) y clasificación externa (clasificación externa)

El método de clasificación en el que todos los datos a ordenar están en la memoria se denomina clasificación interna, y los datos que se van a ordenar se encuentran en Los métodos de clasificación en disco, cinta y otro almacenamiento externo se denominan clasificación externa.

Búsqueda:

Al igual que los algoritmos de clasificación, los algoritmos de búsqueda también son uno de los problemas más estudiados en informática. Los algoritmos de búsqueda y los algoritmos de clasificación están relacionados porque muchos algoritmos de búsqueda dependen del orden del conjunto de datos que se busca. Existen cuatro algoritmos de búsqueda básicos:

·Búsqueda secuencial.

· Búsqueda de comparación

· Búsqueda de base

· Hashing

A continuación Todavía tomo un par de tarjetas desordenadas como ejemplo para describir el proceso de trabajo de estos algoritmos.

El proceso de búsqueda secuencial es: mira cada carta empezando por la primera hasta encontrar la carta que buscas.

La búsqueda comparativa (también llamada búsqueda binaria, es decir, búsqueda binaria) requiere que las cartas hayan sido ordenadas. El proceso es: extrae una carta al azar. Si esta carta es exactamente la que estás buscando, busca El proceso. termina. Si la carta extraída es más grande que la carta que estás buscando, repite la operación de búsqueda en las cartas que están delante de ella; de lo contrario, repite la operación de búsqueda en las cartas que están detrás hasta que encuentres la carta que estás buscando;

El proceso de búsqueda de cardinalidad es: primero dividir las cartas en 13 montones según sus puntos, o en 4 montones según sus palos. Luego busque el montón de cartas que tengan el mismo número o palo que la carta que está buscando y luego use cualquier algoritmo de búsqueda para encontrar la carta que está buscando en este montón de cartas.

El proceso de búsqueda de hash es:

(1) Deje espacio en la mesa para varias pilas de cartas y construya una función que pueda colocar varias cartas. Según los puntos y palos, las tarjetas se asignan a un montón específico (esta función se llama función hash).

(2) Divide las cartas en varios montones según la función hash.

(3) Encuentre la pila donde está la tarjeta que está buscando según la función hash, y luego encuentre la tarjeta que está buscando en esta pila de tarjetas.

Por ejemplo, puedes construir una función hash de este tipo:

pila=rango+traje

Entre ellas, el rango es un valor que indica el número de cartas; palo es un valor que representa el palo de la pila de cartas representa el valor de la pila, que determina en qué pila se clasifica una carta. Si se utilizan 1, 2,...,13 para representar A, 2,... respectivamente. K usa 0, 1, 2 y 3 para representar tréboles, diamantes, corazones y espadas respectivamente, entonces el valor de la pila será 1, 2,..., 16, de modo que una baraja de cartas se puede dividir en 16 pilas.

Aunque la búsqueda hash parece un poco escandalosa, de hecho es un algoritmo de búsqueda muy práctico. Una variedad de programas, desde programas de compresión (como Stacker) hasta programas de almacenamiento en caché de disco (como SmartDrive), casi todos utilizan este método para mejorar la velocidad de búsqueda,

Ordenación o rendimiento de búsqueda:

Un problema importante con la clasificación y la búsqueda es la velocidad. Este problema a menudo se pasa por alto porque el tiempo dedicado a clasificar o buscar es casi insignificante en comparación con el resto del programa. Sin embargo, para la mayoría de las aplicaciones de clasificación o búsqueda, no necesita gastar mucho esfuerzo para programar un algoritmo al principio, sino que primero debe elegir el más simple entre los algoritmos existentes (ver 3.1 y 3.4), cuando encuentre que el algoritmo que está utilizando hace que el programa se ejecute muy lentamente, cambie a un algoritmo mejor (consulte la introducción a continuación).

A continuación se muestra una forma de juzgar la velocidad de un algoritmo de clasificación o búsqueda.

Primero, introduzca el concepto de complejidad del algoritmo, que se refiere a la cantidad de operaciones que deben completarse para ordenar o buscar en diversas situaciones (mejor, peor y promedio). El rendimiento de diferentes algoritmos puede ser. ser comparado.

La complejidad del algoritmo está relacionada con la cantidad de datos en el conjunto de datos para ordenar o buscar. Por lo tanto, se introduce una expresión basada en la cantidad de datos en el conjunto de datos para expresar la complejidad del algoritmo. algoritmo.

La complejidad del algoritmo más rápido es O(1), lo que significa que el número de operaciones del algoritmo no tiene nada que ver con la cantidad de datos. La complejidad O (N) (N representa la cantidad de datos en el conjunto de datos) significa que la cantidad de operaciones del algoritmo está directamente relacionada con la cantidad de datos. La complejidad O (logN) está entre las dos anteriores, lo que significa que el número de operaciones del algoritmo está relacionado con el logaritmo de la cantidad de datos. Un algoritmo con complejidad O(NlogN) (N veces logN) es más lento que un algoritmo con complejidad O(N), que es incluso más lento que un algoritmo con complejidad O(N2).

Nota: Si la complejidad de ambos algoritmos es O(logN), entonces el algoritmo con una base mayor de logN será más rápido. En los ejemplos de este capítulo, las bases de logN son ambas 10< /. p>