Python implémente huit algorithmes de tri

Comment utiliser Python pour implémenter huit algorithmes de tri

1. Tri par insertion
Description
Tri par insertion L'opération de base consiste à insérer une donnée dans les données ordonnées triées, obtenant ainsi une nouvelle donnée ordonnée avec le nombre plus un. L'algorithme est adapté au tri d'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. >
Description Le tri Shell 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, le fichier entier a été regroupé. dans exactement un groupe, et 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

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

Mise en œuvre 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

4. >

Description Divisez les données à trier en deux parties indépendantes en une seule passe de tri. Toutes les données d'une partie sont plus petites que toutes les données de la partie. other part. , puis utilisez cette méthode pour trier rapidement les deux parties des données respectivement. 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.
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. 🎜>

Description
Idée de base : Dans la première passe, sélectionnez le plus petit enregistrement parmi les enregistrements à trier r1 ~ r[n], et échangez-le avec r1 ; Lors du deuxième passage, le plus petit enregistrement est sélectionné parmi les enregistrements r2 ~ r[n] à trier, et il est échangé avec r2 et ainsi de suite, lors du i-ième passage, le plus petit enregistrement est sélectionné parmi les ; enregistrements r[i] ~ r[n] à trier. Obtenez le plus petit enregistrement et échangez-le avec r[i], de sorte que la séquence ordonnée continue de croître jusqu'à ce que tous soient triés.
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. >

Description

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). Vous pouvez utiliser les caractéristiques du tableau pour localiser rapidement l'élément à l'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. Mise en œuvre du code

7、归并排序
描述
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（pide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一 个有序表，称为二路归并。
归并过程为：比较a[i]和a[j]的大小，若a[i]≤a[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否 则将第二个有序表中的元素a[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复 制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序， 最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。
代码实现

 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)

8、基数排序
描述
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
代码实现

 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

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持PHP中文网。

更多Python实现八大排序算法相关文章请关注PHP中文网！