Python实现的快速排序

今天看了下《算法新解》这本书,很薄的一本书,最开始吸引我的有两点,一个是里面的大量的图,内容相对来说比较清新,第二个是里面的代码是基于Python实现。尽管算法和语言的关联实现差别不是很大,重在思想,我是希望直接一些,能看到最直接的就懒得转换了。

看这本书的时候有几个瞬间突然有顿悟的感觉。

第一个是一般的翻译书的内容背景很难转换,老外举的例子我们很多时候没有代入感。在这里我找到了一些共同的语言,作者看起来是在硅谷工作,举的一个旅行家问题是以旧金山,帕罗奥图,伯克利来说明,一看到这个例子,我就能很快想起之前去那边的行程安排,地图我已经研究得很熟了,所以再看到这个例子完全不会陌生,还多了一些亲切感。这可能就是一些额外的知识补充给带给我的福利吧。

第二个是对于数据结构设计上和算法的密切相关,让我突然理解了数据库中的设计方式。如果说原来是明白了5分,现在是打通了原来的一道壁垒,我能够真正的接受那种设计方式。

第三个是对于算法的设计,排除了我原来的一些盲点。大学看的算法书都很严谨,严谨到很多时候看不懂,越是关键的算法,觉得自己花费的脑细胞越多,但是感觉还是不得要领,今天在这里找到了一些灵感,大概2个多小时的时间,竟然看完了1/3的内容。

算法是程序员的一大利器,做一件事情实现的方式有很多,但是如何平衡找到最合适的方法却很难。记得大学看一个算法,花了好几个小时,结果上课的时候,老师花了不到五分钟就讲完了,然后脑袋一片空白,记得当时学快速排序的时候,感觉这个算法应该是很复杂,感觉理解了,但是很快就忘记了。如果要落到纸面上完全不行。

第四个是对递归的理解。今天看了之后算是刷新自己的认知。里面有句话说的好:递归将人分为三个截然不同的阵营,恨它的,爱它的,和恨了几年又爱上它的。我确切的说也是属于第三种。

使用循环,程序的性能可能而更好,但是使用递归,程序更容易理解。

对于快速排序,算法的思考方式就是由简到难。

如果是一个数,则返回,如果是两个数,直接比较很快就能出结果,我们用雇一个通用思维来考虑,设定一个参考值,如果大于参考值,则在右侧由数组存放,如果小于参考值,则在左侧存放。这样一来,三个数,四个数都是如此的思路。我们就可以使用递归来处理了。

能执行的程序很短,内容如下:

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        less = [i for i in array[1:] if i<= pivot]
        greater = [i for i in array[1:] if i > pivot]
        return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([5,11,3,5,8,2,6,7])

如果给程序打上日志,简单补充几个print来看看每个节点的执行情况:

def quicksort(array):
    if len(array) < 2:
        return array
    else:
        pivot = array[0]
        print("pivot:",pivot)
        less = [i for i in array[1:] if i<= pivot]
        print("less:",less)
        greater = [i for i in array[1:] if i > pivot]
        print("greater",greater)
        print("sum:",(less) + [pivot] + (greater))
        return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([5,11,3,5,8,2,6,7])

生成的日志如下:

D:\programs\python2.7\python.exe C:/python/kmp/db_ops/quicksort.py
('pivot:', 5)
('less:', [3, 5, 2])
('greater', [11, 8, 6, 7])
('sum:', [3, 5, 2, 5, 11, 8, 6, 7])
('pivot:', 3)
('less:', [2])
('greater', [5])
('sum:', [2, 3, 5])
('pivot:', 11)
('less:', [8, 6, 7])
('greater', [])
('sum:', [8, 6, 7, 11])
('pivot:', 8)
('less:', [6, 7])
('greater', [])
('sum:', [6, 7, 8])
('pivot:', 6)
('less:', [])
('greater', [7])
('sum:', [6, 7])
[2, 3, 5, 5, 6, 7, 8, 11]

Process finished with exit code 0

对于分析问题还是大有帮助。程序本身不长,算是我见过最精炼的快排程序了。

原文发布于微信公众号 - 杨建荣的学习笔记(jianrong-notes)

原文发表时间:2018-01-28

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CVer

7 月编程语言指数榜:Python力压Java夺冠

PYPL官方发布7月编程语言指数榜,Python以5.5%的高速上涨趋势力压Java夺得榜首。在此后五名是:Javascript、PHP、C#、C/C++和R。

18430
来自专栏Sorrower的专栏

算法怎么玩(一): 从直男到渣男

20520
来自专栏韩伟的专栏

你真的理解数码技术吗?(一)

第1章 以数字为语言 知识,是人类得以进化到地球生物链顶端的最重要武器。 在远古的地球上,人类为了捕猎动物聚在一起,通过各种奇奇怪怪的大呼小叫和指手画脚来商量战...

29540
来自专栏华章科技

PYPL 指数榜:Python 超越 Java 并逐渐拉开差距

此外,JavaScript 和 PHP 在季军位置的争夺上也十分激烈。二者在上半年的指数得分上十分接近,不过本月由于 PHP 出现了 1.5 个百分点的下降,地...

10120
来自专栏企鹅号快讯

零基础入门Python,值得推荐的几本书籍!

于我个人而言,我很喜欢Python,当然我也有很多的理由推荐你去学Python我只说两点.一是简单,二是写Python薪资高.我觉得这俩理由就够了,对不对.买本...

288100
来自专栏java一日一条

为什么程序员总是写糟糕的代码?这3个原因

我一下子想到的最明显的原因是,有好的程序员,也有不那么好的程序员,有的人技术水平高,有的人水平却低,有人对这门技艺感兴趣,但也有的人却不愿意在工作之外学习其他。

7530
来自专栏闵开慧

给程序入门者的一点建议

Java自学之道(一) 给程序入门者的一点建议     在书场上看到很多有关Java的书籍,但这就像进了瓜地里挑瓜挑的眼花,很多人不知道自己到底该选那本书好。很...

31860
来自专栏blackheart的专栏

[程序设计语言]-01:引言

1.机器语言>汇编语言>高级语言 语言是人与人的一种交流工具,就比如我现在用汉语来写这篇博文来交流探讨技术问题;程序设计语言也是如此,只是交流对象不是人而是机器...

18760
来自专栏编程

C语言编程怎么培养编程思维?没思路?我来带你找自己的思路

编程思维,可以说是一种感觉吧。培养编程思维,就是培养自己解决问题的能力,这种感觉可以帮助你更快找到问题点,对症下药。 1.要【会学】C语言 跟着老师或者自学学完...

38250
来自专栏Java学习网

为什么程序员总是写糟糕的代码?这3个原因

我最近一直在想我们作为一个行业为什么总是产出糟糕代码的原因。 1.明显原因…… 我一下子想到的最明显的原因是,有好的程序员,也有不那么好的程序员,有的人技术水平...

36160

扫码关注云+社区

领取腾讯云代金券