美文网首页Python学习日志《python算法基础》读书笔记
《python算法教程》Day9 - 快速排序法

《python算法教程》Day9 - 快速排序法

作者: billyang916 | 来源:发表于2018-04-20 00:16 被阅读20次

    这是《python算法教程》第9篇读书笔记,笔记的主要内容为快速排序法。

    快速排序法简介

    快速排序法运用分治法的方式,将需要排序的序列细分成小序列进行排序。
    思路如下:将序列划分为大于序列第一个值、小于序列第一元素的两个序列,以及用于作为比较基准的序列的第一个元素。之后递归调用上述思路,将拆分出来的两个序列分别按照上述思路进行拆分,直到需要排序的序列剩下一个元素。之后将拆分的序列组合起来。

    代码展示

    以下展示快速排序的两种代码方案。
    第一种是每次划分序列,均生成两个新的序列。
    第二种则是通过调换元素间的顺序,以使得用于对比的基准元素的左边的元素均小于基准元素,基准元素右边的元素大于基准元素。

    方案1

    #快速排序
    import numpy as np
    
    def partition(seq):
        lo=[x for x in seq if x<seq[0]]
        hi=[x for x in seq if x>seq[0]]
        return lo ,seq[0],hi
        
    def quickSort(seq):
        if len(seq)<=1:
            return seq
        lo,pi,hi=partition(seq)
        return quickSort(lo) + [pi] + quickSort(hi)
    
    #生成随机整数序列,用于测试排序算法
    seq=np.random.randint(0,100,100)
    print(seq)
    res=quickSort(seq)
    print(res)
    

    方案2

    #快速排序
    import numpy as np
    
    def quickSort(seq):
        if len(seq)<=1:
            return seq
        i=0
        j=len(seq)-1
        k=seq[0]
        while i<j:
            while i<j and k<=seq[j]:
                j-=1
            seq[i],seq[j]=seq[j],seq[i]
            while i<j and k>=seq[i]:
                i+=1
            seq[i],seq[j]=seq[j],seq[i]
        #print(seq[0:i],seq[i+1:len(seq)])
        return quickSort(seq[0:i]) +[k]+quickSort(seq[i+1:len(seq)])
    
    #生成随机整数序列,用于测试排序算法
    seq=[x for x in np.random.randint(0,100,50)]
    print(seq)
    res=quickSort(seq)
    print(res)
    

    我的博客即将搬运同步至腾讯云+社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=11flspuoq5iwm

    相关文章

      网友评论

        本文标题:《python算法教程》Day9 - 快速排序法

        本文链接:https://www.haomeiwen.com/subject/llagkftx.html