这题也是博主最近面试中遇到的一题,这个面试大厂还是要好好刷题的,面试过程写了native版本,但是也要学会这一点
# -*- coding: utf-8 -*- # @Time : 2019/3/11 下午3:22 # @Author : zhusimaji # @File : qsort_by_for.py # @Software: PyCharm def qsort(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=vpartion(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 vpartion(arr,l,r): data=arr[l] while l<r: while r>l and arr[r]>=data: r=r-1 arr[l]=arr[r] while l<r and arr[l]<=data: l=l+1 arr[r]=arr[l] arr[l]=data return l if __name__ == '__main__': a = [1, 54, 3, 56, 24, 6, 234] qsort(a) print(a)
在上面的代码中 vpartion的函数就是不断的计算对应的切分点,然后将对应的切分点索引返回,让后在qsort函数中实现栈的操作,在native 快速排序中递归的操作就是堆栈的操作,如果递归的层数超级多会出现栈溢出的问题,因此可以通过这种方式不使用递归来进行
下面给出上面例子中的堆栈中索引变化的过程:
[6, 0] [6, 1] [3, 1, 6, 5] [3, 1]
直到堆栈之中所有数据为空的时候,此时也完成了数据的排序。