快速排序的原理是基于分治策略，设定一个基准线（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如有错误，欢迎指正和交流~
