¿Cuántos algoritmos de clasificación existen?

La clasificación es una operación importante en la programación informática. Su función es reorganizar una secuencia arbitraria de elementos de datos (o registros) en una secuencia ordenada por palabras clave.

Ordenar es ordenar los elementos de una colección en un orden determinado. En términos generales, hay dos tipos de clasificación, orden ascendente y orden descendente. Hay 8 clasificaciones básicas en el algoritmo:

(1) Clasificación por burbujas

(2) Clasificación por selección; ;

(3) Clasificación por inserción

(4) Clasificación por colinas

(5) Clasificación por fusión

(6) Clasificación rápida;

(7) Clasificación por base;

(8) Clasificación en montón;

(9) Clasificación por conteo; 10 ) clasificación de cubos.

Clasificación por inserción

El algoritmo de clasificación por inserción se basa en la situación en la que una secuencia ya está organizada en orden y agrega elementos de acuerdo con el método de clasificación original insertando un elemento a la vez. . Esta comparación se realiza desde el final de la secuencia ordenada, es decir, el elemento que se insertará en la secuencia se compara primero con el elemento más grande de la secuencia ordenada. Si es mayor que el elemento más grande, se puede insertar directamente después. el elemento más grande. Si, en caso contrario comparar y buscar con el bit anterior hasta encontrar la posición que se debe insertar. La idea básica de la ordenación por inserción es insertar un registro para ordenarlo en la subsecuencia previamente ordenada de acuerdo con su tamaño de clave cada vez, y encontrar la posición más adecuada hasta que se inserten todos los registros. Durante la ejecución, si se encuentra una posición igual al elemento insertado, el elemento a insertar se colocará después del elemento igual, por lo que el orden de la secuencia original no cambiará después de insertar el elemento. Creemos que la clasificación por inserción también es un método de clasificación estable. La clasificación por inserción se divide en tres categorías: clasificación por inserción directa, clasificación por media inserción y clasificación Hill.

Clasificación de burbujas

El algoritmo de clasificación de burbujas mueve elementos más pequeños hacia adelante o elementos más grandes hacia atrás. Este método compara principalmente el tamaño de dos elementos adyacentes e intercambia las posiciones de los dos elementos de acuerdo con los resultados de la comparación y las reglas del algoritmo. De esta manera, el propósito de ordenar se puede lograr comparando e intercambiando uno por uno. La idea básica de la clasificación de burbujas es comparar primero las claves del primer y segundo registro, si están en orden inverso, intercambiar los dos registros y luego comparar las claves del segundo y tercer registro. así sucesivamente, repita el cálculo anterior hasta que se complete la comparación entre las (n-1)ésimas y enésimas palabras clave registradas, y luego realice la segunda y tercera clasificación de acuerdo con el proceso anterior hasta que toda la secuencia esté en orden. Se debe prestar especial atención al proceso de clasificación. Cuando dos elementos adyacentes son del mismo tamaño, no es necesario intercambiar posiciones en este paso. Por lo tanto, la clasificación de burbujas es un algoritmo de clasificación estricto y estable que no cambia los mismos elementos. en la secuencia. relación posicional relativa entre ellos.

Clasificación por selección

La idea básica del algoritmo de clasificación por selección es seleccionar el elemento más pequeño actual para cada posición. La idea básica de la clasificación por selección se basa en dos métodos básicos de clasificación simples: clasificación por selección directa y clasificación en montón. Primero, seleccione todos los elementos comenzando desde la primera posición, seleccione el más pequeño entre todos los elementos para esta posición, luego seleccione la segunda posición, seleccione el más pequeño entre los elementos restantes para esta posición y así sucesivamente. Repita la selección del "elemento mínimo"; hasta que se complete la selección del elemento en la (n-1)ésima posición, entonces solo quedará el elemento más grande en la enésima posición, y no se requiere más selección en este momento. Al utilizar este tipo de clasificación, se debe prestar atención a uno de los detalles que es diferente del método de burbujeo. Por ejemplo: secuencia 58539. Sabemos que el primer elemento "5" seleccionado en la primera pasada se intercambiará con el elemento "3", por lo que el orden relativo entre los dos elementos idénticos "5" en la secuencia original cambiará. Por lo tanto, decimos que la clasificación por selección no es un algoritmo de clasificación estable y destruirá la estabilidad durante el proceso de cálculo.

Clasificación rápida

La idea básica de la clasificación rápida es utilizar un algoritmo de clasificación de un solo paso para dividir los elementos de la secuencia que se van a clasificar en dos bloques grandes, donde los Los elementos de una parte deben ser menores o iguales que los elementos de otra parte de la secuencia, y luego realizar el algoritmo de clasificación rápida nuevamente en los elementos de las dos secuencias divididas de acuerdo con este método. Todo el proceso de implementación de clasificación se puede llamar de forma recursiva. y finalmente los requeridos Los elementos de la secuencia desordenada ordenada se convierten en una secuencia ordenada.

Clasificación por combinación

El algoritmo de ordenación por combinación divide recursivamente la secuencia en secuencias cortas, utilizando una secuencia directa con solo 1 elemento o una secuencia con solo 2 elementos como secuencia corta. y luego ordene todas las secuencias cortas ordenadas en secuencias largas de acuerdo con ciertas reglas. La clasificación por combinación incorpora la estrategia de divide y vencerás, es decir, cada registro en la secuencia inicial que contiene n registros se considera como una subsecuencia de longitud 1, y luego estas n subsecuencias se fusionan en pares para obtener n/2 longitudes de 2 ( cuando Siempre que sea un número impar, aparecerá una subsecuencia ordenada de longitud l; repita los pasos anteriores hasta obtener una secuencia larga ordenada de longitud n); Cabe señalar que al comparar e intercambiar elementos, si los dos elementos son iguales en tamaño, no es necesario intercambiar posiciones deliberadamente, por lo que este algoritmo no destruirá la estabilidad de la secuencia, es decir, la clasificación por fusión también es estable. Algoritmo de clasificación.