快速排序python递归 [英] quick sort python recursion
本文介绍了快速排序python递归的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
这是我的快速排序代码,partition
函数运行良好,但是在调用递归时遇到问题. pos
每次启动功能时都会更改,然后列表限制也将更改.该如何解决?
This is my quick sort code, the partition
function works well, but I got a problem while calling the recursion. The pos
changes every time it starts the function and then the list limits are change as well. How to fix that?
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
推荐答案
您的代码中存在许多问题,以下是一些修复程序,它们只是为了使其正常工作:
There are numerous problems in your code, here are some fixes just to make it work:
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
python test.py
[1、2、3、34、45]
[1, 2, 3, 34, 45]
这篇关于快速排序python递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文