专栏首页python读书笔记《python算法教程》Day9 - 快速排序法快速排序法简介代码展示

《python算法教程》Day9 - 快速排序法快速排序法简介代码展示

这是《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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

    billyang916
  • 《python算法教程》Day10 - 平面最近点对问题平面最小点对问题介绍代码演示

    今天是《python算法教程》的第10篇读书笔记。笔记的主要内容是使用python实现求最小点对的时间复杂度为O(nlogn)的算法。 平面最小点对问题介绍 在...

    billyang916
  • 《python算法教程》Day11 - 分治法求解平面凸包问题平面凸包问题简介分治法求解思路点与直线的位置判断代码示例

    这是《python算法教程》的第11篇读书笔记,笔记主要内容是使用分治法求解凸包。 平面凸包问题简介 在一个平面点集中,寻找点集最外层的点,由这些点所构成的凸多...

    billyang916
  • PHP数据结构(一)——顺序结构线性表

    PHP数据结构(一)——顺序结构线性表 (原创内容,转载请注明来源,谢谢) 线性表的要求:存在唯一的“第一个”元素与“最后一个”元素,每个元素最多一个前驱和一个...

    用户1327360
  • Linux 命令系列之 seq

    在搭建 Elasticsearch 集群时,需要设置多个数据目录,以提高磁盘吞吐量,使用 seq和mkdir 可以快速批量创建。

    叨叨软件测试
  • 技术栈小课堂:使用Linux seq命令生成数字序列!

    在Linux中生成数字列表的最简单方法之一是使用seq(序列)命令。seq以最简单的形式表示一个数字,然后列出从1到该数字的所有数字。例如:

    用户6543014
  • Linux 命令(113)—— seq 命令

    seq(Sequence) 命令用于按照指定步长产生从起始数到结束数之间的所有整数。起始数和步长可使用默认值 1,结束数必须指定。

    Dabelv
  • Python寻找给定序列中相差最小的两个数字

    import random def getTwoClosestElements(seq): #先进行排序,使得相邻元素最接近 #相差最小的元素必然相邻 ...

    Python小屋屋主
  • 单细胞RNA-seq的设计和方法(一)

    Bulk vs scRNA-seq.png Bulk RNA-seq : 它测定的是一个大的细胞群体中的每一个基因的平均表达水平。对比较转录组学、找疾病标志物、...

    生信技能树jimmy
  • 单细胞RNA-seq分析介绍

    在整个人体组织中,细胞类型、状态和相互作用是非常多种多样的,为了更好的了解这些组织和存在的细胞类型,我们需要更高分辨率的技术,而scRNA-seq提供了在单个细...

    生信技能树jimmy

扫码关注云+社区

领取腾讯云代金券