Ocho algoritmos de clasificación que debes conocer para entrevistas (Python)
Introducción
La operación básica de la ordenación por inserción es insertar un dato en datos ordenados, obteniendo así nuevos datos ordenados con un número más uno.
Este algoritmo es adecuado para ordenar una pequeña cantidad de datos y la complejidad temporal es O (n 2).
El algoritmo de interpolación es un método de clasificación estable.
Pasos
(1) A partir del primer elemento, se puede considerar que el elemento ha sido ordenado.
② Saque el siguiente elemento y escanee de atrás hacia adelante de acuerdo con el orden de los elementos ordenados.
③Si el elemento (ordenado) es más grande que el nuevo elemento, mueva el elemento a la siguiente posición.
④ Repita el paso 3 hasta encontrar la posición donde el elemento ordenado es menor o igual que el nuevo elemento.
⑤Inserte el nuevo componente en esta ubicación.
6. Repetir el paso 2.
Demostración de clasificación
Implementación del algoritmo
Segundo, clasificación de burbujas
Introducción
La clasificación de burbujas es una clasificación simple algoritmo con complejidad temporal O (n 2).
Itera sobre la serie a ordenar, comparando dos elementos a la vez e intercambiándolos si están en el orden incorrecto. El acceso a la serie se repite hasta que no es necesario ningún intercambio, es decir, la serie queda ordenada.
El nombre de este algoritmo proviene del hecho de que los elementos más pequeños "flotarán" lentamente hasta la parte superior de la secuencia mediante el intercambio.
Principio
Recorre la lista y encuentra el elemento con más iteraciones en cada bucle.
Bucles anidados necesarios: el bucle externo controla el número total de bucles y el bucle interno es responsable de cada ronda de comparación de bucles.
Pasos
① Comparar elementos adyacentes. Si el primero es más grande que el segundo, cámbialos.
② Haz el mismo trabajo para cada par de elementos adyacentes, desde el primer par al principio hasta el último par al final. En este punto, el último elemento debería ser el número más grande.
③ Repita los pasos anteriores para todos los elementos excepto el último elemento.
(4) Continúe repitiendo los pasos anteriores para cada vez menos elementos cada vez hasta que no haya ningún par de números para comparar.
Implementación del algoritmo:
Tercero, clasificación rápida
Introducción
La clasificación rápida es una mejora de la clasificación de burbujas, basándose en divide y vencerás La idea de propuesta por C. A. R. Hoare en 1962.
Idea básica
La idea básica de clasificación rápida es: cavar agujeros y llenar números + método divide y vencerás.
Primero seleccione un valor de eje (pivote, también llamado punto de referencia) y divida los registros que se van a ordenar en dos partes independientes mediante una sola pasada de clasificación. Las palabras clave de una parte del registro son más pequeñas que las palabras clave. de la otra parte. Entonces esto Las dos partes de los registros se pueden ordenar por separado para lograr una clasificación de secuencia completa.
Pasos de implementación
① Seleccione un elemento de la secuencia, llamado "pivote"
(2) Reordene la secuencia para que sea menor que el valor de referencia Todo; los elementos de se colocan delante del punto de referencia y todos los elementos mayores que el valor del punto de referencia se colocan después del punto de referencia (el mismo número puede estar en ambos lados
③ Repita el segundo paso para los dos decimales); series hasta que cada intervalo Solo hay un número.
Demostración de clasificación
Implementación del algoritmo
Cuarto, clasificación Hill
Introducción
La clasificación de shell es inserción Un tipo de clasificación, y también una clasificación incremental reducida. Es una versión más eficiente y mejorada del algoritmo de clasificación por inserción directa. La clasificación Hill es un algoritmo de clasificación inestable con una complejidad temporal de O (1,3n).
La clasificación por colina es un método mejorado basado en las siguientes dos propiedades de la clasificación por inserción:
La clasificación por inserción es eficiente cuando se opera con datos que casi se han ordenado, es decir, la eficiencia de se puede lograr la clasificación lineal;
Pero la clasificación por inserción suele ser muy ineficiente porque la clasificación por inserción solo puede mover un bit de datos a la vez.
Idea básica
(1) La clasificación Hill es agrupar registros por un número determinado y utilizar un algoritmo de inserción directa para ordenar cada grupo
②A medida que aumenta el número; A medida que disminuye el volumen, cada grupo de paquetes contiene cada vez más palabras clave.
Cuando el incremento se reduce a 1, el archivo completo se divide en un grupo y el algoritmo finaliza.
Demostración de clasificación
Implementación del algoritmo
5. Ordenación por selección
Introducción
La ordenación por selección es sencilla e intuitiva. Algoritmo de clasificación con complejidad temporal ο (N2).
Idea básica
La idea básica de la clasificación selectiva: comparación + intercambio.
En el primer paso, seleccione el registro más pequeño de los registros a ordenar r1 ~ r[n] e intercámbielo con r1
En el segundo paso, seleccione el registro más pequeño; de los registros r2 ~ r[n] para ordenar e intercambiar con r2;
Por analogía, en el paso I, seleccione el registro más pequeño de los registros que se ordenarán e intercambiará con r[i], por lo que que La secuencia ordenada continúa creciendo hasta que se completa toda la clasificación.
Demostración de clasificación
Seleccione una animación de muestra para ordenar. El rojo representa el valor mínimo actual, el amarillo representa la secuencia ordenada y el azul representa la posición actual.
Implementación del algoritmo
6. Clasificación del montón
Introducción
Heapsort se refiere a una estructura de datos diseñada utilizando el árbol del montón (montón). Un algoritmo de clasificación es una clasificación selectiva.
Utilice las características de las matrices para especificar rápidamente elementos de índice.
Idea básica
El montón se divide en un montón raíz grande y un montón raíz pequeño, que es un árbol binario completo.
El requisito para un montón raíz grande es que el valor de cada nodo no sea mayor que el valor de su nodo padre, es decir, a[parent[I]]>;=A[i].
En una matriz ordenada en orden descendente, se requiere un montón raíz porque, de acuerdo con los requisitos del montón raíz, el valor máximo debe estar en la parte superior del montón.
Demostración de clasificación
Implementación del algoritmo
7. Ordenación por combinación
Introducción
La ordenación por combinación es un método basado en Un algoritmo de clasificación eficiente para operaciones de fusión. Este algoritmo es una aplicación muy típica de divide y vencerás.
Idea básica
El algoritmo de clasificación por fusión consiste en fusionar dos (o más) listas ordenadas en una nueva lista ordenada, es decir, dividir la secuencia que se va a ordenar en varias subsecuencias. Cada subsecuencia está ordenada. Luego, las subsecuencias ordenadas se fusionan en una secuencia ordenada completa.
Idea algorítmica
Método recursivo de arriba hacia abajo (si la secuencia * * * tiene n elementos)
(1) Reemplazar cada dos elementos de la secuencia Fusionar números adyacentes para formar secuencias de piso (n/2). Después de ordenar, cada secuencia contiene dos elementos;
(2) Fusione las secuencias anteriores nuevamente para formar secuencias de piso (n/4). elementos. Una secuencia contiene cuatro elementos;
③ Repita el paso ② hasta que todos los elementos estén ordenados.
Método de iteración de abajo hacia arriba
(1) Solicite un espacio cuyo tamaño sea la suma de las dos secuencias ordenadas. Este espacio se utiliza para almacenar la secuencia fusionada;
p>
(2) Establezca dos punteros, cuyas posiciones iniciales son las posiciones iniciales de las dos secuencias de clasificación
③Compare los elementos señalados por los dos punteros y seleccione uno relativamente más pequeño; elemento Colóquelo en el espacio de combinación y mueva el puntero a la siguiente posición
④Repita el paso ③ hasta que el puntero llegue al final de la secuencia
⑤Copie todos los elementos restantes de otra secuencia; directamente para fusionar el final de la secuencia.
Demostración de clasificación
Implementación del algoritmo
8. Radix Sort
Introducción
Radix Sort es una "distribución ordenar" ”, también conocido como “método del depósito”.
La clasificación por base es una clasificación estable con una complejidad temporal de O (nlog(r)m), donde R es la base y M es el número de montones.
En algunos casos, la clasificación por base es más eficiente que otros métodos de clasificación estable.
Idea básica
Todos los valores (enteros positivos) a comparar se unifican a la misma longitud de dígitos, y los números con dígitos más cortos están precedidos por ceros. Luego, comenzando desde el bit más bajo, ordene una vez. De esta forma, desde el orden más bajo hasta el orden más alto, la secuencia se convierte en una secuencia ordenada.
Hay dos implementaciones de clasificación por base, clasificando de mayor a menor según la prioridad:
clasificación MSD (dígito más significativo) comenzando desde el dígito superior más a la izquierda. Primero, los códigos clave k1 se registran en el mismo grupo y los códigos clave k1 son iguales.
Luego, estos grupos se clasifican en subgrupos según k2. Después de eso, continúe ordenando y agrupando los códigos clave posteriores hasta que los subgrupos estén ordenados según el código clave más bajo kd. Luego, conecta los grupos para obtener una secuencia ordenada. El modo MSD es adecuado para secuencias de varios dígitos.
LSD (dígito menos significativo) se ordena comenzando desde el dígito inferior más a la derecha. Primero ordene desde kd, luego ordene desde kd-1 y repita hasta que se ordene k1 para obtener una secuencia ordenada. El modo LSD es adecuado para secuencias con muy pocos dígitos.
Efecto de clasificación
Implementación del algoritmo
9. Resumen
Una revisión de varios tipos de estabilidad, complejidad temporal y complejidad espacial;
Clasificación de orden cuadrado O (n?): varias clasificaciones simples: inserción directa, selección directa, riesgo- tomando clasificación de burbujas;
En términos de complejidad temporal:
Clasificación de orden logarítmico lineal O (nlog?n): clasificación rápida, clasificación de montón, clasificación de fusión;
Clasificación O (N1+0)), que es una constante entre 0 y 1: clasificación Hill;
Clasificación lineal Clasificación O(n): clasificación por base, además de clasificación por cubos y contenedores.