schnell Sortieren, Rekursion python
Dies ist mein quick sort code, der partition
- Funktion funktioniert gut, aber ich habe ein problem beim Aufruf der Rekursion. Die pos
ändert sich jedes mal, wenn es startet die Funktion und dann die Liste Grenzen werden sich ebenso ändern. Wie um das zu beheben?
def partition(lst, start, end):
pos=0
if len(lst)<2:
return
for i in range(len(lst[start:end])):
if lst[i] < lst[end]:
lst[i],lst[pos]=lst[pos],lst[i]
pos+=1
elif i==(len(lst[start:end])-1):
lst[end],lst[pos]=lst[pos],lst[end]
return pos
def quick_sort_recursive(lst, start, end):
pos=partition(lst, start, end)
if start<=pos<=end :
quick_sort_recursive(lst, start, pos-1)
quick_sort_recursive(lst, pos+1, end)
else:
return lst
Du musst angemeldet sein, um einen Kommentar abzugeben.
Gibt es zahlreiche Probleme in Ihrem code, hier sind einige Updates nur zu machen, damit es funktioniert:
Beispiel:
Gibt:
Ich denke, in einem reinen rekursive Implementierung der partition aux-Funktion nicht benötigt wird:
Triviales Beispiel Quick-Sort-Algorithmus:
*
*