Beispiele für gängige Allokationssortierungsmethoden in Python-Datenstrukturen und -Algorithmen [Bucket-Sortierung und Radix-Sortierung]_Python

Dieser Artikel stellt hauptsächlich die gängigen Zuordnungs- und Sortiermethoden von Python-Datenstrukturen und -Algorithmen vor. Er analysiert die zugehörigen Prinzipien und Implementierungstechniken der Bucket-Sortierung und der Basissortierung in Form von Beispielen Artikel und Beispiele dieses Artikels Beschreibt die gängigen Zuordnungs- und Sortiermethoden von Python-Datenstrukturen und -Algorithmen. Teilen Sie es als Referenz mit allen. Die Details lauten wie folgt:

Boxsortierung (Eimersortierung)

Die Boxsortierung basiert auf Der Wertebereich des Schlüsselworts beträgt 1 ~ m. Für die Boxsortierung muss es sich um einen begrenzten Typ von Schlüsselwörtern handeln, und es kann unendlich viele Boxen geben. Es hat im Allgemeinen einen geringen praktischen Wert und wird im Allgemeinen im Zwischenprozess der Basissortierung verwendet .

Bucket-Sortierung ist eine praktische Variante der Box-Sortierung. Sie unterteilt den Bereich des Datensatzes, z. B. [0,1), in n Teilintervalle gleicher Größe, wobei jedes Teilintervall ein Bucket ist , und dann werden jedem Bucket n Nicht-Datensätze zugewiesen. Da die Schlüsselwortsequenz gleichmäßig auf [0,1] verteilt ist, fallen im Allgemeinen nicht viele Datensätze in denselben Bucket.

Die folgende Bucket-Sortiermethode wird mithilfe eines Wörterbuchs implementiert, sodass für Ganzzahltypen kein zusätzlicher Platz geschaffen werden muss

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

Radix-Sortierung

# 基数排序
# 输入：待排序数组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)     # 按分配结果拼合

Das Folgende ist ein Auszug aus: „Datenstrukturen und Algorithmen - Theorie und Praxis“

Die Kardinalsortierung kann auf die Sortierung nach mehreren Schlüsselwörtern erweitert werden, beispielsweise auf die Sortierung von Pokerkarten nach Farbe oder Punkt.
Angenommen, die lineare Tabelle enthält zu sortierende Elemente und jedes Element enthält d Schlüsselwörter {k1, k2, ..., kd}, dann verfügt die lineare Tabelle über einen geordneten Verweis auf die Schlüsselwörter für die lineare Tabelle Zwei beliebige Elemente r[i] und r[j], 1<=i<=j<=n, erfüllen die folgende geordnete Beziehung:
　{k1i,k2i,...,kdi} < ,...,kdj🎜>wobei k1 als Schlüsselwort mit der höchstwertigen Ziffer und kd als Schlüsselwort mit der niedrigstwertigen Ziffer bezeichnet wird
Es gibt zwei Sortiermethoden: MSD (höchstwertige Ziffer zuerst) LSD (niederwertige Ziffer). zuerst)

MSD: Sortieren Sie zuerst die Gruppen nach k1, dann sortieren Sie jede Gruppe nach k2 und teilen Sie sie in Untergruppen usw. auf Die niedrigste Position von kd wird verwendet, um jede Untergruppe zu sortieren und dann jede Gruppe zu verknüpfen.

LSD: Im Gegensatz zu MSD wird zuerst nach kd, dann nach kd-1 usw. sortiert.

PS: Hier ist ein weiteres Demonstrationstool zum Sortieren, das als Referenz empfohlen wird:

Online-Animation Demonstration des Einfügens/ Auswahl-/Blase-/Zusammenführungs-/Hill-/Schnellsortieralgorithmus-Prozesstools:
http://tools.jb51.net/aideddesign/paixu_ys

Das Obige ist der gesamte Inhalt dieses Artikels, ich hoffe, er kann für alle hilfreich sein! !

Verwandte Empfehlungen:

Python-Implementierung des String-Matching-Algorithmus-Beispielcodes

Erfahrungsaustausch über die ersten Schritte mit dem Python-Crawler

Zusammenfassung zur Verwendung der Protokollierungsbibliothek in Python

Das obige ist der detaillierte Inhalt vonBeispiele für gängige Allokationssortierungsmethoden in Python-Datenstrukturen und -Algorithmen [Bucket-Sortierung und Radix-Sortierung]_Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!