können wir diese Funktion eine schnelle Sortierung nennen

-1

Ich fand diese Funktion in Python geschrieben im Internet und ich bin verwirrt, wenn es eine schnelle Sortierung ist oder nicht, weil es in einer Zeile geschrieben ist und es sehr gut und schnell funktioniert und ich denke, dass es funktioniert mit der Komplexität von O (n * log n) selbst im schlimmsten Fall, so ist dies der Code:können wir diese Funktion eine schnelle Sortierung nennen

def qsort(L): 
    return (qsort([x for x in L[1:] if x < L[0]]) +\ 
      L[0:1] + \ 
      qsort([x for x in L[1:] if x >= L[0]])) if L else []

Quelle

2017-03-16 Adelov

Sieht aus wie ein Quicksort. – Carcigenicate

Brechen Sie diesen einen Liner in mehrere Zeilen auf, um einen Sinn daraus zu machen. Ein Liner nur um der Sache willen ist oft eine schlechte Idee, wenn er die Lesbarkeit behindert ... – Julien

Ja, es ist ein Quicksort. (Es verwendet weniger als optimalen Speicherplatz, aber es zählt immer noch.) – Ryan

Ja, es ist schnell Art, wie es perfekt ist, diesen Algorithmus Definition entsprechen: von der willkürliches Element abholen Liste, verschiebe Werte niedriger als dieses Element an den Anfang der Liste (vor dem ausgewählten Element) und führe eine schnelle rekursive Sortierung durch:

qsort([x for x in L[1:] if x < L[0]])

Ergebnis ist, leere Liste

größer oder gleich Werte an das Ende der Liste (nach dem ausgewählten Elemente) und führt eine schnelle Sortierung rekursiv

qsort([x for x in L[1:] if x >= L[0]])

, wenn die Liste leer ist (Rekursion Terminierung) dann natürlich ist.

Quelle

2017-03-17 17:18:54

Ich denke ja, aber wenn ich es teste ihre Geschwindigkeit Ich fand es besser als megeSort – Adelov

Soweit ich mich erinnere, während beide zusammenführen und schnelle Sortierung haben durchschnittliche Komplexität nlogn schnelle Sortierung führt besser, wenn es um typische zufällige Verteilungen kommt –

können wir diese Funktion eine schnelle Sortierung nennen

Antwort

Verwandte Themen