Maison >développement back-end >Tutoriel Python >Comment implémenter un algorithme de tri à bulles en utilisant Python ?
Comment implémenter un algorithme de tri à bulles en utilisant Python ?
L'algorithme de tri à bulles est un algorithme de tri simple mais efficace. Son idée est de comparer en continu deux éléments adjacents si leur ordre est incorrect, échangez leurs positions jusqu'à ce que toute la séquence soit triée. Ce qui suit montrera comment utiliser Python pour implémenter l'algorithme de tri à bulles à travers des exemples de code spécifiques.
def bubble_sort(arr): n = len(arr) # 外层循环控制比较的轮数 for i in range(n - 1): # 内层循环控制每轮的比较次数 for j in range(n - i - 1): # 如果相邻的两个元素顺序不正确,则交换它们的位置 if arr[j] > arr[j + 1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr # 测试示例 arr = [64, 34, 25, 12, 22, 11, 90] sorted_arr = bubble_sort(arr) print("排序后的数组:", sorted_arr)
Dans le code ci-dessus, nous définissons une fonction appelée bubble_sort
, qui accepte une liste comme paramètre et renvoie la liste triée. La partie centrale du tri à bulles est une boucle imbriquée à deux niveaux. La boucle externe contrôle le nombre de tours de comparaison. Chaque tour de comparaison déplace le plus grand élément de la partie non triée vers la fin. La boucle interne contrôle le nombre de comparaisons par tour, en comparant deux éléments adjacents et en échangeant leurs positions s'ils ne sont pas dans le bon ordre. Le nombre de boucles et d'échanges augmente avec la taille de la séquence à trier, donc la complexité temporelle du tri à bulles est O(n^2). bubble_sort
的函数,该函数接受一个列表作为参数,并返回排序后的列表。冒泡排序的核心部分是两层嵌套的循环。外层循环控制比较的轮数,每一轮比较都会使得未排序部分中最大的元素移到最后。内层循环控制每轮比较的次数,通过比较相邻的两个元素,如果它们的顺序不正确,则交换它们的位置。循环的次数和交换的次数都随着待排序序列的大小而增加,因此冒泡排序的时间复杂度为O(n^2)。
在上述代码中,我们使用了一组测试示例来验证排序算法的正确性。在这个例子中,我们使用了一个包含7个元素的整数列表,并将其传递给bubble_sort
函数。运行程序后,控制台将输出排序后的列表。对于给定的测试示例,输出应该是 [11, 12, 22, 25, 34, 64, 90]
bubble_sort
. Après avoir exécuté le programme, la console affichera la liste triée. Pour l'exemple de test donné, la sortie doit être [11, 12, 22, 25, 34, 64, 90]
. Au-delà de cet exemple simple, l'algorithme de tri à bulles peut être appliqué à tout type d'éléments comparables. Vous pouvez utiliser le tri à bulles pour trier des entiers, des nombres à virgule flottante, des chaînes, etc. Dans le même temps, nous pouvons également optimiser l'algorithme de tri en fonction de nos propres besoins, par exemple en ajoutant un indicateur pour déterminer si le tri est terminé, ce qui peut réduire le nombre de comparaisons inutiles.
Résumé :
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!