¿Cuáles son los algoritmos de clasificación de datos más utilizados y cuáles son sus características? Por ejemplo, combine un algoritmo de clasificación y utilice una matriz para ordenar los datos.

Introducción a la clasificación

La clasificación es una operación importante que se utiliza a menudo en el procesamiento de datos en las computadoras y sus sistemas de aplicaciones, el tiempo dedicado a la clasificación ocupa una gran parte del tiempo de ejecución del sistema. Una gran proporción; y la clasificación en sí también juega un papel importante en la promoción del desarrollo del análisis de algoritmos. Hay cientos de métodos de clasificación, pero no existe un método ideal y satisfactorio. Este capítulo presenta los siguientes métodos de clasificación de uso común, los analiza y compara.

1. Clasificación por inserción (clasificación por inserción directa, clasificación por inserción media, clasificación Hill)

2. Clasificación por intercambio (clasificación por burbuja, clasificación rápida); 3. Clasificación por selección (clasificación por selección directa, clasificación en montón);

4. Clasificación por combinación;

5. Clasificación por base;

Puntos de aprendizaje

1. Dominar los conceptos básicos de clasificación y las características de varios métodos de clasificación, y ser capaz de aplicarlos de manera flexible;

2. Dominar la clasificación por inserción (clasificación por inserción directa, clasificación por media inserción, Clasificación Hill), clasificación por intercambio (clasificación por burbujas, clasificación rápida), clasificación por selección (clasificación por selección directa, clasificación por montón), métodos de clasificación por fusión bidireccional y sus métodos de análisis de rendimiento;

3. método de clasificación y su método de análisis de rendimiento.

Ordenación o clasificación

La llamada clasificación consiste en organizar los registros en el archivo de modo que estén ordenados en orden creciente (o decreciente) de palabras clave. Su definición exacta es la siguiente:

Entrada: n registros R1, R2,..., Rn, y sus correspondientes palabras clave son K1, K2,..., Kn.

Salida: Ril, Ri2,…,Rin, tal que Ki1≤Ki2≤…≤Kin. (o Ki1≥Ki2≥…≥Kin).

1． El archivo-objeto ordenado

El archivo-objeto ordenado consta de un conjunto de registros.

Un registro consta de varios elementos de datos (o campos). Uno de estos elementos se puede utilizar para identificar un registro, denominado elemento clave. El valor de este elemento de datos se llama clave.

Nota:

Cuando no sea probable que cause confusión, los elementos de palabras clave se denominarán palabras clave para abreviar.

2． La base para las operaciones de clasificación: palabras clave

Las palabras clave utilizadas como base para las operaciones de clasificación pueden ser de tipo numérico o de caracteres.

La selección de palabras clave debe basarse en los requisitos de la pregunta.

Por ejemplo, en las estadísticas de puntuación del examen de ingreso a la universidad, cada candidato se considera un récord. Cada registro contiene número de boleto de admisión, nombre, puntajes de cada materia y puntaje total, etc. Para identificar de forma única el registro de un candidato, debe utilizar "número de boleto de admisión" como palabra clave. Si desea clasificar a los candidatos según su puntuación total, debe utilizar "puntuación total" como palabra clave.

Estabilidad de la clasificación

Cuando las palabras clave de los registros a ordenar son diferentes, el resultado de la clasificación es único; de lo contrario, el resultado de la clasificación no es único.

En el archivo que se va a ordenar, si hay varios registros con las mismas palabras clave, el orden relativo entre estos registros con las mismas palabras clave permanecerá sin cambios después de la clasificación y el método de clasificación es estable. El orden entre registros con la misma palabra clave cambia, se dice que este método de clasificación es inestable.

Nota:

La estabilidad del algoritmo de clasificación es para todas las instancias de entrada. Es decir, entre todas las instancias de entrada posibles, siempre que haya una instancia que haga que el algoritmo no cumpla con los requisitos de estabilidad, el algoritmo de clasificación es inestable.

Clasificación de los métodos de clasificación

1. Dividido según si está involucrado el intercambio de datos de la memoria interna y externa

Durante el proceso de clasificación, si todo el archivo se procesa en la memoria y el intercambio de datos de la memoria interna y externa no está involucrado durante la clasificación, se llama clasificación interna (denominada clasificación interna; por el contrario, si se requiere el intercambio de datos entre la memoria interna y externa durante el proceso de clasificación, se llama clasificación externa);

Nota:

① La clasificación interna es adecuada para archivos pequeños con una pequeña cantidad de registros

② La clasificación externa es adecuada para archivos con demasiados registros que no pueden grabarse de una vez Coloque todos los registros en un archivo grande en la memoria.

2． Los métodos de clasificación interna se pueden dividir en cinco categorías según la estrategia: clasificación por inserción, clasificación por selección, clasificación por intercambio, clasificación por fusión y clasificación por distribución.

