Dix principaux algorithmes de tri que les programmeurs doivent maîtriser (Partie 1)

Introduction à ce numéro

algorithme de tri On peut dire que chaque programmeur doit le maîtriser Il est nécessaire de comprendre leurs principes et leur mise en œuvre Ce 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

01

Bubble Sort

Bubble Sort: Un algorithme de tri classique, car pendant le fonctionnement de l'algorithme, les valeurs extrêmes apparaissent progressivement comme bulles au fond de l'eau, d'où son nom.

Principe de l'algorithme :

• 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.

Le code est le suivant :

'''冒泡排序'''
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]

02

Vite Sort

Tri rapide :

L'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée, ce qui constitue une amélioration par rapport à l'algorithme de tri à bulles.

Principe de l'algorithme :

.

• 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é.

Le code est le suivant :

'''快速排序'''
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]

03

Sélectionner le tri

Tri par sélection : C'est un tri simple et intuitif algorithme. Quelles que soient les données saisies, la complexité temporelle est O(n²). Ainsi, lors de son utilisation, plus la taille des données est petite, mieux c'est.

Trouver le plus petit (grand) élément dans la séquence non triée et le stocker à la position de départ de la séquence triée.

Continuez à trouver le plus petit (grand) élément parmi les éléments non triés restants, puis placez-le à la fin de la séquence triée.

• 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(&#39;result list: &#39;, result)
# result list: [5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

04

插入排序

插入排序（Insertion Sort）：一般也被称为直接插入排序，是一种最简单直观的排序算法。

算法原理：

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  

• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。

代码如下：

'''插入排序'''
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(&#39;result list: &#39;, result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

05

堆排序

堆排序（Heap sort）：是指利用堆这种数据结构所设计的一种排序算法，堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

算法原理：

• 创建一个堆 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(&#39;result list: &#39;, 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!