Python implementa un algoritmo de búsqueda binaria y clasificación por fusión

Python implementa algoritmos de búsqueda binaria y clasificación por fusión.

Hoy todavía estoy aprendiendo algoritmos. Estuve trabajando en un proyecto de bbs hace unos días. La interfaz también es fea y el comentario. La función parece tener errores. No lo hago ahora. Tengo que aprender algoritmos y estructuras de datos. Si no puedo aprobar el examen escrito, ni siquiera tengo la oportunidad de ser entrevistado...

Hoy. Aprendí el algoritmo de búsqueda binaria. La búsqueda binaria es bastante simple, pero no sé cómo fusionar y ordenar. No pude entender la clasificación de combinación escrita en lenguaje C. Más tarde, consulté. blogs de otras personas y finalmente lo entendí.

Búsqueda a la mitad

Veamos primero la explicación del libro de texto sobre la búsqueda a la mitad. Tenga en cuenta que la búsqueda binaria es para secuencias ordenadas. Cada vez que se dobla por la mitad, el intervalo de búsqueda se reduce aproximadamente a la mitad. bajo y alto son respectivamente el primer subíndice y el último subíndice del intervalo de búsqueda. Cuando aparece bajo>alto, significa que la palabra clave de destino no existe en toda la secuencia ordenada y la búsqueda falla.

Mira mi implementación usando programación Python:

defBinSearch(array, key, low, high): mid=int((low+high)/2) ifkey==array ret = BinSearch(array,76,0,len(array)-1)# Encuentra 65 hasta la mitad de la búsqueda print(ret)

Salida: Encuentra 76 en la lista.

76

Complejidad del tiempo: O(logn)

Algoritmo de clasificación por fusión

Primero explique la idea de clasificación:

Primero, la clasificación por fusión utiliza la ley binaria , en última instancia, la idea es dividir y conquistar. La clasificación por combinación se refiere al proceso de descomponer una secuencia desordenada para clasificarla en varias subsecuencias ordenadas y fusionar las subsecuencias ordenadas en una secuencia ordenada general. Se ordena una secuencia de longitud 1. Por lo tanto, cuando la longitud de la subsecuencia obtenida por descomposición es mayor que 1, la descomposición debe continuar hasta que la longitud sea 1.

(La siguiente figura es el proceso de descomposición, la figura es de la programación de Python para implementar fusionar clasificación)

El proceso de fusión es el siguiente:

Muy bien, ahora puedes decirles a otros que sé cómo fusionar y ordenar.

Pero si te pido que escribas el código, creo que no podrás...

Vamos, echemos un vistazo al algoritmo de clasificación por combinación que escribí en Python:

defmerge_sort(array):# Recursion Decompose mid=int((len(array)+1)/2) iflen(array)==1:# Condición para el final de la recursividad, finalizará cuando la lista solo tenga un retorno de datosarray list_left=merge_sort(array print(merge_sort(array) )Salida:

Salida:

>>>list_left: [49]

>> >list_right: [38]

> >>list_left: [38, 49]

>>>list_right: [65]

>>>list_left: [97]

>>>lista_derecha: [76]

>>>lista_izquierda: [38, 49, 65]

>>>lista_derecha: [ 76, 97]

[38, 49, 65, 76, 97]

Complejidad del tiempo: caso promedio = mejor caso = peor caso = O(nlogn)

Complejidad espacial: O(n)

Estabilidad: Estable

Un ejemplo de fusión y clasificación de la secuencia {6, 5, 3, 1, 8, 7, 2, 4 } es el siguiente:

El proceso macro de ordenar una columna de números mediante ordenación por fusión:

Lo anterior es el contenido completo de este artículo, espero que sea útil para todos. aprendiendo