专栏首页python读书笔记《算法图解》NOTE 4 快速排序法1.递归与分治法2.快速排序法的实现3.快速排序法的时间复杂度(用渐近表示法表示)

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

这是《算法图解》的第四篇读书笔记,主要涉及快速排序法。

1.递归与分治法

快速排序法(quick sort)之所以有这个名称,源于其排序速度,相较于其他排序方式来说,较快。而其高排序效率,主要源于其使用了分治法(divide and conquer)的思路。 所谓分治法,即分而治之,将一个问题划分为几个子问题,而后解决子问题。当然,子问题可以再分解为几个子问题,直到子问题不能再划分时,解决不能再划分的子问题。若有需要,可以将子问题的答案合并,作为原问题的答案。请注意,解决问题的方法一直保持不变。 为什么上述的思路可行呢,简单来说,可用数学归纳法进行说明。 对与规模为n的原问题,需证明解决方案: 在问题规模为n时可行的时候: n=1(最小规模的问题)可行, 同时规模为n+1时仍可行。 具体的数学证明,请参考相关的资料。 分治法的思路是否和上一篇读书笔记所述的递归(recursion)相似呢。实,分治法是通过递归实现的。

2.快速排序法的实现

如上文所说,快速排序法应用了分治法的思想。其具体思路如下: 1.从原序列中选择一个数作为基础值 2.将原序列中的元素按照与基础值的大小比较结果,分为大于基础值、小于基础值两个序列:S1和S2. 3.将元素列按照S1、基础值和S2的顺序组合成一个新序列并将新序列返回。 4.分别将S1和S2重复步骤1、步骤2和步骤3。 5.重复步骤4,直到划分后的序列只有一个或零个元素,此时直接返回含有单个元素或0个元素的序列。 代码如下:

#演示快速排序法,排序结果以降序显示
def quick_sort(seq):
    #基线条件
    if len(seq)<2:
        return seq
    base_value=seq[0]
    less=[]
    large=[]
    #划分子序列
    for idx in range(1,len(seq)):
        if base_value>=seq[idx]:
            less.append(seq[idx])
        else:
            large.append(seq[idx])
    return quick_sort(large)+[base_value]+quick_sort(less)

seq=[10,15,12,18,15,1]
print(quick_sort(seq))

3.快速排序法的时间复杂度(用渐近表示法表示)

基于分治思想的快速排序法,其时间复杂度为n*log2 n 。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    这是《python算法教程》第9篇读书笔记,笔记的主要内容为快速排序法。 快速排序法简介 快速排序法运用分治法的方式,将需要排序的序列细分成小序列进行排序。 ...

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

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

    billyang916
  • 《python算法教程》Day4 - 拓扑排序(基于有向无环图)拓扑排序简介代码实例

    这是《python算法教程》的第4篇读书笔记。这篇笔记的主要内容为拓扑排序。 拓扑排序简介 在将一件事情分解为若干个小事情时,会发现小事情之间有完成的先后次序之...

    billyang916
  • scTrio-seq(逆向收费读文献2019-15)

    本次分享的文献发表于2018年11月30日,在Science 杂志,“Single-cell Multi-omics Sequencing and Analys...

    生信技能树
  • 【NLP】实践一个完整的数据挖掘项目

    大部分机器学习项目死在第1步和第2步,平时我们说的机器学习,指的是3、4、5这3步,实践中,其实最难的是业务理解这一步,业务理解OK了,后面的一切都有章可循。

    yuquanle
  • 采购免费OA系统的注意事项

    随着互联网的不断发展,信息化办公管理已日渐深入人心,免费OA办公系统的成熟稳定,功能齐全且人性化,操作简便等优点,帮助中小型企事业单位建设信息化管理,所以很多企...

    用户3865428
  • 计算机网络?(一)

    负责连接两条或以上传输线路的计算机。同时路由器也是一个网关,它在网络层交换数据包。

    gojam
  • 火爆的图机器学习,2020年将有哪些研究趋势?

    2019年绝对是图机器学习(GML)大火的一年,凡是学术会议,图神经网络的会场总会爆满。

    AI科技评论
  • foreach rf

    用户1359560
  • k8s镜像中心私有项目没法pull问题解决办法

    问天丶天问

扫码关注云+社区

领取腾讯云代金券