递归和非递归快速排序(Python实现)

递归和非递归快速排序(Python实现)

快速排序的原理是基于分治策略，设定一个基准线（pivot），将数据分为两部分，不断分治实现数据的排序

由实现原理容易得到递归代码如下：

def qsort(arr):
if not len(arr):
return []
else:
# 在这里以第一个元素为基准线
pivot = arr[0]
left = qsort([x for x in arr[1:] if x < pivot])
right = qsort([x for x in arr[1:] if x >= pivot])
return left+[pivot]+right

递归代码思路清晰易懂，也容易写出来，但性能相对较差，因为递归次数有限（递归的数据不断压入栈中，容易造成栈溢出）

非递归快排思路：
利用栈的思想，将需要继续排序的首尾下标存入栈中，不断弹栈进行分区操作

具体实现代码如下：

def quick_sort(arr):
'''''
模拟栈操作实现非递归的快速排序
'''
if len(arr) < 2:
return arr
stack = []
stack.append(len(arr)-1)
stack.append(0)
while stack:
l = stack.pop()
r = stack.pop()
index = partition(arr, l, r)
if l < index - 1:
stack.append(index - 1)
stack.append(l)
if r > index + 1:
stack.append(r)
stack.append(index + 1)
def partition(arr, start, end):
# 分区操作，返回基准线下标
pivot = arr[start]
while start < end:
while start < end and arr[end] >= pivot:
end -= 1
arr[start] = arr[end]
while start < end and arr[start] <= pivot:
start += 1
arr[end] = arr[start]
# 此时start = end
arr[start] = pivot
return start

如有错误，欢迎指正和交流~

最后

以上就是完美诺言为你收集整理的递归和非递归快速排序(Python实现)的全部内容，希望文章能够帮你解决递归和非递归快速排序(Python实现)所遇到的程序开发问题。

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