《算法图解》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 条评论
登录 后参与评论

相关文章

来自专栏码匠的流水账

zuul自定义SimpleHostRoutingFilter

zuul的SimpleHostRoutingFilter主要用来转发不走eureka的proxy,里头是使用httpclient来转发请求的,但是有时候我们需要...

1272
来自专栏跟着阿笨一起玩NET

从sql server 中读取二进制图片

391
来自专栏大内老A

开发自己的Data Access Application Block[下篇]

上接:[原创] 我的ORM: 开发自己的Data Access Application Block - Part I 4. Database 下面来介绍重中之重...

2226
来自专栏自由而无用的灵魂的碎碎念

小项目分享---混色器

编写代码的同志们一般懂美术的就少了,偶也是,什么色轮、三维加色等等。虽然看过一些书籍(如内田广由纪的《配色基础原理》),不过还是一知半解的。

963
来自专栏Golang语言社区

GO语言 TCP传输实例

package main import ( "net" "fmt" ) var ( maxRead = 1100 msgStop = []byt...

3396
来自专栏c#开发者

about store RecordField submit emptystring issue

operate screenshot When click save button submit to change,trace store before...

3437
来自专栏王磊的博客

Net连接mysql的公共Helper类MySqlHelper.cs带MySql.Data.dll下载

MySqlHelper.cs代码如下: using System; using System.Collections.Generic; using System...

4399
来自专栏张善友的专栏

通过SmtpClient发送Exchange会议邮件

看到C#中调用Outlook API 发起会议 ,这个完全可以用SMTP方式实现的,下面我的项目中使用的代码: 对于.NET而言,从2.0开始,发邮件已经是一件...

1929
来自专栏菩提树下的杨过

Silverlight:利用异步加载Xap实现自定义loading效果

关键点: 1.利用WebClient的DownloadProgressChanged事件更新下载进度 2.下载完成后,分析Xap包的程序集Assembly信息 ...

18510
来自专栏我和未来有约会

Silverlight制作逐帧动画 v2 - part2

Silverlight制作逐帧动画 v2 - part2 在这里完善了一下算法,加入了fps的机制进去。 private string[] ...

1886

扫码关注云+社区