Puntos de conocimientos básicos públicos del examen de nivel 2 de computadora de 2018: tecnología de clasificación

Método de clasificación de intercambio de puntos de prueba 11

Enlace del examen:

El punto de prueba 11 es más difícil El contenido suele evaluarse en forma de preguntas de opción múltiple. La probabilidad de evaluación es 30 y la puntuación es de aproximadamente 2 puntos. Los lectores deberían estar familiarizados con los procesos básicos de varios algoritmos de clasificación.

La clasificación por burbujas y la clasificación rápida son métodos de clasificación por intercambio.

(1) Método de clasificación por burbujas

Primero, escanee la tabla lineal hacia atrás desde la cabecera de la tabla y compare los tamaños de dos elementos adyacentes uno por uno. Si el elemento anterior es mayor que el siguiente, se realiza un intercambio, el mayor de los dos elementos adyacentes continúa retrocediendo y finalmente el más grande llega al final de la lista lineal.

Luego escanea la lista lineal restante de atrás hacia adelante y compara los tamaños de dos elementos adyacentes uno por uno. Si el último elemento es más pequeño que el elemento anterior, se intercambian, y el más pequeño de los dos elementos adyacentes continúa avanzando y, finalmente, el más pequeño pasa al frente de la lista lineal.

Repita el proceso anterior para las tablas lineales restantes hasta que las tablas lineales restantes estén vacías y se haya ordenado el orden.

En el peor de los casos, la clasificación de burbujas requiere n(n-1)/2 comparaciones.

(2) Método de clasificación rápida

La idea básica es: tomar cualquier elemento de la secuencia que se va a ordenar como punto de referencia (normalmente el primer elemento) y ordenar los elementos que se van a ordenar. ordenados mediante una clasificación Los elementos se dividen en dos subsecuencias. El código de clasificación del elemento de la subsecuencia izquierda es menor o igual que el código de clasificación del elemento de referencia, y la subsecuencia derecha es mayor que el código de clasificación del elemento de referencia. Continúe ordenando las dos subsecuencias respectivamente hasta que se ordene toda la secuencia.