十大排序算法(四)--- 快速排序 快速排序算法视频
yuyutoo 2024-10-12 01:09 4 浏览 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解释器执行一下,会输出如下结果:
可以看到,排序正确。
相关推荐
- 国内外注塑机及电脑密码大全(常见注塑机通用密码)
-
一、国外注塑机(日本、德国等)东洋注塑机万能码:9422345日精注塑机密码:222|7777DAMEG注塑机密码:000000000新泻注塑机密码:241650|261450住友注塑机密码:...
- 并发编程实战来咯(并发编程的艺术和并发编程实战)
-
提到并发编程,就不得不提C++ConcurrencyinAction(SecondEdition)(《C++并发编程实战第2版》)啦!《C++并发编程实战第2版》英文原版&中文译版看到这个...
- 无锁队列Disruptor原理解析(无锁队列应用场景)
-
队列比较队列...
- 无锁CAS(附无锁队列的实现)(cas是一种无锁算法)
-
本文所有代码对应的Github链接为:https://github.com/dongyusheng/csdn-code/tree/master/cas_queue...
- Linux高性能服务器设计(linux 服务器性能)
-
C10K和C10M计算机领域的很多技术都是需求推动的,上世纪90年代,由于互联网的飞速发展,网络服务器无法支撑快速增长的用户规模。1999年,DanKegel提出了著名的C10问题:一台服务器上同时...
- 浅谈Go语言的并发控制(go语言 并发)
-
前言本文原创,著作权归...
- Datenlord |Etcd 客户端缓存实践(etcd 数据存储)
-
简介和背景...
- 无锁编程——从CPU缓存一致性讲到内存模型
-
缓存是一个非常常用的工程优化手段,其核心在于提升数据访问的效率。缓存思想基于局部性原理,这个原理包括时间局部性和空间局部性两部分:...
- 如何利用CAS技术实现无锁队列(cas会锁总线吗)
-
linux服务器开发相关视频解析:...
- Kotlin协程之一文看懂Channel管道
-
概述Channel类似于Java的BlockingQueue阻塞队列,不同之处在于Channel提供了挂起的send()和receive()方法。另外,通道Channel可以...
- 详解C++高性能无锁队列的原理与实现
-
1.无锁队列原理1.1.队列操作模型...
你 发表评论:
欢迎- 一周热门
-
-
前端面试: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)