十大排序算法(四)--- 快速排序 快速排序算法视频
yuyutoo 2024-10-12 01:09 5 浏览 0 评论
十大排序算法（四）--- 快速排序
快速排序算法采用的是分治法的思想(Divide and Conquer), 它把一个待排序的数组，以某个元素或者称为基准(这里记为PIVOT)为界，分为两个子数组，比PIVOT小的全部移到到PIVOT左边，比PIVOT大的全部移动到PIVOT右边。再分别对以PIVOT分开的两个子数组重复该过程，直到无法再分。
快速排序正常情况下时间复杂度为O(nlogn)。最坏情况下为O(n^2)。最坏情况发生在每次排序都需要移动所有剩下待排序的元素，这种情况虽然很少发生，但是为了避免这样的情况可以采用随机选择PIVOT元素的方法来预防。下面描述算法的实现步骤：
- 随机的从待排序数组中选择一个元素作为PIVOT
- 将所有比PIVOT小的数放到PIVOT的左边，比PIVOT大的数放到PIVOT的右边。跟PIVOT一样大的数，放到左右都可以。这个步骤称为Partition。这样以PVIOT为界分成了左右两个子数组。
- 对#2分成两个子数组递归进行#1~#3操作，直到排序完成。
假设我们要对A[5, 3, 6, 1, 2, 8]留个数进行排序，下图展示了排序的过程。
绝大多数情况下，快速排序是高效的，但是快速排序不是稳定的。下面是python的代码实现。有兴趣的同学，也可以用其它编程语言尝试实现一下。
import random
A = [5, 3, 6, 1, 2, 8]
def quick_sorting(data, left, right):
if left >= right : return
mark = random.randint(left, right)
data[left], data[mark] = data[mark], data[left]
mark = left
tmp = data[left]
for i in range(left+1, right+1):
if data[i] < tmp:
mark += 1
data[i], data[mark] = data[mark], data[i]
data[left], data[mark] = data[mark], data[left]
quick_sorting(data, left, mark-1)
quick_sorting(data, mark+1, right)
def main():
right=len(A)-1
left = 0
#Ascending
quick_sorting(A, left, right)
print(A)
if __name__=='__main__':
main()
将上面的代码保存到一个文本文件，后缀名修改为.py。可以用python解释器执行一下，会输出如下结果：
可以看到，排序正确。
相关推荐
- 国产RISC-V终端Sipeed Lichee Console4A上架，1699元起
-
IT之家12月11日消息，国内著名开源硬件厂商Sipeed矽速科技推出RISC-V终端LicheeConsole4A，售价1699元（不带LM4A模块）-3299元。Li...
- H3C交换机常用配置命令
-
1、配置主机名...
- ThinkPad老版Bios中英文对应详解
-
ThinkPad老版Bios中文对应详解。解决方案:...
- 澳大利亚Console Connect与非洲数据中心达成战略合作，增强整个非洲的数据连接
-
据techafricanews网11月13日报道，在2024年非洲科技节上，澳大利亚ConsoleConnect与非洲数据中心共同宣布了一项具有里程碑意义的战略合作协议，该协议致力于提升非洲大陆关键...
- 多功能调焦 腾龙TAP-in Console延期发售
-
最新消息传出，腾龙TAP-inConsole(modeltap-01)多功能调焦器由于生产方面原因原本预计3月24日发售延迟至3月30日，腾龙的这款调焦器功能类似于适马的USBDock调焦底座，...
- 关于交换机上存在的不同接口介绍(一)
-
生活中常见的电子设备有很多，其中明交换机主要起到的是连接的作用，上面有非常多的接口，下面就一起来看看这些不同的接口作用是什么。1、RJ-45接口这是我们见的最多、应用最广的一种接口类型，它属于双绞线以...
- 颜值更高?微软新推精英版Xbox One手柄
-
本月，微软的XboxOne升级了更强大的版本——XboxOneEliteconsole（精英版？），升级版的控制手柄功能更强大，可以主导你的客厅；从曝光的图片上看得出，新版XboxOneE...
- “全球首个”:Console Connect为全球物联网项目推出连接解决方案
-
据DevelopingTelecoms2月27日报道，在MWC2023上，全球网络即服务（NaaS）平台ConsoleConnect推出了“全球首个”私有连接解决方案，可帮助企业在全球范围内动态...
- 密码遗忘专题——Console口密码遗忘
-
如果忘记了Console口密码，用户可以通过以下两种方式来设置新的Console口密码：方法一：通过STelnet/Telnet登录设备修改Console口密码。...
- 为锐捷路由器交换机开启web和telnet，实现轻松管理
-
笔者上一篇文章写了关于锐捷二层交换机配置教程，那么接下来讲一下锐捷的路由交换设备配置web、telnet技巧。同样，今天的教程也是基于命令行，比较简单，适合新手小白进行学习。准备工作配置前准备：con...
- C# - 类文件构成,C#基本语法,Console属性与方法 007
-
类文件(.cs)构成类文件主要分为引用命名空间与自己项目的命名空间...
- Console OS系统帮你在PC上自由切换Windows和安卓应用
-
通过ConsoleOS你可以在你的PC上安装自己喜欢的安卓游戏，需要时之间切换回Windows进行其他工作，ConsoleOS能够完全利用你的PC硬件配置，该系统可以安装在PC的内置硬盘里，也可以...
- 交换机通过串口线console口登录设备
-
一、功能简介：PC端通过设备的Console口登录，实现对第一次上电的设备进行基本配置和管理。...
- (每日持续更新)jdk api之Console基础、应用、实战
-
博主18年的互联网软件开发经验，从一名程序员小白逐步成为了一名架构师，我想通过平台将经验分享给大家，因此博主每天会在各个大牛网站点赞量超高的博客等寻找该技术栈的资料结合自己的经验，晚上进行用心精简、整...
- KFC推出“真正的次世代主机”KFConsole!真4K/120帧
-
今天KFCGaming官方推特发布了一则“主机”宣传片，正式公布了旗下名为KFConsole的全新主机产品。并宣称：游戏的未来就在这里，介绍真正的次世代主机！根据官方介绍，本款KFC主机功能强大，支...
欢迎 你 发表评论:
- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了，如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
推荐7个模板代码和其他游戏源码下载的网址
-
其实模版网站在开发工作中很重要，推荐几个参考站给大家
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
【开源分享】2024PHP在线客服系统源码(搭建教程+终身使用)
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)