快速排序的四种python实现（推荐）-6ren

快速排序的四种python实现（推荐）

转载作者：qq735679552 更新时间：2022-09-28 22:32:09

27

4

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章快速排序的四种python实现（推荐）由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

快速排序算法，简称快排，是最实用的排序算法，没有之一，各大语言标准库的排序函数也基本都是基于快排实现的.

本文用python语言介绍四种不同的快排实现.

1. 一行代码实现的简洁版本。

 
    ? 
   
 
     
       
       
         quick_sort  
         = 
         lambda 
         array: array  
         if 
         len 
         (array) < 
         = 
         1 
         else 
         quick_sort([item  
         for 
         item  
         in 
         array[ 
         1 
         :]  
         if 
         item < 
         = 
         array[ 
         0 
         ]])  
         + 
         [array[ 
         0 
         ]]  
         + 
         quick_sort([item  
         for 
         item  
         in 
         array[ 
         1 
         :]  
         if 
         item > array[ 
         0 
         ]]) 
        
 
     
 
   

2. 网上常见的快排实现。

 
    ? 
   
         def 
         quick_sort(array, left, right): 
        
         if 
         left > 
         = 
         right: 
        
         return 
        
         low  
         = 
         left 
        
         high  
         = 
         right 
        
         key  
         = 
         array[low] 
        
         while 
         left < right: 
        
         while 
         left < right  
         and 
         array[right] > key: 
        
         right  
         - 
         = 
         1 
        
         array[left]  
         = 
         array[right] 
        
         while 
         left < right  
         and 
         array[left] < 
         = 
         key: 
        
         left  
         + 
         = 
         1 
        
         array[right]  
         = 
         array[left] 
        
         array[right]  
         = 
         key 
        
         quick_sort(array, low, left  
         - 
         1 
         ) 
        
         quick_sort(array, left  
         + 
         1 
         , high)

由于快排是原地排序，因此不需要返回array.

array如果是个列表的话，可以通过len(array)求得长度，但是后边递归调用的时候必须使用分片，而分片执行的原列表的复制操作，这样就达不到原地排序的目的了，所以还是要传上边界和下边界的.

3.《算法导论》中的快排程序。

 
    ? 
   
         def 
         quick_sort(array, l, r): 
        
         if 
         l < r: 
        
         q  
         = 
         partition(array, l, r) 
        
         quick_sort(array, l, q  
         - 
         1 
         ) 
        
         quick_sort(array, q  
         + 
         1 
         , r) 
        
         def 
         partition(array, l, r): 
        
         x  
         = 
         array[r] 
        
         i  
         = 
         l  
         - 
         1 
        
         for 
         j  
         in 
         range 
         (l, r): 
        
         if 
         array[j] < 
         = 
         x: 
        
         i  
         + 
         = 
         1 
        
         array[i], array[j]  
         = 
         array[j], array[i] 
        
         array[i  
         + 
         1 
         ], array[r]  
         = 
         array[r], array[i 
         + 
         1 
         ] 
        
         return 
         i  
         + 
         1

这个版本跟上个版本的不同在于分片过程不同，只用了一层循环，并且一趟就完成分片，相比之下代码要简洁的多了.

4. 用栈实现非递归的快排程序。

先说两句题外话，一般意义上的栈有两层含义，一层是后进先出的数据结构栈，一层是指函数的内存栈，归根结底，函数的内存栈的结构就是一个后进先出的栈。汇编代码中，调用一个函数的时候，修改的也是堆栈指针寄存器ESP，该寄存器保存的是函数局部栈的栈顶，另外一个寄存器EBP保存的是栈底。不知道与栈存储空间相对的堆存储空间，其组织结构是否也是一个完全二叉树呢?

高级语言将递归转换为迭代，用的也是栈，需要考虑两个问题

1）栈里边保存什么?

2）迭代结束的条件是什么?

栈里边保存的当然是需要迭代的函数参数，结束条件也是跟需要迭代的参数有关。对于快速排序来说，迭代的参数是数组的上边界low和下边界high，迭代结束的条件是low == high.

 
    ? 
   
         def 
         quick_sort(array, l, r): 
        
         if 
         l > 
         = 
         r: 
        
         return 
        
         stack  
         = 
         [] 
        
         stack.append(l) 
        
         stack.append(r) 
        
         while 
         stack: 
        
         low  
         = 
         stack.pop( 
         0 
         ) 
        
         high  
         = 
         stack.pop( 
         0 
         ) 
        
         if 
         high  
         - 
         low < 
         = 
         0 
         : 
        
         continue 
        
         x  
         = 
         array[high] 
        
         i  
         = 
         low  
         - 
         1 
        
         for 
         j  
         in 
         range 
         (low, high): 
        
         if 
         array[j] < 
         = 
         x: 
        
         i  
         + 
         = 
         1 
        
         array[i], array[j]  
         = 
         array[j], array[i] 
        
         array[i  
         + 
         1 
         ], array[high]  
         = 
         array[high], array[i  
         + 
         1 
         ] 
        
         stack.extend([low, i, i  
         + 
         2 
         , high])

另外，当数组下标为-1时，C++、Java等语言中会报错，但python中访问的是最后一个元素，所以如果程序写错了，可能其他语言会报错，但python会输出一个错误的结果.

以上所述是小编给大家介绍的python实现快速排序算法详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我网站的支持！。

原文链接：https://blog.csdn.net/razor87/article/details/71155518 。

最后此篇关于快速排序的四种python实现（推荐）的文章就讲到这里了,如果你想了解更多关于快速排序的四种python实现（推荐）的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

