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)
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
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!