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

xiaoxiao2021-02-28  15

递归和非递归快速排序(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

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

转载请注明原文地址: https://www.6miu.com/read-2800137.html

最新回复(0)