27

4

0

文章推荐： Python零基础入门学习之输入与输出

文章推荐： python实现股票历史数据可视化分析案例

文章推荐： Python如何识别银行卡卡号?

文章推荐：搞定这套Python爬虫面试题(面试会so easy)

apache-spark - pyspark ml 推荐 - Als 推荐
嗨，我是 Spark 的新手，我正在尝试使用 ML 推荐。我的代码 df = sqlContext.createDataFrame( [(0, 0, 4.0), (0, 1, 2.0), (1,
JavaScript动画库...推荐
按照目前的情况，这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持，但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开，visit the
推荐！十个平台工程工具助力开发人员提升效率和体验
平台工程是为软件开发人员创建高效生态系统的过程，帮助他们自主执行软件开发生命周期的端到端操作。平台工程旨在减少开发人员的整体认知负荷并消除流程中的瓶颈，让开发团队的体验更佳。平台工程工具通过改善开发
Ubuntu解决火狐浏览器无法同步书签的问题【推荐】
最近在ubuntu系统中使用自带的firefox浏览器，发现有写问题，比如登陆后，书签，历史记录等，原本在windows下同步的数据无法同步，添加书签的功能也无法使用。经过查询资料后得知，unb
采用React编写小程序的Remax框架的编译流程解析(推荐)
Remax是蚂蚁开源的一个用React来开发小程序的框架，采用运行时无语法限制的方案。整体研究下来主要分为三大部分：运行时原理、模板渲染原理、编译流程；看了下现有大部分文章主要集中在Reamx的运行
Linux下双网卡Firewalld的配置流程(推荐)
实验室拟态存储的项目需要通过lvs-nat模式通过lvs服务器来区隔内外网的服务，所以安全防护的重心则落在了lvs服务器之上。笔者最终选择通过firewalld放行端口的方式来实现需求，由于fire
推荐！数据可视化的十种优秀JavaScript图表库
如今，随着我们身体各类数据的指数级增长，人们需要接受的信息量越来越大，系统必须处理的难度也是越来越高。而这些正是我们需要通过交互式图表和仪表盘，来实现数据可视化的根本原因。在大幅节省用户的时间和精力
linux下vsftpd的安装及配置使用详细步骤(推荐)
vsftpd 是“very secure FTP daemon”的缩写，安全性是它的一个最大的特点。 vsftpd 是一个 UNIX 类操作系统上运行的服务器的名字，它可以运行在诸如 Linux、
C语言实现常用字符串库函数(推荐)
1、实现memcpy 将src所指向的内容拷贝到dst所指向的位置，拷贝len个字节。 memcpy是内存拷贝函数 memcpy在使用的时候不用考虑类型，以字节为单位进行拷贝
Centos7安装配置NFS服务和挂载教程(推荐)
现在有3台服务器 s1(主)，s2(从), s3（从）需要实现文件实时同步，我们可以安装Nfs服务端和客户端来实现！ 1、安装 NFS 服务器所需的软件包：
在JavaScript中查找字符串中最长单词的三种方法(推荐)
本文基于Free Code Camp基本算法脚本“查找字符串中最长的单词”。在此算法中，我们要查看每个单词并计算每个单词中有多少个字母。然后，比较计数以确定哪个单词的字符最多，并返回最长单词的长
Java中的IO流总结(推荐)
I/O简介 I/O是Input/output的缩写，在java中，对于数据的输入和输出以流的方式进行。java.io包下提供了各种“流”类和接口，用以获取不同种类的数据，并通过标准的方法输入或输出
docker容器源码部署httpd用存储卷部署网站(推荐)
目录 docker容器源码部署httpd，用存储卷部署网站创建一个httpd镜像部署nfs 挂载创建容器并映射
Python地理地图可视化folium标记点弹窗设置代码(推荐)
python代码如下： import webbrowser as wbimport foliumif __name__ == '__main__': loc = [30.679943, 104.0
介绍一款python类型检查工具pyright(推荐)
近日，微软在 Github 上开源了一个 Python 静态类型检查工具：pyright ，引起了社区内的多方关注。微软在开源项目上的参与力度是越来越大了，不说收购 Github 这种大的战略野
Linux线程退出方式总结(推荐)
在编写多线程代码时，经常面临线程安全退出的问题。一般情况下，选择检查标志位的方式：在线程的while循环中，执行完例程后，都对标志位进行检查，如果标志位指示继续执行则再次执行例程，如果标志
盘点Python加密解密模块hashlib的7种加密算法(推荐)
前言在程序中我们经常可以看到有很多的加密算法，比如说MD5 sha1等，今天我们就来了解下这下加密算法的吧，在了解之前我们需要知道一个模块嘛就是hashlib，他就是目前Python一个提供字符
Java中泛型总结(推荐)
java 泛型（generics）是 jdk 5 中引入的一个新特性, 泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。泛型的本质是参数化类型，也就是说所操作的数据类型
在Python中合并字典模块ChainMap的隐藏坑【推荐】
在Python中，当我们有两个字典需要合并的时候，可以使用字典的 update 方法，例如： a = {'a': 1, 'b': 2} b = {'x': 3, 'y': 4}
python模拟菜刀反弹shell绕过限制【推荐】
有的时候我们在获取到目标电脑时候如果对方电脑又python 编译环境时可以利用python 反弹shell 主要用到python os库和sokect库这里的服务端在目标机上运行

首页

博学

6Ren·AI

商城

快速排序的四种python实现（推荐）