algorithme de triOn peut dire que chaque programmeur doit le maîtriserIl est nécessaire de comprendre leurs principes et leur mise en œuvreCe qui suit est une introduction à l'implémentation python des dix principaux algorithmes de tri couramment utilisés pour faciliter votre apprentissage.
01 Tri à bulles - Tri par échange
02 Tri rapide - Tri par échange
03 Tri par sélection - Tri par sélection
04 Tri par tas - tri par sélection
05 Tri par insertion - tri par insertion
06 Tri par colline - tri par insertion
07 Tri par fusion - Tri par fusion
08 Tri comptage - tri distribution
09 Tri Radix - tri distribution
10 Tri seau - tri distribution
Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-les tous les deux.
Faites de même pour chaque paire d'éléments adjacents, en commençant par la première paire au début et en terminant par la dernière paire à la fin. À ce stade, le dernier élément doit être le plus grand nombre.
Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.
Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait plus de paires de nombres à comparer.
'''冒泡排序''' def Bubble_Sort(arr): for i in range(1, len(arr)): for j in range(0, len(arr)-i): if arr[j] > arr[j+1]: arr[j], arr[j + 1] = arr[j + 1], arr[j] return arr arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22] result = Bubble_Sort(arr) print('result list: ', result) # result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]
Concentrez les données supérieures ou égales à la valeur seuil sur le côté droit du tableau et les données plus petites que la valeur seuil sur le côté gauche du tableau. À ce stade, chaque élément de la partie gauche est inférieur ou égal à la valeur de division, et chaque élément de la partie droite est supérieur ou égal à la valeur de division.
Ensuite, les données de gauche et de droite peuvent être triées indépendamment. Pour les données du tableau de gauche, vous pouvez prendre une valeur de division et diviser cette partie des données en parties gauche et droite. De même, placez la plus petite valeur à gauche et la plus grande valeur à droite. Les données du tableau à droite peuvent également être traitées de la même manière.
Répétez le processus ci-dessus jusqu'à ce que le tri des données des parties gauche et droite soit terminé.
'''快速排序''' def Quick_Sort(arr): # 递归入口及出口 if len(arr) >= 2: # 选取基准值,也可以选取第一个或最后一个元素 mid = arr[len(arr) // 2] # 定义基准值左右两侧的列表 left, right = [], [] # 从原始数组中移除基准值 arr.remove(mid) for num in arr: if num >= mid: right.append(num) else: left.append(num) return Quick_Sort(left) + [mid] + Quick_Sort(right) else: return arr arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18] result = Quick_Sort(arr) print('result list: ', result) # result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]
et ainsi de suite jusqu'à ce que tous les éléments soient triés.
'''选择排序''' def Selection_Sort(arr): for i in range(len(arr) - 1): # 记录最小数的索引 minIndex = i for j in range(i + 1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j # i 不是最小数时,将 i 和最小数进行交换 if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr arr = [5, 10, 76, 55, 13, 79, 49, 51, 65, 30] result = Quick_Sort(arr) print('result list: ', result) # result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]
将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。
'''插入排序''' def Insertion_Sort(arr): for i in range(1, len(arr)): key = arr[i] j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key return arr arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53] result = Insertion_Sort(arr) print('result list: ', result) # result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]
创建一个堆 H[0……n-1];
把堆首(最大值)和堆尾互换;
把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;
重复步骤 2,直到堆的尺寸为 1。
'''堆排序''' def Heapify(arr, n, i): largest = i # 左右节点分块 left = 2 * i + 1 right = 2 * i + 2 if left < n and arr[i] < arr[left]: largest = left if right < n and arr[largest] < arr[right]: largest = right if largest != i: # 大小值交换 arr[i], arr[largest] = arr[largest], arr[i] # 递归 Heapify(arr, n, largest) def Heap_Sort(arr): nlen = len(arr) for i in range(nlen, -1, -1): # 调整节点 Heapify(arr, nlen, i) for i in range(nlen - 1, 0, -1): arr[i], arr[0] = arr[0], arr[i] # 调整节点 Heapify(arr, i, 0) return arr arr = [26, 53, 83, 86, 5, 46, 72, 21, 4, 75] result = Heap_Sort(arr) print('result list: ', result) # result list: [4, 5, 21, 26, 46, 53, 72, 75, 83, 86]
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!