Exemples de méthodes de tri d'allocation courantes dans les structures de données et les algorithmes Python [Tri par compartiment et tri par base]_python

Cet article présente principalement les méthodes courantes d'allocation et de tri des structures de données et des algorithmes Python. Il analyse les principes associés et les techniques de mise en œuvre du tri par compartiment et du tri par base sous forme d'exemples. Les amis qui ont besoin d'apprendre Python peuvent s'y référer. article et exemples de cet article Décrit les méthodes courantes d'allocation et de tri des structures de données et des algorithmes Python. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

Tri des boîtes (tri par seau)

Le tri des boîtes est basé sur le plage de valeurs du mot-clé 1~m, créez m boîtes à l'avance. Le tri par boîte nécessite que le type de mot-clé soit un type limité. Il peut y avoir une infinité de boîtes. Il a peu de valeur pratique et est généralement utilisé dans le processus intermédiaire de tri par base.

Le tri par buckets est une variante pratique du tri par boîtes. Il divise la plage de l'ensemble de données, telle que [0,1), en n sous-intervalles de même taille, chaque sous-intervalle est un bucket. , puis n non-enregistrements sont alloués à chaque compartiment. Étant donné que la séquence de mots clés est répartie uniformément sur [0,1), il n'y a généralement pas beaucoup d'enregistrements tombant dans le même compartiment.

La méthode de tri par compartiment suivante est implémentée à l'aide d'un dictionnaire, donc pour les types entiers, il n'est pas nécessaire de créer un espace supplémentaire

def BuckSort(A):
 bucks = dict()  # 桶
 for i in A:
  bucks.setdefault(i,[]) # 每个桶默认为空列表
  bucks[i].append(i)  # 往对应的桶中添加元素
 A_sort = []
 for i in range(min(A), max(A)+1):
  if i in bucks:     # 检查是否存在对应数字的桶
   A_sort.extend(bucks[i])  # 合并桶中数据
 return A_sort

Tri Radix

# 基数排序
# 输入：待排序数组s, keysize关键字位数, 亦即装箱次数, radix基数
def RadixSort(s, keysize=4, radix=10):
 # 按关键字的第k分量进行分配 k = 4,3,2,1
 def distribute(s,k):
  box = {r:[] for r in range(radix)}  # 分配用的空箱子
  for item in s:   # 依次扫描s[]，将其装箱
   t = item
   t /= 10**(k-1)
   t %= 10    # 去关键字第k位
   box[t].append(item)
  return box
 # 按分配结果重新排列数据
 def collect(s,box):
  a = 0
  for i in range(radix):
   s[a:a + len(box[i])] = box[i][:] # 将箱子中元素的合并，覆盖到原来的数组中
   a += len(box[i])     # 增加偏移值
 # 核心算法
 for k in range(1,keysize+1):
  box = distribute(s,k)   # 按基数分配
  collect(s,box)     # 按分配结果拼合

Ce qui suit est extrait de : "Structures de données et algorithmes - Théorie et pratique"

Le tri cardinal peut être étendu au tri par plusieurs mots-clés, comme le tri des cartes de poker par couleur et par numéro.
Généralement, en supposant que le tableau linéaire comporte des éléments à trier et que chaque élément contient d mots-clés {k1, k2,...,kd}, alors le tableau linéaire a une référence ordonnée aux mots-clés pour le tableau linéaire. Deux éléments r[i] et r[j], 1<=i<=j<=n, satisfont la relation ordonnée suivante :
　{k1i,k2i,...,kdi} < ,...,kdj>
où k1 est appelé le mot-clé du chiffre le plus significatif et kd est appelé le mot-clé du chiffre le moins significatif
Il existe deux méthodes de tri : MSD (chiffre le plus significatif en premier) LSD (chiffre le moins significatif premier)

MSD : Triez d'abord les groupes par k1. Si les éléments d'un même groupe sont égaux au mot-clé k1, triez ensuite chaque groupe par k2 et divisez-le en sous-groupes, et ainsi de suite. la position la plus basse kd est utilisée pour trier chaque sous-groupe, puis lier chaque groupe.

LSD : contrairement à MSD, trier d'abord par kd, puis kd-1, et ainsi de suite.

PS : Voici un autre outil de démonstration sur le tri recommandé pour votre référence :

Animation en ligne Démonstration d'insertion/ outils de processus d'algorithme de sélection/bulle/fusion/Hill/tri rapide :
http://tools.jb51.net/aideddesign/paixu_ys

Ce qui précède C'est tout le contenu de cet article, j'espère qu'il pourra être utile à tout le monde ! !

Recommandations associées :

Implémentation Python d'un exemple de code d'algorithme de correspondance de chaînes

Partage d'expérience de démarrage avec le robot d'exploration Python

Résumé sur l'utilisation de la bibliothèque de journalisation en 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!