[GO] Python-Anfänger organisieren schnelle Sortierungen

Dies ist ein Memorandum

Ich werde es wirklich vergessen

Website zitieren

Dieses Mal möchte ich die Websites vorstellen, die ich besucht habe, um sie früher zu organisieren.

• Algorithmusreferenz
• Trace-Referenz

Die Algorithmen selbst unterscheiden sich geringfügig voneinander. Da es sich jedoch um die gleiche schnelle Sortierung handelt, werden sie basierend auf dem Algorithmus von @ muijp organisiert.

Programm

[@ Muijps schnelle Sortierung](https://qiita.com/muijp/items/257e8b9b49d891137d56#%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3% 82% BD% E3% 83% BC% E3% 83% 88-Quick-Sort) hat ein zufälliges Array-Programm und eine Ausgabe zum Debuggen, die neulich von @shiracamus empfohlen wurde.

q_sort.py

def qSort(a):
    print(a)#Zum Debuggen
    if len(a) in (0, 1):
        return a

    p = a[-1]
    l = [x for x in a[:-1] if x <= p]
    r = [x for x in a[:-1] if x >  p]

    return qSort(l) + [p] + qSort(r)
a = r.sample(range(1,11),k=9)
qSort(a)
#Ausgabe_____________________
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

Ja, das Programm ist zu kurz, um es zu verstehen.

Zerlegen und nachdenken

Das erste, was zu bemerken ist return qSort(l) + [p] + qSort(r) Ich denke, dass. Dies ist der Teil, in dem kleine Zahlen (Anordnung) und große Zahlen (Anordnung) rechts und links vom "Drehpunkt (interessierende Zelle)" platziert werden, was ein Merkmal der schnellen Sortierung ist.

Trace-Referenz Wenn Sie sich das GIF auf dieser Seite ansehen

1. Nehmen Sie den mittleren Drehpunkt
2. Vertauschen Sie die kleine Zahl links und die große Zahl rechts in der Reihenfolge von außen
3. Ändern Sie den Scanbereich von Minimum zu Pivot und bringen Sie den Pivot in die Mitte Sie können sehen, dass sich das wiederholt.

In diesem Programm jedoch p = a[-1] As, den Drehpunkt auf die letzte Zahl bringen Und l = [x for x in a[:-1] if x <= p] r = [x for x in a[:-1] if x > p] Also habe ich es in eine Zahl unterteilt, die größer als der Pivot und eine Zahl kleiner als der Pivot ist, und sie mit "return" (Aufruf der Wiederholungsfunktion) verbunden.

Der Erste if len(a) in (0, 1): return a Gibt zurück, wenn die Anzahl der Zeichen eins oder weniger beträgt, wird sie als Rückgabewert der rekursiven Funktion zurückgegeben.

Rückverfolgung

Versuchen Sie auf der Grundlage der obigen Angaben, die oben angegebene Zufallszahl zu ermitteln

#Ausgabe_____________________
[3, 7, 1, 6, 9, 8, 2, 10, 4]
[3, 1, 2]
[1]
[3]
[7, 6, 9, 8, 10]
[7, 6, 9, 8]
[7, 6]
[]
[7]
[9]
[]
>>[1, 2, 3, 4, 6, 7, 8, 9, 10]

Sequenz [3, 7, 1, 6, 9, 8, 2, 10, 4] Pivot p = 4 Kleines Array l = {3,1,2} Großes Array r = {7,6,9,8,10} Und zerlegen

Beleben Sie die kleine Sequenz wieder, p=2 l={1}、r={3} Und Demontage Jeder wurde zerlegt, also bestätigen Sie

Wenn Sie die große Sequenz neu starten, ist diese Zeit p das Maximum bei 10, also l={7,6,9,8} 、r={} Ist zerlegt Dann unterteilen Sie alle Zahlen Wird als kombinierte Daten zurückgegeben Es ist.

schließlich

Diesmal war es fast rund, aber mir wurde klar, dass ich es nicht verstand. Es war wirklich schön, eine solche Gelegenheit zu haben.