Comment implémenter huit algorithmes de tri en Python

Cet article présente principalement l'implémentation Python des huit algorithmes de tri et fournit une description détaillée et l'implémentation du code des huit algorithmes de tri. Les amis intéressés peuvent se référer à

Implémentation Python des huit algorithmes de tri pour des informations spécifiques. contenu. Comme suit

1. Tri par insertion
Description

L'opération de base du tri par insertion consiste à insérer une donnée dans les données ordonnées triées, de manière à obtenez une nouvelle donnée ordonnée avec le nombre plus un, l'algorithme est adapté pour trier une petite quantité de données et la complexité temporelle est O(n^2). C'est une méthode de tri stable. L'algorithme d'insertion divise le tableau à trier en deux parties : la première partie contient tous les éléments du tableau, sauf le dernier élément (ce qui fait au tableau un espace de plus pour avoir une position d'insertion), et la deuxième partie ne contient que celui-ci. élément (c'est-à-dire l'élément à insérer). Une fois la première partie triée, ce dernier élément est inséré dans la première partie triée.

Mise en œuvre du code

def insert_sort(lists):
  # 插入排序
  count = len(lists)
  for i in range(1, count):
    key = lists[i]
    j = i - 1
    while j >= 0:
      if lists[j] > key:
        lists[j + 1] = lists[j]
        lists[j] = key
      j -= 1
  return lists

2. Tri des collines
Description

Coquille Le tri est un type de tri par insertion. Également connu sous le nom de réduction du tri incrémentiel, il s’agit d’une version plus efficace et améliorée de l’algorithme de tri par insertion directe. Le tri Hill est un algorithme de tri non stable. Cette méthode est due à DL. Shell doit son nom à sa proposition en 1959. Le tri Hill regroupe les enregistrements par un certain incrément de l'indice et trie chaque groupe à l'aide de l'algorithme de tri par insertion directe à mesure que l'incrément diminue progressivement, chaque groupe contient de plus en plus de mots-clés lorsque l'incrément diminue à 1, une fois que le fichier entier a été. regroupés en un seul groupe, l'algorithme se termine.

Mise en œuvre du code

def shell_sort(lists):
  # 希尔排序
  count = len(lists)
  step = 2
  group = count / step
  while group > 0:
    for i in range(0, group):
      j = i + group
      while j < count:
        k = j - group
        key = lists[j]
        while k >= 0:
          if lists[k] > key:
            lists[k + group] = lists[k]
            lists[k] = key
          k -= group
        j += group
    group /= step
  return lists

Tri des bulles
Description

Il parcourt à plusieurs reprises la séquence à trier, en comparant deux éléments à la fois et en les échangeant s'ils sont dans le mauvais ordre. Le travail de visite du tableau est répété jusqu'à ce qu'aucun échange ne soit plus nécessaire, ce qui signifie que le tableau a été trié.

Implémentation du code

def bubble_sort(lists):
  # 冒泡排序
  count = len(lists)
  for i in range(0, count):
    for j in range(i + 1, count):
      if lists[i] > lists[j]:
        lists[i], lists[j] = lists[j], lists[i]
  return lists

Tri rapide
Description

Réussi. Le tri en un seul passage divise les données à trier en deux parties indépendantes. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie. Ensuite, les deux parties des données sont rapidement triées séparément selon cette méthode. Le processus de tri peut être récursif. Effectuer de manière à ce que l'ensemble des données devienne une séquence ordonnée.

Mise en œuvre du code

def quick_sort(lists, left, right):
  # 快速排序
  if left >= right:
    return lists
  key = lists[left]
  low = left
  high = right
  while left < right:
    while left < right and lists[right] >= key:
      right -= 1
    lists[left] = lists[right]
    while left < right and lists[left] <= key:
      left += 1
    lists[right] = lists[left]
  lists[right] = key
  quick_sort(lists, low, left - 1)
  quick_sort(lists, left + 1, high)
  return lists

5. Tri par sélection directe
Description

Idée de base : lors du premier passage, sélectionnez le plus petit enregistrement parmi les enregistrements à trier r1 ~ r[n], et échangez-le avec r1 lors du deuxième passage, sélectionnez le plus petit enregistrement parmi les enregistrements à trier r2 ~ r[ ; n] , échangez-le avec r2 ; et ainsi de suite, la i-ème passe sélectionne le plus petit enregistrement parmi les enregistrements à trier r[i] ~ r[n], et l'échange avec r[i], de sorte que l'ordre La séquence continue de croître jusqu'à ce que tout soit trié.

Implémentation du code

def select_sort(lists):
  # 选择排序
  count = len(lists)
  for i in range(0, count):
    min = i
    for j in range(i + 1, count):
      if lists[min] > lists[j]:
        min = j
    lists[min], lists[i] = lists[i], lists[min]
  return lists

