这是我的快速排序代码，partition 函数运行良好，但在调用递归时出现问题。 pos 每次启动函数时都会更改，然后列表限制也会更改。如何解决？
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
请您参考如下方法:
您的代码中存在许多问题，这里有一些修复以使其正常工作:
def partition(lst, start, end):
pos = start # condition was obsolete, loop won't
# simply run for empty range
for i in range(start, end): # i must be between start and end-1
if lst[i] < lst[end]: # in your version it always goes from 0
lst[i],lst[pos] = lst[pos],lst[i]
pos += 1
lst[pos],lst[end] = lst[end],lst[pos] # you forgot to put the pivot
# back in its place
return pos
def quick_sort_recursive(lst, start, end):
if start < end: # this is enough to end recursion
pos = partition(lst, start, end)
quick_sort_recursive(lst, start, pos - 1)
quick_sort_recursive(lst, pos + 1, end)
# you don't need to return the list
# it's modified in place
例子:
example = [3,45,1,2,34]
quick_sort_recursive(example, 0, len(example) - 1)
print example
给予:
python test.py
[1, 2, 3, 34, 45]
