Maison > Article > développement back-end > Guide d'implémentation et d'optimisation du tri par sélection Python
Étapes et méthodes d'optimisation du tri par sélection Python
Selection Sort est un algorithme de tri simple et intuitif. Son idée de base est de sélectionner à chaque fois l'élément le plus petit (ou le plus grand) parmi les éléments de données à trier, de le stocker au début de la séquence, puis de continuer à rechercher l'élément le plus petit (ou le plus grand) parmi les éléments non triés restants. , placé à la fin de la séquence triée. Répétez ce processus jusqu'à ce que tous les éléments de données à trier soient disposés.
Les étapes du tri par sélection peuvent être résumées comme suit :
Les méthodes d'optimisation du tri par sélection sont :
Ce qui suit est un exemple de code de tri par sélection en Python :
def selection_sort(arr): n = len(arr) for i in range(n - 1): min_pos = i max_pos = i for j in range(i + 1, n): if arr[j] < arr[min_pos]: min_pos = j if arr[j] > arr[max_pos]: max_pos = j if min_pos != i: arr[i], arr[min_pos] = arr[min_pos], arr[i] if max_pos == i: max_pos = min_pos if max_pos != n - 1 - i: arr[n - 1 - i], arr[max_pos] = arr[max_pos], arr[n - 1 - i] if min_pos == n - 1 - i: min_pos = max_pos if min_pos != i: arr[i], arr[min_pos] = arr[min_pos], arr[i] return arr # 测试 arr = [64, 25, 12, 22, 11] print("排序前:", arr) sorted_arr = selection_sort(arr) print("排序后:", sorted_arr)
Dans le code ci-dessus, la position de la variable min_pos
记录最小元素的位置,使用变量 max_pos
记录最大元素的位置。在每次遍历中,通过比较更新这两个位置,然后进行交换。在列表长度为奇数时,如果 min_pos
和 max_pos
que nous utilisons coïncide avec la position de départ, et nous devons vérifier et traiter la position échangée.
Ci-dessus sont les étapes et les méthodes d'optimisation du tri de sélection Python, ainsi que des exemples de code spécifiques. Bien que le tri par sélection soit simple, il est moins efficace et a une complexité temporelle de O(n^2). Par conséquent, dans les applications pratiques, si l’échelle de tri est grande, il est recommandé d’utiliser des algorithmes de tri plus efficaces, tels que le tri rapide ou le tri par fusion.
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!