快速排序-模拟堆栈

1,619次阅读
没有评论
这题也是博主最近面试中遇到的一题,这个面试大厂还是要好好刷题的,面试过程写了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]

直到堆栈之中所有数据为空的时候,此时也完成了数据的排序。

admin
版权声明:本站原创文章,由admin2019-03-11发表,共计798字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)