python 算法 排序实现快速排序
发布时间:2022-09-04 03:20:17
标签:python,快速排序
QUICKSORT(A, p, r)是快速排序的子程序,调用划分程序对数组进行划分,然后递归地调用QUICKSORT(A, p, r),以完成快速排序的过程。快速排序的最差时间复杂度为O(n2),平时时间复杂度为O(nlgn)。最差时间复杂度的情况为数组基本有序的时候,平均时间复杂度为数组的数值分布较为平均的时候。在平时情况下快速排序跟堆排序的时间复杂度都为O(nlgn),但是快速排序的常数项较小,所以要优于堆排序。
PARTITION(A, p, r)
x ← A[r]
i ← p - 1
for j ← p to r - 1
do if A[j] ≤ x
then i ← i + 1
swap(A[i], A[j])
swap(A[i + 1], A[r])
return i + 1
QUICKSORT(A, p, r)
if p < r
then q ← PARTITION(A, p, r)
QUICKSORT(A, p, q - 1)
QUICKSORT(A, q + 1, r)
实现:
#!/usr/bin/python
import sys
def partion(array, p, r):
x = array[r]
i = p - 1
for j in range(p, r):
if (array[j] < x):
i+=1
array[j], array[i] = array[i], array[j]
i+=1
array[i], array[r] = array[r], array[i]
return i
def quick_sort(array, p, r):
if p < r:
q = partion(array, p, r)
quick_sort(array, p, q - 1)
quick_sort(array, q + 1, r)
if __name__ == "__main__":
array = [1, 3, 5, 23, 64, 7, 23, 6, 34, 98, 100, 9]
quick_sort(array, 0, len(array) - 1)
for a in array:
sys.stdout.write("%d " % a)
0
投稿
猜你喜欢
- 一、使用 print() 函数在 Python 中,print() 函数支持格式化输出,与 C 语言的 printf 类似。1. 格式化输出
- 1、存储过程基本语法: create procedure sp_name() begin ...... end; 2、如何调用: call
- 位运算,赋值状态时异或对应位数1的整形,判断状态则与运算对应位数1的整形。最大用处就是同时判断32位状态,节省存储空间,便于扩展, 
- 大家都知道,数据库的安全性是很重要的,它直接影响到数据库的广泛应用。用户可以采用任意一种方法来保护数据库应用程序,也可以将几种方法结合起来使
- 如下所示: m_start =date +' 09:00' m_end =date +' 13:00'rsv
- 一 描述561. 数组拆分 I - 力扣(LeetCode) (leetcode-cn.com)给定长度为 2n 的整数
- 1. 引言今天来给小伙伴推荐两款实用的便于调试Python代码的工具,可以方便展示我们调试代码的中间状态,提升大家的编码效率。2. 动机在日
- Java一直标榜一句老话叫“编写一次,到处运行(Write Once,Run Anywhere)”,CSS也差一点点做到了。但就是为了差的一
- 在SQL Server 2008里安装审计,步骤如下:1. 给每个SQL Server 2008具体实例创建一个SQL Server审计2.
- 02条件语句和while循环三目运算a = 6#原判断语句if a > 5:print(True)else:print(False)#
- 介绍godep是解决包依赖的管理工具,目前最主流的一种,原理是扫描记录版本控制的信息,并在go命令前加壳来做到依赖管理godep 建议在 g
- 很长时间以来,一直想将自己的一些零碎的想法总结下,给自己一个完整的思维,也算是做个存档。一家之言,绝不敢说对别人会有什么帮助,对外人的层面上
- 拼音类文件py_class.php源码如下:<?php class py_class{ function py_class(){
- 理论Python中不存在真正的私有方法。为了实现类似于c++中私有方法,可以在类的方法或属性前加一个“_”单下划线,意味着该方法或属性不应该
- 脚本主要功能:1)通过zabbix api接口采集所有监控主机ip地址;2)通过cmdb系统(蓝鲸)接口采集所有生产主机IP地址、主机名、操
- asp使用fso对象遍历目录及目录下的文件代码:<%@ Language=VBScript %><%&
- 阅读上一篇:W3C优质网页小贴士(三)明智地选择 URI没有什么比走到你最喜欢的商店门口,却发现店门紧闭,而且没有看见店面搬迁告示这种事情还
- 如果原来没有使用过正则表达式,那么可能对这个术语和概念会不太熟悉。不过,它们并不是您想象的那么新奇。请回想一下在硬盘上是如何查找文件的。您肯
- 代码如下:'返回某年总共有多少天 Function DayOfYear(ByVal y) DayOfYear = DatePart(
- 相信为数不少的系统管理员每天都在做着同一样的工作——对数据进行备份。一旦哪一天疏忽了,而这一天系统又恰恰发生了故障,需要进行数据