Algoritmos comunes de búsqueda y clasificación
Ventajas: Es adecuado tanto para tablas secuenciales como para listas enlazadas individualmente. No requiere el orden de los elementos en la tabla, lo que facilita la inserción. Solo necesita insertar el final de la tabla. .
Desventajas: Lento.
Mejora: establezca un centinela al final de la tabla, por lo que no es necesario realizar un bucle para determinar si el subíndice de la matriz está fuera de los límites, ya que eventualmente se establecerá.
Condiciones aplicables:
El árbol de decisión del método de búsqueda binaria no es solo un árbol de clasificación binario, sino también un árbol equilibrado ideal. La complejidad del tiempo es O (lbn).
Implementación de bucle
Implementación recursiva
Los elementos a ordenar deben implementar la interfaz Comparable de Java. Esta interfaz tiene un método compareTo(), que se puede utilizar. para juzgar dos La relación de tamaño entre elementos.
Seleccione el elemento más pequeño de la matriz e intercámbielo con el primer elemento de la matriz. Luego, se selecciona el elemento más pequeño de los elementos restantes de la matriz y se intercambia con el segundo elemento de la matriz. Continúe haciendo esto hasta que se ordene toda la matriz.
La ordenación por selección requiere ~N2/2 comparaciones y ~N intercambios, y su tiempo de ejecución es independiente de la entrada ==, lo que hace que requiera muchas operaciones de comparación e intercambio en la matriz ordenada.
Intercambie continuamente elementos adyacentes en orden inverso de izquierda a derecha. Después de un ciclo, el elemento desordenado más grande puede flotar hacia la derecha.
En un bucle, si no hay intercambio, entonces la matriz ya está en orden y puede salir directamente en este momento.
Inserte el elemento actual en la matriz ordenada de la izquierda cada vez, de modo que la matriz de la izquierda siga ordenada después de la inserción.
Para el array {3, 5, 2, 4, 1}, su orden se invierte: (3, 2), (3, 1), (5, 2), (5, 4) , (5,1), (2,668+0).
= =La complejidad temporal de la ordenación por inserción depende del orden inicial de la matriz. Si la matriz ya está parcialmente ordenada, hay menos órdenes inversas, menos intercambios y menor complejidad temporal = =.
Para matrices grandes, la ordenación por inserción es muy lenta porque solo puede intercambiar elementos adyacentes y solo puede reducir el número de inversiones en 1 a la vez. La clasificación Hill parece resolver esta limitación de la clasificación por inserción. Al intercambiar elementos no adyacentes, se reduce el número de órdenes inversas en más de 1 a la vez.
La clasificación Hill utiliza la clasificación por inserción para ordenar secuencias con un intervalo de H. Al disminuir continuamente H hasta h = 1, se puede ordenar toda la matriz.
El tiempo de ejecución de la clasificación Hill no puede alcanzar el nivel cuadrado. El número de comparaciones necesarias para la clasificación Hill de la secuencia creciente 1, 4, 13, 40,... no excederá n veces la longitud de la secuencia creciente. secuencia varias veces. El algoritmo de clasificación avanzado introducido más tarde es sólo dos veces más rápido que la clasificación Bisir.
La idea de la ordenación por fusión es dividir la matriz en dos partes, ordenarlas por separado y luego fusionarlas.
El método merge fusiona dos partes ordenadas de una matriz en una.
Divida una matriz grande en dos matrices pequeñas para resolver.
Dado que el problema se divide en dos mitades de subproblemas cada vez, la complejidad de este algoritmo es generalmente O (NlogN).
Primero fusione estos microarrays y luego combínelos en pares para obtener microarrays.
Tome a[l] como elemento segmentado, luego escanee desde el extremo izquierdo de la matriz hacia la derecha hasta encontrar el primer elemento que sea mayor o igual a él, luego escanee desde el extremo derecho de la matriz a la izquierda para encontrar el elemento que es menor que el primer elemento e intercambiar los dos elementos. Si continuamos con este proceso, podemos asegurarnos de que el elemento izquierdo del puntero izquierdo I no sea más grande que el elemento dividido y que el elemento derecho del puntero derecho J no sea más pequeño que el elemento dividido. Cuando los dos punteros se encuentran, los elementos divididos a[l] y a[j] se intercambiarán.
La clasificación rápida es una clasificación in situ y no requiere una matriz auxiliar, pero las llamadas recursivas requieren una pila auxiliar.
El mejor escenario para la ordenación rápida es dividir la matriz exactamente por la mitad cada vez, de modo que se minimice el número de llamadas recursivas. En este caso, el número de comparaciones es CN = 2CN/2+N y la complejidad es O (NlogN).
En el peor de los casos, la primera vez comienza con el elemento más pequeño, la segunda vez comienza con el segundo elemento más pequeño, y así sucesivamente.
Por tanto, es necesario comparar N2/2 en el peor de los casos. Para evitar que la matriz se ordene desde el principio, la matriz debe mezclarse aleatoriamente durante la clasificación rápida.
Debido a que la ordenación rápida también se llamará a sí misma recursivamente en matrices pequeñas, la ordenación por inserción tiene mejor rendimiento que la ordenación rápida para matrices pequeñas, por lo que puede cambiar a la ordenación por inserción en matrices pequeñas.
En el mejor de los casos, la mediana de la matriz se puede utilizar como elemento divisorio cada vez, pero el costo de calcular la mediana es muy alto. Un compromiso es tomar tres elementos y utilizar el elemento de tamaño mediano como elemento segmentado.
Para matrices con una gran cantidad de elementos repetidos, la matriz se puede dividir en tres partes, correspondientes a los elementos segmentados menor, igual y mayor que.
La clasificación rápida con división de tres vías puede ordenar matrices aleatorias con una gran cantidad de elementos repetidos en tiempo lineal.
El método de clasificación rápida partición() devolverá un número entero J..j-1] menor o igual que a[j], y a[j+1..h] mayor o igual a a[j] , en este caso, a[j] es el jésimo elemento más grande de la matriz.
Puedes usar esta función para encontrar el késimo elemento más grande en una matriz.
El algoritmo es lineal. Suponiendo que la matriz se puede dividir en dos partes a la vez, el número total de comparaciones es (N+N/2+N/4+)...) hasta que se encuentra el k-ésimo elemento, y la suma es significativamente menor que 2N .
El valor de un nodo en el montón es siempre mayor o igual que el valor de su nodo hijo. El montón es un árbol binario completo.
Un montón se puede representar mediante una matriz porque un montón es un árbol binario completo, y un árbol binario completo se puede almacenar fácilmente en una matriz. La posición del nodo padre del nodo en la posición K es k/2, y las posiciones de sus dos nodos secundarios son 2k y 2k+1 respectivamente. Para describir más claramente la relación posicional de los nodos, aquí no se utiliza la posición con índice de matriz 0.
En el montón, cuando un nodo es más grande que su nodo padre, es necesario intercambiar los dos nodos. Después del intercambio, puede ser más grande que su nuevo padre, lo que requiere operaciones constantes de comparación e intercambio, lo que se denomina flotante.
De manera similar, cuando un nodo es más pequeño que un nodo secundario, también debe compararse e intercambiarse continuamente hacia abajo, lo que se denomina hundimiento. Si un nodo tiene dos hijos, debe intercambiarse con el mayor de los dos hijos.
Coloque el nuevo elemento al final de la matriz y colóquelo en su lugar.
Elimina el elemento más grande de la parte superior de la matriz, coloca el último elemento de la matriz encima y deja que el elemento se hunda en su lugar.
Si intercambia el elemento más grande con el último elemento de la matriz en el montón actual sin eliminarlo, puede obtener una secuencia con cabeza y cola decrecientes, que es una secuencia creciente hacia adelante. Esta es la clasificación del montón. .
La altura del montón es logN, por lo que la complejidad de insertar elementos en el montón y eliminar el elemento más grande es logN.
Para la clasificación en montón, la complejidad es NlogN porque es necesario hundir N nodos.
La clasificación en montón es una clasificación in situ que no utiliza espacio adicional.
La clasificación en montón rara vez se utiliza en los sistemas operativos modernos porque no puede almacenar en caché utilizando el principio de localidad, es decir, los elementos de la matriz rara vez se comparan e intercambian con elementos adyacentes.
El núcleo de la clasificación por conteo es convertir los valores de los datos de entrada en claves y almacenarlos en un espacio de matriz adicional. Como ordenación de complejidad de tiempo lineal, == ordenación por conteo requiere que los datos de entrada sean un número entero dentro de un cierto rango ==.
Cuando los elementos de entrada son n enteros entre 0 y k, su == tiempo de ejecución es O(n+k)==. La clasificación por conteo no es una clasificación por comparación y la velocidad de clasificación es más rápida que cualquier algoritmo de clasificación por comparación. Dado que la longitud de la matriz C utilizada para contar depende del rango de los datos en la matriz a ordenar (igual a la diferencia entre los valores máximo y mínimo de la matriz a ordenar más 1), para matrices con mayor rangos de datos, contar y ordenar requiere mucho tiempo y memoria. Es más adecuado para ordenar == matrices de matrices de enteros no negativos de tamaño pequeño ==.
La clasificación por cubos es una versión mejorada de la clasificación por conteo. Utiliza la relación de mapeo de funciones, y la clave para la eficiencia radica en la determinación de esta función de mapeo. Para mejorar la eficiencia de la clasificación de depósitos, debemos hacer dos cosas:
Al mismo tiempo, para la clasificación de elementos en el depósito, es muy importante elegir qué algoritmo de clasificación de comparación tiene un impacto en el rendimiento.
La velocidad es más rápida cuando los datos de entrada se distribuyen uniformemente en cada depósito, y la más lenta cuando todos los datos de entrada se distribuyen en el mismo depósito.
Complejidad real N*K
La clasificación rápida es el algoritmo de clasificación de propósito general más rápido. Tiene pocas instrucciones en el bucle interno y también puede usar caché porque siempre hay datos. accedido secuencialmente. Su tiempo de ejecución es de aproximadamente ~cNlogN, donde c es más pequeño que otros algoritmos de clasificación logarítmica lineal.
Al utilizar la clasificación rápida dividida en tres vías, algunas entradas distribuidas que pueden aparecer en aplicaciones prácticas pueden alcanzar un nivel lineal, mientras que otros algoritmos de clasificación aún requieren un tiempo logarítmico lineal.