• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

快速排序-模拟堆栈

Python admin 7个月前 (03-11) 512次浏览 0个评论 扫描二维码
这题也是博主最近面试中遇到的一题,这个面试大厂还是要好好刷题的,面试过程写了 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]

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


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明快速排序-模拟堆栈
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!