python快排递归非递归

• 递归形式如下:

alist = [3,1,2,9,0,7,4,8,5,6]
def quickSort(alist,start,end):
if start >= end:
return
index = start
privior = alist[index]
low = start
hight = end
#这个while跑完之后,alist[start]就是provior,start左边的都比privior小,右边的都比privior大
while low < hight:
#在高位找出一个比privior小的数字,必须先写高位hight,然后再写低位的low
while alist[hight] >= privior and low < hight :
hight = hight - 1
#在低位找出一个比privior大的数字
while alist[low] <= privior and low < hight :
low = low + 1
#两者交换
if low < hight:
temp = alist[low]
alist[low] = alist[hight]
alist[hight] = temp
alist[index] = alist[low]
alist[low] = privior
quickSort(alist,start,low)
quickSort(alist,low+1,end)
if __name__ == '__main__':
quickSort(alist,0,9)
astr = ''
for item in alist:
astr = astr + str(item)
astr = astr + ' '
print(astr)

• 非递归的形式如下:

alist = [3,1,2,9,0,7,4,8,5,6]
def qs(alist,start,end):
if start >= end:
return
indexList = []
indexList.append(start)
indexList.append(end)
#判断条件是栈非空
while len(indexList) > 0:
priviorIndex = indexList[0]
privior = alist[indexList[0]]
low = indexList[0]
hight = indexList[1]
while low < hight:
#必须先写右边的,没办法的.否则hight的值会被冲掉,这是代码的问题
while alist[hight] >= privior and low < hight:
hight = hight - 1
while alist[low] <= privior and low < hight:
low = low + 1
#满足交换条件
if low < hight:
temp = alist[low]
alist[low] = alist[hight]
alist[hight] = temp
alist[priviorIndex] = alist[low]
alist[low] = privior
#其实使用递归的时候,可见其保存的现场就是三个东西,alist,下一步快排的左边界,下一步快排的右边界,
# 我们只需要手工保存这几个现场,并且在必要的时候弹出栈即可,下面的两个if就是保存现场
if low > indexList[0]:
indexList.append(indexList[0])
indexList.append(low)
if hight < indexList[1]:
indexList.append(low + 1)
indexList.append(indexList[1])
#这里就是弹出栈的代码
indexList.pop(0)
indexList.pop(0)
if __name__ == '__main__':
qs(alist,0,9)
astr = ''
for item in alist:
astr = astr + str(item)
astr = astr + ' '
print(astr)

最后

以上就是故意荔枝为你收集整理的python快排递归非递归的全部内容，希望文章能够帮你解决python快排递归非递归所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。