主要还是学习使用栈模拟实现递归：

# -*- coding: utf-8 -*-

def partition(arr,low,high):

# 这时另外一种考虑方式，而且他是不需要额外空间的，他只使用一个指针来区分小于基准和大于基准的

# pointer_less_than代表这个指针的左边全部都是小于基准的（包括自己，不包括首元素）

# 然后从左往右扫描，遇到小于基准的元素，就把小于基准元素区域的后面紧接着的一个元素和他交换

# 那么小于基准元素区域就多了一个元素，。。。就这样小于基准的元素就连在了一起

# 首元素是基准元素，小于基准元素区域块，大于基准元素区域块，现在分成了三个部分

# 把首元素和小于基准元素区域块最后一个元素交换，那三部分就变成，小于的，基准，大于的

# 刚开始小于基准的元素为0，暂且指向首位值

pointer_less_than = low

# 然后一次扫描后面所有元素

for i in range(pointer_less_than +1,high+1):

# 遇到小于基准的，就把小于基准元素区域的后面紧接着的一个元素和他交换，小于的块相当于也更新了

if arr[i] < arr[low] :

pointer_less_than +=1

arr[pointer_less_than],arr[i]=arr[i],arr[pointer_less_than]

# 把首元素和小于基准元素区域块最后一个元素交换，那三部分就变成，小于的，基准，大于的

arr[low],arr[pointer_less_than] = arr[pointer_less_than],arr[low]

return pointer_less_than

class guide:

def __init__(self,left =None,right =None):

self.left =left

self.right =right

def quick_sort(arr):

stack =[guide(0,len(arr)-1),]

while stack:

pointer = stack.pop()

index = partition(arr,pointer.left,pointer.right)

if index+1 <= pointer.right:

stack.append(guide(index+1,pointer.right))

if pointer.left <= index-1:

stack.append(guide(pointer.left,index-1))

arr = [7,9,6,5,4,8,3,1]

print(arr)

quick_sort(arr)

print(arr)

runfile('D:/share/test/stack_recursion.py',wdir='D:/share/test')

[7,1]

[1,7,9]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!