一行Python代码搞定快速排序算法

上次文章分析了 Python 算法中的冒泡排序,Python 中常见的排序算法有:冒泡排序、快速排序、插入排序、选择排序、归并排序、堆排序、二叉树排序。

今天给大家分析下 Python 算法中的快速排序。

快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

运行环境

语言:Python3
编辑器:Pycharm

代码分析

先用常规的方式来完成快速排序,采用的思路是:分而治之加递归。

步骤

1、分而治之:任意选取一个数据(通常选用数组的第一个数,上面动态图选的最后一个)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。

2、经过第一步,将一个列表拆分成了 2 个列表,利用递归函数,继续调用函数本身,直到列表里的元素个数在 1 个(包括)以下则停止递归,否则继续递归递归排序下去,代码如下(左右滑动可查看全部代码)

为了让小白们更好的理解,我们来把每次递归后小的值、中间值、大的值打印出来。也就是打印比列表中 array[0] 小的值、array[0]、比 array[0] 大的值,就是下面代码中标黄的部分,代码如下:

上面代码中加了三个 print() 函数,我们来看下这三个 print() 打印出来的结果。

为了看得更清楚,每三个打印结果后我手动加了空格。原列表 array 在以第一个元素 9 为基准的情况下,比 9 小的数字 8 移动到 左边,其他大的继续在右边。

接下来判断条件元素个数小于 2 的停止递归,所以 [8] 停止递归,[11, 88, 32] 则继续第二次递归。

以第一个值 11 为基准,比 11 小的没有,为空列表,比 11 大的 88 和 32 组成新的列表。接下来对符合递归条件的 [88, 32] 进行第三次递归。

以第一个 88 为基准,比它小的 32 移动到左边,比它大的没有,为空。至此,没有符合递归条件的元素列表了,递归全部结束,把产生的新列表全部拼接加起来就是开头的结果。

递归函数之前文章有单独讲过,不明白的可以戳 零基础学 Python 之递归函数 查看。

好了,以上的内容理解后,我们再来看看 Python 怎么把快速排序算法优化成一行代码呢?

一行代码搞定

都说 Python 以简洁著称,今天借助匿名函数就可以把快速排序的功能优化成一行代码了。话不多说,直接上代码。

只要理解了上面的递归函数,再理解下匿名函数就能理解这一行代码的功能了。匿名函数之前也有文章分析过的,没上车的同学戳  Python匿名函数详解  查看。

上面一行代码直接给出你要排序的列表并打印就可以实现排序的功能。

打印结果和上面一致。

好了,今天的内容结束了,不知道你掌握了多少,欢迎留言讨论。

 

文章为pk哥原创,我在我的公众号: Python 知识圈 上会分享更多心得体会,你也可以关注。

***版权申明:本文为 Python知识圈 pyzhishiquan.com 原创,没有Python知识圈书面授权,请勿以任何形式转载,摘编,复制或镜像。***

为您推荐

发表评论

电子邮件地址不会被公开。