6. Tri du tas
Description

Tas Le tri (Heapsort) fait référence à un algorithme de tri conçu à l'aide d'une structure de données telle qu'un arbre empilé (tas). Il s'agit d'un type de tri par sélection. Vous pouvez utiliser les caractéristiques des tableaux pour localiser rapidement l'élément à un index spécifié. Le tas est divisé en un grand tas de racines et un petit tas de racines, qui est un arbre binaire complet. L'exigence d'un grand tas racine est que la valeur de chaque nœud ne soit pas supérieure à la valeur de son nœud parent, c'est-à-dire A[PARENT[i]] >= A[i]. Dans le tri non décroissant d'un tableau, un grand tas racine doit être utilisé, car selon les exigences d'un grand tas racine, la plus grande valeur doit être en haut du tas.

Implémentation du code

# 调整堆
def adjust_heap(lists, i, size):
  lchild = 2 * i + 1
  rchild = 2 * i + 2
  max = i
  if i < size / 2:
    if lchild < size and lists[lchild] > lists[max]:
      max = lchild
    if rchild < size and lists[rchild] > lists[max]:
      max = rchild
    if max != i:
      lists[max], lists[i] = lists[i], lists[max]
      adjust_heap(lists, max, size)

# 创建堆
def build_heap(lists, size):
  for i in range(0, (size/2))[::-1]:
    adjust_heap(lists, i, size)

# 堆排序
def heap_sort(lists):
  size = len(lists)
  build_heap(lists, size)
  for i in range(0, size)[::-1]:
    lists[0], lists[i] = lists[i], lists[0]
    adjust_heap(lists, 0, i)

7. Tri par fusion
Description

Fusionner Le tri est un algorithme de tri efficace basé sur des opérations de fusion. Cet algorithme est une application très typique utilisant la méthode diviser pour mieux régner (pide and Conquer). Fusionnez les sous-séquences déjà ordonnées pour obtenir une séquence complètement ordonnée ; c'est-à-dire que vous devez d'abord rendre chaque sous-séquence ordonnée, puis ordonner les segments de la sous-séquence. Si deux listes ordonnées sont fusionnées en une seule liste ordonnée, on parle de fusion bidirectionnelle.

Le processus de fusion est le suivant : comparez les tailles de a[i] et a[j], si a[i]≤a[j], copiez l'élément a[i] dans la première liste ordonnée dans r [k], et ajoutez 1 à i et k respectivement ; sinon, copiez l'élément a[j] dans la deuxième liste ordonnée dans r[k], et ajoutez 1 à j et k respectivement. Ce cycle continue jusqu'à l'un des éléments ordonnés. lists est récupéré, puis les éléments restants de l’autre liste ordonnée sont copiés dans les cellules de r de l’indice k à l’indice t. Nous utilisons généralement la récursion pour implémenter l'algorithme de tri par fusion. Tout d'abord, l'intervalle à trier [s, t] est divisé en deux par le point médian, puis la sous-plage de gauche est triée, puis la sous-plage de droite est triée, et enfin, l'intervalle de gauche et l'intervalle de droite sont fusionnés en intervalles ordonnés [s,t].

Implémentation du code

def merge(left, right):
  i, j = 0, 0
  result = []
  while i < len(left) and j < len(right):
    if left[i] <= right[j]:
      result.append(left[i])
      i += 1
    else:
      result.append(right[j])
      j += 1
  result += left[i:]
  result += right[j:]
  return result

def merge_sort(lists):
  # 归并排序
  if len(lists) <= 1:
    return lists
  num = len(lists) / 2
  left = merge_sort(lists[:num])
  right = merge_sort(lists[num:])
  return merge(left, right)

Tri Radix
Description

Radix Le tri (tri par base) appartient au « tri par distribution », également appelé « tri par compartiment » ou tri par bac, comme son nom l'indique, il utilise une partie des informations sur la valeur clé pour distribuer les éléments à trier dans certains « compartiments ». la méthode de tri par base est une méthode de tri stable et sa complexité temporelle est O (nlog(r)m), où r est la base prise et m est le nombre de tas, à certains moments, l'efficacité de la méthode de tri par base est. plus élevé que les autres méthodes de tri de stabilité.

Mise en œuvre du code

import math
def radix_sort(lists, radix=10):
  k = int(math.ceil(math.log(max(lists), radix)))
  bucket = [[] for i in range(radix)]
  for i in range(1, k+1):
    for j in lists:
      bucket[j/(radix**(i-1)) % (radix**i)].append(j)
    del lists[:]
    for z in bucket:
      lists += z
      del z[:]
  return lists

以上就是Python实现八大排序算法的详细介绍，希望对大家的学习有所帮助。

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!