快速排序-模拟堆栈

2,445次阅读

这题也是博主最近面试中遇到的一题，这个面试大厂还是要好好刷题的，面试过程写了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 快速排序中递归的操作就是堆栈的操作，如果递归的层数超级多会出现栈溢出的问题，因此可以通过这种方式不使用递归来进行

下面给出上面例子中的堆栈中索引变化的过程：