Ordenamiento de burbuja en Python

Document 对象参考手册Ejemplo de Python3

El ordenamiento de burbuja es un simplealgoritmo de ordenamiento por intercambio, cuyo principio de funcionamiento central es:

  1. Itera repetidamente sobre la lista a ordenar, comparando a la vezlos dos elementos adyacentes；
  2. Si el orden de los dos elementos no cumple con el requisito (por ejemplo, al ordenar en forma ascendente, el elemento anterior es mayor que el siguiente), entoncesse intercambian sus posiciones；
  3. Cada recorrido hará que elelemento más grande de la parte no ordenada actual suba hasta el final(en el caso de orden ascendente), como una burbuja que sube;
  4. Repite el proceso anterior hasta que toda la lista esté completamente ordenada (no se produzcan intercambios o se hayan recorrido todos los elementos).

Características clave

  • Tipo de ordenamiento: ordenamiento por intercambio
  • Complejidad temporal: peor caso / O(n²) (lista completamente en orden inverso), caso promedio / O(n²), mejor caso / O(n) (versión optimizada, lista ya ordenada)
  • Complejidad espacial: O(1) (ordenamiento in situ, sin espacio auxiliar adicional)
  • Estabilidad: ordenamiento estable (la posición relativa de elementos iguales no cambia)

Ejemplo

def bubbleSort(arr): n = len(arr) # Recorrer todos los elementos del array for i in range(n): # Los últimos i elementos ya están en la posición correcta (no es necesario compararlos) for j in range(0, n-i-1): if arr[j] > arr[j+1] : arr[j], arr[j+1] = arr[j+1], arr[j] arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print ("Array ordenado:") for i in range(len(arr)): print ("%d" %arr[i]),

El resultado de ejecutar el código anterior es:

排序后的数组:
11
12
22
25
34
64
90

Document 对象参考手册Ejemplo de Python3

Otras extensiones