Análisis del algoritmo de clasificación

1. Operaciones básicas de los algoritmos de clasificación

La mayoría de los algoritmos de clasificación tienen dos operaciones básicas:

(1) comparar los tamaños de dos palabras clave;

( 2) cambiar el puntero al registro o mover el registro mismo.

Nota:

La implementación de la (2) operación básica depende del método de almacenamiento de los registros a ordenar.

2． Métodos de almacenamiento comunes para ordenar archivos

(1) Utilice tablas de secuencia (o vectores directamente) como estructura de almacenamiento

Proceso de clasificación: reorganice físicamente los registros mismos (es decir, a través de clave Juicio comparativo entre palabras, mueva el registro a la ubicación adecuada)

(2) Utilice la lista vinculada como estructura de almacenamiento

Proceso de clasificación: no es necesario mover el registro, solo es necesario modificar el puntero. Este tipo de clasificación generalmente se denomina clasificación de lista vinculada (o encadenada);

(3) Almacene los registros que se ordenarán de manera secuencial, pero al mismo tiempo cree una tabla auxiliar (como incluir palabras clave y apuntando a la ubicación del registro) Tabla de índice compuesta por punteros)

Proceso de clasificación: solo es necesario reorganizar físicamente las entradas de la tabla auxiliar (es decir, solo se mueven las entradas de la tabla auxiliar, pero los registros en sí no se mueven). Es adecuado para métodos de clasificación que son difíciles de implementar en listas vinculadas y aún necesitan evitar mover registros durante el proceso de clasificación.

3． Evaluación del rendimiento de los algoritmos de clasificación

(1) Criterios para evaluar la calidad de los algoritmos de clasificación

Existen dos criterios principales para evaluar la calidad de los algoritmos de clasificación:

① Tiempo de ejecución y espacio auxiliar requerido

② La complejidad del algoritmo en sí

(2) La complejidad espacial del algoritmo de clasificación

Si el espacio auxiliar requerido por el algoritmo de clasificación No depende del tamaño del problema n, es decir, el espacio auxiliar es O (1), lo que se denomina clasificación in situ (In-PlaceSou).

El espacio auxiliar generalmente requerido para la clasificación no local es O (n).

(3) Costo de tiempo del algoritmo de clasificación

El costo de tiempo de la mayoría de los algoritmos de clasificación es principalmente la comparación entre palabras clave y el movimiento de registros. El tiempo de ejecución de algunos algoritmos de clasificación depende no sólo del tamaño del problema, sino también del estado de los datos en la instancia de entrada.

Representación secuencial de la estructura de almacenamiento de archivos

#define n l00 // Longitud supuesta del archivo, es decir, el número de registros que se ordenarán

typedef int KeyType ; // Tipo de clave asumido

typedef struct{ //Tipo de registro

KeyType key; // Elemento de palabra clave

InfoType otherinfo; El tipo InfoType se define según la aplicación específica

}RecType;

typedef RecType SeqList[n+1] //SeqList es un tipo de tabla de secuencia y la unidad 0 en la tabla se usa generalmente para actuar como centinela

Nota:

Si el tipo de palabra clave no tiene un operador de comparación, puede definir una macro o función de antemano para expresar la operación de comparación. .

Cuando la palabra clave de ejemplo es una cadena, puede definir la macro "#define LT(a, b)(Stromp((a), (b))<0)". Entonces "a

La clasificación se divide en cuatro categorías según el tiempo promedio:

(1) Clasificación por orden cuadrado (O(n2))

Generalmente llamada clasificación simple , por ejemplo Inserción directa, selección directa y ordenación por burbujas;

(2) Ordenación por orden logarítmico lineal (O(nlgn))

Como ordenación rápida, por montón y por combinación;

(3) La clasificación por orden O (n1+￡)

￡ es una constante entre 0 y 1, es decir, 0<￡<1, como la clasificación Hill;

(4) Clasificación por orden lineal (O(n))

Como clasificación por cubo, contenedor y base.

Comparación de varios métodos de clasificación

En la clasificación simple, la inserción directa es la mejor y la clasificación rápida es la más rápida. Cuando el archivo está en orden positivo, la inserción directa y la propagación son ambas. el mejor.

Factores que afectan el efecto de clasificación

Debido a que los diferentes métodos de clasificación se adaptan a diferentes entornos y requisitos de aplicación, se deben tener en cuenta los siguientes factores al elegir un método de clasificación adecuado:

①El número de registros a ordenar n;

②El tamaño (escala) del registro;

③La estructura de la palabra clave y su estado inicial;

④Requisitos de estabilidad del par;

⑤ Condiciones de la herramienta de lenguaje;

⑥ Estructura de almacenamiento

⑦ Complejidad de tiempo y espacio auxiliar, etc.

Selección de métodos de clasificación en diferentes condiciones

