[PYTHON] Verstehen Sie den Prozess der Sortierung von Zusammenführungen. Nach dem Durchfluss fein zerlegen.
Was ist Zusammenführungssortierung?
Eine Art Sorte. Stabile Sorte. Es verwendet die Divide-and-Conquer-Methode.
- Teilen Sie das zu sortierende Array in zwei Teile ――Wiederholen Sie die Unterteilung in zwei Teile, bis ein Element vorhanden ist (Teilen) --Vergleichen Sie jedes führende Element und verschmelzen Sie mit der kleineren Zahl vorwärts (lösen, zusammenführen) --Vergleichen Sie die ersten Zahlen der sortierten Elemente und führen Sie sie nebeneinander zusammen (erobern, zusammenführen)
Referenz: Kagoshima University HP
## Sortiercode zusammenführen
python
#Nach dem Zerlegen in die kleinsten Einheiten zusammenführen. Wiederholen Sie diesen Vorgang
def merge_sort(arr):
#Wenn das Element 1 oder 0 ist, wird das Array so zurückgegeben, wie es ist. (Weil es kein Vergleichsziel gibt und keine Sortierung erforderlich ist)
if len(arr) <= 1:
return arr
#In zwei Teile teilen. Extrahieren Sie nur den ganzzahligen Teil, um ihn durch Schneiden zu trennen
mid = len(arr)//2
#Teilen Sie das ursprüngliche Array in zwei Teile
arr1 = arr[:mid]
arr2 = arr[mid:]
#Teilen Sie weiter in zwei Teile, bis die minimale Einheit erreicht ist
#Die Wiederholung endet, wenn sie zurückgegeben wird
arr1 = merge_sort(arr1)
arr2 = merge_sort(arr2)
return merge1(arr1, arr2)
#Vergleichen Sie die beiden Elemente und setzen Sie das kleinere zuerst ein
def merge1(arr1,arr2):
#Array, um das Zusammenführungsergebnis zu setzen
merged = []
l_i, r_i =0,0
while l_i < len(arr1) and r_i < len(arr2):
if arr1[l_i] <= arr2[r_i]:
merged.append(arr1[l_i])
l_i += 1
else:
merged.append(arr2[r_i])
r_i += 1
if l_i < len(arr1):
merged.extend(arr1[l_i:])
if r_i < len(arr2):
merged.extend(arr2[r_i:])
return merged
Bestätigung
list=[7,4,3,5,6,1,2]
merge_sort(list)
#[1, 2, 3, 4, 5, 6, 7]
## Sortierdetails zusammenführen Da zwei Funktionen ausgeführt werden, ist es schwer zu verstehen. Lassen Sie es uns zusammenfassen.
- Funktion zur kleinsten Einheit (div_arr)
- Eine Funktion (Zusammenführung), die die kleinere zum Array hinzufügt.
Funktion zur Herstellung der kleinsten Einheit
Betrachten Sie zunächst eine Funktion, die jedes Element unterteilt.
python
def div_arr(arr):
#Wenn das Element 1 oder 0 ist, wird das Array so zurückgegeben, wie es ist. (Weil es kein Vergleichsziel gibt und keine Sortierung erforderlich ist)
if len(arr) <= 1:
return print(arr)
#In zwei Teile teilen. Extrahieren Sie nur den ganzzahligen Teil, um ihn durch Schneiden zu trennen
mid = len(arr)//2
#Teilen Sie das ursprüngliche Array in zwei Teile
arr1 = arr[:mid]
arr2 = arr[mid:]
#Teilen Sie weiter in zwei Teile, bis die minimale Einheit erreicht ist
#Die Wiederholung endet, wenn sie zurückgegeben wird
arr1 = div_arr(arr1)
arr2 = div_arr(arr2)
Bestätigung
list=[7,4,3,5,6,1,2]
div_arr(list)
[7]
[4]
[3]
[5]
[6]
[1]
[2]
Der Punkt ist, zwei vorzubereiten, arr1 und arr2. Der in die Funktion eingegebene Wert ist zweigeteilt, und die Verarbeitung wird immer auf der Rückseite (arr2) gespeichert.
Daher wird die Verarbeitung auch nach dem Ende von arr1 mit der Rückgabe fortgesetzt, solange arr2 vorrätig ist.
Ich habe erwartet, dass das Array mit "return arr" ausgegeben wird, aber da nichts angezeigt wird, habe ich es auf "return print (arr)" gesetzt. (Ich weiß nicht, warum es nicht erscheint ...)
### (Referenz) Wenn die rekursive Verarbeitung nur in der ersten Reihe ausgeführt wird
python
def div_arr(arr):
if len(arr) <= 1:
return print(arr)
mid = len(arr)//2
arr1 = arr[:mid]
arr1 = div_arr(arr1)
python
list=[7,4,3,5,6,1,2]
div_arr(list)
[7]
Da nur arr1 verarbeitet wird, wird nur [7] ausgegeben.
- Es wird nicht [7], [4], [3]. Weil [4] und [3] arr2 zugewiesen werden, während der rekursive Prozess wiederholt wird.
## Eine Funktion, die dem Array die kleinere hinzufügt
python
#Vergleichen Sie die beiden Elemente und setzen Sie das kleinere zuerst ein
def merge1(arr1,arr2):
#Array, um das Zusammenführungsergebnis zu setzen
#Der Anfangswert ist 0, aber der Inhalt erhöht sich jedes Mal, wenn die Zusammenführung wiederholt wird.
merged = []
#Anfangswert der Array-Nummer des zu vergleichenden Elements
l_i, r_i =0,0
#Schleifenendbedingung. Vergleich aller Arrays und Endungen
while l_i < len(arr1) and r_i < len(arr2):
#Wenn das vordere Element kleiner ist
#Wenn sie gleich sind, geben Sie der anderen Partei Priorität
if arr1[l_i] <= arr2[r_i]:
merged.append(arr1[l_i])
#Fügen Sie der Sequenznummer 1 hinzu, damit dasselbe Element nicht erneut überprüft wird.
l_i += 1
else:
merged.append(arr2[r_i])
r_i += 1
#Wenn die while-Anweisung endet, fügen Sie die gesamte Antwort hinzu, die nicht hinzugefügt wurde.
#Da jedes Array bereits in aufsteigender Reihenfolge sortiert wurde, wird es unverändert hinzugefügt.
if l_i < len(arr1):
merged.extend(arr1[l_i:])
if r_i < len(arr2):
merged.extend(arr2[r_i:])
return merged
Bestätigung
a=[2,3]
b=[1,8,9]
merge1(a,b)
#[1, 2, 3, 8, 9]
## Visualisieren Sie den gesamten Verarbeitungsablauf Schauen wir uns anhand der beiden oben genannten Prozesse den Prozess von merge_sort an.
python
#Array zum Sortieren
arr=[7,4,3,5,6]
#Erster Prozess
arr1=[7,4]
arr2=[3,5,6]
#Rekursive arr1
arr1`=[7]
arr2`=[4]
##Lösung von arr1##
merge`=[4,7]
#Rekursives arr2
arr1``=[3]
arr2``=[5,6]
#arr2``Wiederholt sich
arr1```=[5]
arr2```=[6]
##arr2``Lösung von##
merge``=[5,6]
##Lösung von arr2##
merge```=[3,5,6]
## Endlich Arrs Lösung ##
merge=[3,4,5,6,7]
## Die Lösung von arr ist eine Verschmelzung von arr1 und arr2
# Lösung von arr1 merge` = [4,7]
#arr2 Lösung zusammenführen```=[3,5,6]
Es ist kompliziert. ** Die letzten 3 Zeilen sind wichtig **
python
arr1 = merge_sort(arr1)
arr2 = merge_sort(arr2)
return merge1(arr1, arr2)
Der zusammengeführte Wert (Ergebnis von merge1) wird bei jeder Ausführung von merge_sort in arr1 und arr2 eingegeben.
Es wird weiter zusammengeführt.
Damit werden die auf die minimale Einheit zerlegten Elemente wieder zusammengesetzt.
Die Person, die das für erstaunlich hielt, und die Person, die das versteht, ist auch erstaunlich
Recommended Posts