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

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 classe d'insertion

06 Tri par colline - Tri par classe par insertion

07 Tri par fusion - Tri par classe de fusion

08 tri - tri distribution

09 Tri Radix - tri distribution

10 Tri Bucket - tri distribution

06

Tri des collines

Tri) : est le tri par insertion Un, également connu sous le nom de « Décroissant Increment Sort", est une version plus efficace et améliorée de l'algorithme de tri par insertion directe.

Principe de l'algorithme :

• (l'écart est appelé l'étape taille) inférieure à n Les éléments à trier sont divisés en plusieurs sous-séquences de groupes, tous les enregistrements dont la distance est un multiple de l'écart sont placés dans le même groupe
  Un tri par insertion directe est effectué sur les éléments de chaque groupe. Une fois ce tri terminé, les éléments de chacun. Les groupes sont Réduisez la valeur de l'écart dans l'ordre

• , et répétez le regroupement et le tri ci-dessus

• Répétez l'opération ci-dessus, lorsque l'écart = 1, le tri se termine

Le code est le suivant :

'''希尔排序'''
def Shell_Sort(arr):
    # 设定步长,注意类型
    step = int(len(arr) / 2)
    while step > 0:
        for i in range(step, len(arr)):
            # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
            while i >= step and arr[i - step] > arr[i]:
                arr[i], arr[i - step] = arr[i - step], arr[i]
                i -= step
        step = int(step / 2)
    return arr

arr = [29, 63, 41, 5, 62, 66, 57, 34, 94, 22]
result = Shell_Sort(arr)
print('result list: ', result)
# result list: [5, 22, 29, 34, 41, 57, 62, 63, 66, 94]

07

Fusionner le tri

Merge Sort : est un algorithme de tri efficace et stable basé sur l'opération de fusion. L'algorithme utilise la méthode diviser pour régner. Une application très typique consiste à fusionner de manière ordonnée. sous-séquences pour obtenir une séquence complètement ordonnée.

Appliquer l'espace pour que sa taille soit la somme des deux triés séquences. Cet espace est utilisé pour stocker la séquence fusionnée. La séquence

définit deux index. Les positions initiales

index
• sont les positions de départ des deux séquences triées
  et comparez les éléments pointés par les deux
index
• . sélectionnez les éléments relativement petits dans l'espace de fusion et déplacez le

  index vers la position suivante

• Répétez l'étape précédente jusqu'à ce qu'un certain

  index dépasse la fin de la séquence

  . et supprimez tous les éléments restants de l'autre séquence. Les éléments sont copiés directement à la fin de la séquence fusionnée

代码如下：

'''归并排序'''def Merge(left, right):
    arr = []
    i = j = 0
    while j < len(left) and  i < len(right):
        if left[j] < right[i]:
            arr.append(left[j])
            j += 1
        else:
            arr.append(right[i])
            i += 1
    if j == len(left):
        # right遍历完
        for k in right[i:]:
            arr.append(k)
    else:
        # left遍历完
        for k in left[j:]:
            arr.append(k)
    return arr

def Merge_Sort(arr):
    # 递归结束条件
    if len(arr) <= 1:
        return arr
    # 二分
    middle = len(arr) // 2
    left = Merge_Sort(arr[:middle])
    right = Merge_Sort(arr[middle:])
    # 合并
    return Merge(left, right)

arr = [27, 70, 34, 65, 9, 22, 47, 68, 21, 18]
result = Merge_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [9, 18, 21, 22, 27, 34, 47, 65, 68, 70]

08

计数排序

计数排序（Count sort）：是一个非基于比较的排序算法，它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。

算法原理：

• 找出待排序的数组中最大和最小的元素

• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项

• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

代码如下：

'''计数排序'''
def Count_Sort(arr):
    max_num = max(arr)
    min_num = min(arr)
    count_num = max_num - min_num + 1
    count_arr = [0 for i in range(count_num)]
    res = [0 for i in range(len(arr))]
    # 统计数字出现的次数
    for i in arr:
        count_arr[i - min_num] += 1
    # 统计前面有几个比自己小的数
    for j in range(1, count_num):
        count_arr[j] = count_arr[j] + count_arr[j - 1]
    # 遍历重组
    for k in range(len(arr)):
        res[count_arr[arr[k] - min_num] - 1] = arr[k]
        count_arr[arr[k] - min_num] -= 1
    return res

arr = [5, 10, 76, 55, 13, 79, 5, 49, 51, 65, 30, 5]
result = Count_Sort(arr)
print('result list: ', result)
# result list: [5, 5, 5, 10, 13, 30, 49, 51, 55, 65, 76, 79]

09

基数排序

基数排序（radix sort）：是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法原理（以LSD为例）：

• 根据个位数的数值，遍历列表将它们分配至编号0到9的桶子中
  

• 将这些桶子中的数值重新串接起来

• 根据十位数的数值，遍历列表将它们分配至编号0到9的桶子中

• 再将这些桶子中的数值重新串接起来
  

代码如下：

'''基数排序'''
def Radix_Sort(arr):
    max_num = max(arr)
    place = 0
    while 10 ** place <= max_num:
        # 创建桶
        buckets = [[] for _ in range(10)]
        # 分桶
        for item in arr:
            pos = item // 10 ** place % 10
            buckets[pos].append(item)
        j = 0
        for k in range(10):
            for num in buckets[k]:
                arr[j] = num
                j += 1
        place += 1
    return arr

arr = [31, 80, 42, 47, 35, 26, 10, 5, 51, 53]
result = Radix_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [5, 10, 26, 31, 35, 42, 47, 51, 53, 80]

10

桶排序

桶排序 (Bucket sort)或所谓的箱排序：划分多个范围相同的桶区间，每个桶自排序，最后合并，桶排序可以看作是计数排序的扩展。

算法原理：

• 计算有限桶的数量
  

• 逐个桶内部排序

• 遍历每个桶，进行合并

代码如下：

'''桶排序'''
def Bucket_Sort(arr):
    num = max(arr)
    # 列表置零
    pre_lst = [0] * num
    result = []
    for data in arr:
        pre_lst[data - 1] += 1
    i = 0
    while i < len(pre_lst): # 遍历生成的列表，从小到大
        j = 0
        while j < pre_lst[i]:
            result.append(i + 1)
            j += 1
        i += 1
    return result

arr = [26, 53, 83, 86, 5, 46, 5, 72, 21, 4, 75]
result = Bucket_Sort(arr)
print(&#39;result list: &#39;, result)
# result list: [4, 5, 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!