浅尝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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

BZOJ2783: [JLOI2012]树(树上前缀和+set)

Description 数列 提交文件:sequence.pas/c/cpp 输入文件:sequence.in 输出文件:sequence.out 问题描述:...

2744
来自专栏Spring相关

Css权重解析

关于CSS权重,我们需要一套计算公式来去计算,这个就是 CSS Specificity,我们称为CSS 特性或称非凡性,它是一个衡量CSS值优先级的一个标准 具...

842
来自专栏HTML5学堂

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

3285
来自专栏青玉伏案

算法与数据结构(四) 图的物理存储结构与深搜、广搜(Swift版)

开门见山,本篇博客就介绍图相关的东西。图其实就是树结构的升级版。上篇博客我们聊了树的一种,在后边的博客中我们还会介绍其他类型的树,比如红黑树,B树等等,以及这些...

16310
来自专栏磐创AI技术团队的专栏

Tensorflow从入门到精通(二):附代码实战

1.Tensor介绍 Tensor(张量)是Tensorflow中最重要的数据结构,用来表示Tensorflow程序中的所有数据。Tensor本是广泛应用在物...

2827
来自专栏Small Code

MATLAB 矩阵分块函数 mat2cell 及 cellfun 函数

为了清理桌面上的 words, so do this! 在做一个项目的时候,接触到了这个函数,瞬间感觉好有用,遂记录之。(好像有点废话……) mat2cell ...

3006
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

47114
来自专栏贾志刚-OpenCV学堂

TensorFlow中的feed与fetch

TensorFlow中的feed与fetch 一:占位符(placeholder)与feed 当我们构建一个模型的时候,有时候我们需要在运行时候输入一些初始数...

4007
来自专栏ml

错排公式

错排公式 百科名片 pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题: n个有...

3719
来自专栏King_3的技术专栏

leetcode-896-单调数列

如果对于所有 i <= j,A[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <= j,A[i]> = A[j],那么数组 A 是单调递...

1083

扫码关注云+社区