专栏首页Python专栏浅尝Python快速排序

浅尝Python快速排序

wiki

什么是快速排序?

wiki百科的定义是:快速排序,又称划分交换排序,简称快排,一种排序算法。在平均状况下,排序n个项目

次比较。在最坏状况下则需要

次比较,但这种状况并不常见。事实上,快速排序通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上可以很有效率地达成。

步骤

快速排序步骤

快速排序使用分治法策略来把一个序列(list)分为两个子序列(sub-lists)。

  • 从数列中挑出一个元素,称为"基准"(pivot),
  • 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

举个?

比如有一个数组

96 69 1314 520 666

1. 选取一个基准数就是之前说的privot,一个比较大小的数。

一般都会取最后一个数,这里就取666为基准数,依次把数组的数和666比较,比666小的放左边,比666大的放右边,这样有如下结果:

96 69 520 666 1314

2. 判断区间个数,经过第1步后右边区间只有一个数了,没有数字再和它比较了,因此不需要重复操作,左边区间还有:

96 69 520

3. 重复第1步,选取520作为基准数,得到比较结果:

96 69 520

4. 重复第1步,选取69作为基准数,得到比较结果:

69 96

5. 这样左右两边区间都只有一个数了,这就标志着排序完成,最后把所有区间合并就得到排序结果:

69 96 520 666 1314

Code

上代码!

def quick_sort(lst):
    _less = [] # 存储小于基准数的值
    _greater = [] # 存储大于基准数的值
   # 递归函数一定要有退出条件
    if len(lst) <= 1:
        return lst
    # 基准数,直接获取src的最后一个
    _pivot = lst.pop()
    for _item in lst:
        if _item <= _pivot: 
            _less.append(_item)
        else: 
            _greater.append(_item)
    # 这里用到了python的list是可以直接相加的特性
   # 递归思想很重要,去处理列表中不止1个的
    return quick_sort(_less) + [_pivot] + quick_sort(_greater)

代码中采用了递归的做法,优化的地方也是有的,比如用生成器去优化列表的值获取。

l = [69, 96, 520, 666, 1314]
print(quick_sort(l))
[69, 96, 520, 666, 1314]

如果你对今天的内容还感兴趣的话,何不点个赞再走呢?

如果感兴趣到想赞赏我,就不要犹豫啦~


本文分享自微信公众号 - 猿媛牧场(xpchuiit)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-06-07

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • GitHub宕机24小时,我们还能干嘛

    不过我更喜欢下面这幅图,虽然我已经2年不用windows了,但是看到这个图还是很想笑啊,每次windows一个补丁,就能让你半天不用看屏幕了。

    用户1634449
  • python的生产者消费者模型,看这篇就够了

    用户1634449
  • 200行代码,一行行教你自制微信机器人

    1) 用一个windows客户端工具运营公众号,真的很局限。虽然工具的功能很强大,能自动添加好友,自动拉好友入群,关键字回复等等,但是有一个绕不开的点,它是一款...

    用户1634449
  • MFC自绘按钮的实现

    自绘按钮的实现过程 申明自绘属性 进行VM_MESUREITEM事件响应,说明按钮的尺寸 进行VM_DRAWITEM消息的重新响应,说明如何绘制按钮 首先在vc...

    cloudskyme
  • Hadoop基础环境配置

    这里如果自己配置了hostname,可以使用自己配置的hostname替换localhost,默认使用localhost,端口信息也可以自己指定为未使用的端口。

    JonyChiao
  • Macheine Learning Yearning学习笔记(三)

    Chapter 13、Build your first system quickly, then iterate(快速构建第一个系统,然后再一步步迭代)

    yuquanle
  • 历时25天,我的博客(www.ityouknow.com)终于又活了过来

    纯洁的微笑
  • ActiveMQ详解(2)——JMS基本概念

    张申傲
  • 用‘slay’干掉某个用户的所有进程

    Slay slay 是Chris Ausbrooks写的一款用于杀掉指定用户所有运行进程的命令行工具。slay对系统管理员而言在找出那些不应该运行进程的用户是...

    小小科
  • 为帝国cms模板添加站内搜索小教程

      由于客户的需要,最近都在整帝国cms,很多东西还是不熟悉,特别是帝国cms模板,以前用的那些网站模板一般是保存在ftp文件中,而帝国cms模板是直接保存在数...

    ytkah

扫码关注云+社区

领取腾讯云代金券