Unerwartetes Verhalten einer rekursiven Einfügesortierfunktion in Python

Question

Ich schrieb eine rekursive Einfügesortierfunktion in Python 2.7 und stieß auf zwei Dinge, die ich nicht verstehen kann.

Der erste war der Fehler TypeError: can only assign an iterable, die ich vermutete, es mit der Rekursion der Funktion zu tun hatte, aber ich habe nicht vor allem das Problem mit meinem Code:

def recursiveInsertionSort(v): 
    if len(v)!=2: 
     v[0:len(v)-1]=recursiveInsertionSort(v[0:len(v)-1]) 
    i=len(v)-1 
    while v[i-1]>v[i]: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 
     if i==0: return v 

Das zweite Problem ist es wahrscheinlich verbunden.

In diesem Fall habe ich nicht einmal einen Fehler bekommen (wenn Sie wissen, warum bitte sagen Sie mir), aber die Funktion hat einfach nicht funktioniert.

def recursiveInsertionSort(v): 
    if len(v)!=2: 
     recursiveInsertionSort(v[0:len(v)-1]) 
    i=len(v)-1 
    while v[i-1]>v[i] and i>0: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 

Als ich das Problem war mit der rekursiven Verwendung der Funktion erraten korrigierte ich meinen Fehler:

def recursiveInsertionSort(v): 
    if len(v)!=2: 
     temp=v[0:len(v)-1] 
     recursiveInsertionSort(temp) 
     v[0:len(v)-1]=temp 
    i=len(v)-1 
    while v[i-1]>v[i] and i>0: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 

Aber ich möchte wirklich die Ursachen dieser beiden Verhaltensweisen verstehen, können Sie mir helfen ?

EDIT Ich bitte auch, ob es eine schönere Art und Weise zu tun ist:

temp=v[0:len(v)-1] 
recursiveInsertionSort(temp) 
v[0:len(v)-1]=temp 

Answer 1

das Problem bei der ersten Implementierung war mit der if Anweisung innerhalb der Schleife. Wenn die Schleife beendet wurde, weil v[i-1] kleiner oder gleich v[i] war, würde es nicht return irgendetwas (was in Python ist das gleiche wie return None tun). Die TypeError, die Sie erhalten, stammt aus dem rekursiven Aufruf, der den None-Wert erhält, da None einem Segment nicht zugewiesen werden kann.

Sie können die erste Version des Codes Arbeit machen, wenn Sie die beiden Bedingungen in der while Anweisung kombinieren und das Rück v bedingungslos, nachdem die Schleife endet:

while i > 0 and v[i-1] > v[i]: 
    v[i-1], v[i] = v[i], v[i-1] 
    i -= 1 
return v 

Sie wahrscheinlich die Bedingungen in dieser Reihenfolge setzen sollte in deine andere Version auch.

Warum Ihre zweite Version nicht funktionierte, war das Problem, dass Sie die ursprüngliche Liste zerschnitten und eine neue Liste mit einer Teilkopie des Inhalts erstellt haben. Dann hat Ihre rekursive Sortierung diese Kopie an Ort und Stelle verändert. Aber dann hatte die äußere Funktion keine Möglichkeit, die Änderungen zu sehen, da sie keinen Verweis auf die geschnittene Kopie enthielt. Ihre dritte Version behebt dies, indem Sie das Slice explizit als neue Variable speichern.

Ich glaube nicht, dass es einen besseren Weg gibt, die genau drei Zeilen Ihres letzten Codeblocks zu machen. Wenn Sie jedoch die Funktion geändert, um einen optionalen paraemter des höchsten Index zu akzeptieren, zu sortieren, könnten Sie tun, ohne überhaupt zu schneiden:

def recursiveInsertionSort(v, i=None): 
    if i is None: 
     i = len(v) - 1 
    if i > 1: 
     recursiveInsertionSort(v, i-1) 
    while v[i-1]>v[i] and i>0: 
     v[i-1], v[i]=v[i], v[i-1] 
     i-=1 

Das wird ein wenig effizienter als Ihr aktueller Code sein, wie Die Liste wird nicht für jeden rekursiven Aufruf kopiert. Beide Versionen sind immer noch O(N**2), also erwarten Sie nicht, dass es mit quicksort oder anderen effizienteren Sortierungen auf großen Datensätzen konkurrieren.