[PYTHON] Sortierung mit rekursiv zusammenführen

So führen Sie die Sortierung mit rekursiv zusammen

• Es fühlt sich wie ein Memorandum an (weil ich es vergesse, wenn ich zurückblicke, denke ich, dass es Dinge gibt, die ich nicht nur mit dem Code verstehen kann)

Array-Daten = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]

1. Teilen Sie links (links) und rechts (rechts) in der Mitte des Arrays => Links [3,1,9,4,2] Rechts [5,7,6,8,10] Mitte: 5

2. Teilen Sie weiter durch links und rechts (verwenden Sie rekursiv) => Links [3,1,9,4,2] -> Links [3,1] Rechts [9,4,2] Mitte: 2 Rechts [5,7,6,8,10] -> Links [5,7] Rechts [6,8,10] ....

3. Schließlich wird es [3], [1], [9], [4], [2], [5], [7], [6], [8], [10] sein (Vorbereitung abgeschlossen) !)

4. Dieses Mal werden die zweigeteilten Werte den neuen Variablen (result_sort) in der Reihenfolge von links zugewiesen (da sie bei 0 beginnen). [3,1], [4,2] => Sortieren [1,3] [2,4]

• Es gibt keine [9] und [6]! Warum? => Beim Teilen von [9,4,2] Da die Mitte "1" ist, rechts: [9] Links: [4,2], beginnt die Verarbeitung zuerst bei [4,2]. (Für eine Wiederholung fahren Sie mit 1-> 2-> 3-> 4-> 5 fort und spulen dann zurück, während Sie mit 5-> 4-> 3-> 2-> 1 zurückspulen.) => * * Um Ihr Verständnis zu vertiefen, studieren Sie die Wiederholung **

5. [9] und [4,2] sind sortiert nach-> [9] und [4,2] -> result_sort => [2,4,9]
6. [3,1] und [9,4,2] sind sortiert nach-> [3,1] und [9,4,2] -> result_sort => [1,2,3,4,9]
7. Recht ist vollständig. Als nächstes machen Sie 4 bis 6 von links 8 [3,1,9,4,2] und rechts [5,7,6,8,10] werden verglichen 9 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Erklärung im Code (Python)

sample.py

data = [3, 1, 9, 4, 2, 5, 7, 6, 8, 10]

Weisen Sie Variablen Daten zu

sample.py

def merge_sort(data):
    if len(data) <= 1: #True, wenn der Inhalt des Arrays 1 oder weniger beträgt
        return data
    center = len(data) // 2 #Mitte des Arrays
    left = merge_sort(data[:center])#Links geteilt[3,1,9,4,2] => [3,1] => [3]
    right = merge_sort(data[center:]) #Rechts geteilt[5,7,6,8,10] => [9,4,2] => [1]
    return left, right #=> [3], [1]Ist bestanden

Mit diesem Code können Sie 1 ~ 3 ausführen.

sample.py

def merge_sort(data):
    if len(data) <= 1: #True, wenn der Inhalt des Arrays 1 oder weniger beträgt
        return data
    center = len(data) // 2 #Mitte des Arrays
    left = merge_sort(data[:center])#Links geteilt[3,1,9,4,2] => [3,1] => [3]
    right = merge_sort(data[center:]) #Rechts geteilt[5,7,6,8,10] => [9,4,2] => [1]
    return merge(left, right)

Fügen Sie einfach "return merge (left, right)" hinzu

sample.py

def merge(left, right):
    result_sort = [] #Kombiniertes Ergebnis
    left_i, right_j = 0, 0
    print(left + right) #=>Kennen Sie die Reihenfolge, die Sie sortieren möchten
    while(left_i < len(left)) and (right_j < len(right)):
        if left[left_i] <= right[right_j]:
            result_sort.append(left[left_i]) #Vergleichen Sie hier rechts und links, die Sie kombinieren möchten, und treffen Sie das Ergebnis.
            left_i += 1
        else:
            result_sort.append(right[right_j]) #Vergleichen Sie hier rechts und links, die Sie kombinieren möchten, und treffen Sie das Ergebnis.
            right_j += 1
    if len(left[left_i:]) != 0: #=>True, wenn die Zahl im linken Array, die sortiert, aber übrig geblieben ist, nicht 0 ist(left_Überprüfen Sie mit i)
        result_sort.extend(left[left_i:])
    if len(right[right_j:]) != 0:
        result_sort.extend(right[right_j:]) #True (rechts), wenn die Zahl im rechten Array, die sortiert, aber übrig geblieben ist, nicht 0 ist_Bestätigen Sie mit j)
    print(result_sort) #=>Sie können die sortierte Reihenfolge sehen
    return result #Endgültiger Rückgabewert

4 ~ 8 machen

Zitat (Danke)

• https://medium-company.com/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88/
• https://qiita.com/woolon/items/4cff50de7e697cb2664f