(1) Si n es pequeño (como n≤50), se puede utilizar la inserción directa o la clasificación por selección directa.

Cuando el tamaño del registro es pequeño, la clasificación por inserción directa es mejor; de lo contrario, debido a que la cantidad de registros movidos por selección directa es menor que la de la inserción directa, la clasificación por selección directa es mejor.

(2) Si el estado inicial del archivo es básicamente en orden (refiriéndose al orden positivo), se debe utilizar inserción directa, burbuja o clasificación rápida aleatoria.

(3) Si n es grande, se debe utilizar un método de clasificación con una complejidad temporal de O (nlgn): clasificación rápida, clasificación en montón o clasificación por combinación.

La clasificación rápida se considera actualmente el mejor método entre la clasificación interna basada en la comparación. Cuando las palabras clave a ordenar se distribuyen aleatoriamente, el tiempo promedio de clasificación rápida es el más corto;

Montón. La clasificación requiere menos espacio auxiliar que la clasificación rápida y no sufre los peores escenarios que pueda tener la clasificación rápida. Ambas clasificaciones son inestables.

Si se requiere que la clasificación sea estable, se puede utilizar la clasificación por combinación. Sin embargo, no vale la pena recomendar el algoritmo de clasificación de fusión por pares a partir de un solo registro presentado en este capítulo. Por lo general, se puede utilizar en combinación con la clasificación por inserción directa. Primero utilice la ordenación por inserción directa para obtener subarchivos ordenados más largos y luego combínelos en pares. Debido a que la ordenación por inserción directa es estable, la ordenación por combinación mejorada sigue siendo estable.

4) En el método de clasificación basado en comparación, después de cada comparación de los tamaños de dos palabras clave, solo ocurren dos transiciones posibles, por lo que se puede usar un árbol binario para describir el proceso de decisión de comparación.

Cuando n palabras clave de un archivo se distribuyen aleatoriamente, cualquier algoritmo de clasificación que se base en la "comparación" requiere al menos O(nlgn) tiempo.

La clasificación de cajas y la clasificación por base solo requieren un paso para provocar m posibles transferencias, es decir, cargar un registro en una de las m cajas. Por lo tanto, en general, la clasificación por cajas y la clasificación por base pueden ocurrir en O Clasificación completa. de n registros dentro de (n) tiempo. Sin embargo, la clasificación por cuadros y la clasificación por base solo se aplican a palabras clave con características estructurales obvias, como cadenas y números enteros. Cuando el rango de valores de la palabra clave pertenece a un conjunto infinito (como palabras clave de números reales), no se puede utilizar la clasificación por cuadros. clasificación por base, en este momento la única forma de ordenar es mediante la ayuda de "comparación".

Si n es muy grande y el número de palabras clave registradas es pequeño y se puede descomponer, es mejor utilizar la clasificación por base. Aunque la clasificación por depósitos no tiene requisitos sobre la estructura de las palabras clave, solo puede hacer que el tiempo promedio alcance un orden lineal cuando las palabras clave se distribuyen aleatoriamente; de ​​lo contrario, será un orden cuadrado. Al mismo tiempo, cabe señalar que las tres clasificaciones de asignación de cuadro, depósito y base suponen que si la palabra clave es un número, su valor no es negativo, de lo contrario, al asignarla a un número de cuadro (depósito). , se agregará el tiempo correspondiente.

(5) Algunos lenguajes (como Fortran, Cobol o Basic, etc.) no proporcionan punteros ni recursividad, lo que hace que la implementación de fusión sea rápida (utilizan la recursividad para implementarla de forma más sencilla) y La clasificación por base (se utilizan punteros) se vuelve compleja. En este momento, se puede considerar otra clasificación.

(6) En el algoritmo de clasificación proporcionado en este capítulo, todos los datos de entrada se almacenan en un vector. Cuando el tamaño de los registros es grande, para evitar perder mucho tiempo moviéndolos, se puede utilizar una lista vinculada como estructura de almacenamiento. Por ejemplo, la ordenación por inserción, la ordenación por combinación y la ordenación por base son fáciles de implementar en listas vinculadas, lo que reduce la cantidad de movimientos de registros. Sin embargo, algunos métodos de clasificación, como la clasificación rápida y la clasificación en montón, son difíciles de implementar en listas vinculadas. En este caso, puede extraer palabras clave para crear una tabla de índice y luego ordenar la tabla de índice. Sin embargo, un método más simple es: introducir un vector entero t como tabla auxiliar y establecer t [i] = i (0≤i

R[t[0]]. key ≤R[t[1]].key≤…≤R[t[n-1]].key

Si es necesario, el resultado final es:

R[0 ].key ≤R[1].key≤…≤R[n-1].key

Una vez completada la clasificación, los registros se pueden reorganizar en el orden especificado por la tabla auxiliar para completar esto. reordenamiento El tiempo es O(n).