Python快速排序算法实例分析
作者:qlshine 发布时间:2021-10-23 09:14:37
标签:Python,快速排序,算法
本文实例讲述了Python快速排序算法。分享给大家供大家参考,具体如下:
快速排序的时间复杂度是O(NlogN)
算法描述:
① 先从序列中取出一个数作为基准数
② 分区过程, 将比这个数大的数全部放到它的右边, 小于或等于它的数全部放到它的左边
③ 再对左右区间重复第二步, 直到各区间只有一个数
假设对 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 进行排序, 首先在这个序列中随便找一个基准数(用来参照), 比如选择 6 为基准数, 接下来把所有比基准数大的数放在6的右边, 比6小的数放在左边
原理分析:
① 选择最左边的数为基准数key
② 设立两个游标 low 和 high , 分别指向数组的最低位和最高位
③ 然后high先动, 如果high位上的数比key大, 则向前走, 如果high-1位上的数比key大, 继续向前走, 直到该位上的数<=key
④ 此时比较low位, 如果<=key, low向后走, 变为low+1, 依次类推, 直到该位上的数比key大
⑤ 交换high和low位上的数
⑥ 重复以上步骤, 直到low=high , 交换 key 和 high 位上的值
⑦ 最后进行递归操作
示例代码:
#!/usr/bin/env python
# coding:utf-8
# 设置最低位和最高位
def quickSort(nums, low, high):
# 设置一个比较基准key
key = nums[low]
while low<high:
# 如果最高位的数 大于等于 key则向前走
while low<high and nums[high] >= key:
high -= 1
# 如果最低位的数 小于等于 key则向后走
while low<high and nums[low] <= key:
low += 1
# 交换值
nums[low], nums[high] = nums[high], nums[low]
#最后low=high, 此时交换key和high位上的值, 使小于key的值在key左边, 大的在key右边
nums[nums.index(key)], nums[low] = nums[low], nums[nums.index(key)]
# 返回最低位的位置
return low
# 进行重复操作
def interval(nums, low, high):
if low<high:
# 进行排序并得到最低位位置以循环操作
key_index = quickSort(nums, low, high)
interval(nums, low, key_index)
interval(nums, key_index+1, high)
nums = [64,3,9,2,4,7,0,12,45,]
interval(nums, 0, len(nums)-1)
print "脚本之家测试结果:"
print nums
"""
[0, 2, 3, 4, 7, 9, 12, 45, 64]
"""
运行结果:
PS:关于排序算法的详细说明还可参考本站在线工具:
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具
http://tools.jb51.net/aideddesign/paixu_ys
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/qlshine/p/6032111.html
0
投稿
猜你喜欢
- 前言本文用Python实例阐述了一些关于进程、线程和协程的概念,由于水平有限,难免出现错漏,敬请批评改正。前提条件熟悉Python基本语法熟
- 下面我们以论坛排行榜举例说明:<% @ LANGUAGE="VBSCRIPT" %&
- 和YSlow一样,“Page Speed”也是一个基于firebug附加组件的FireFox插件。虽然听起来有点拗口,但是意思很容易理解:如
- 除了第一年外,谷歌每年母亲节都会更换主页的logo以向全世界的母亲致敬。虽然2000年和2001年母亲节的logo图片看起来没什么不同,但是
- 运算符重载意味着赋予超出其预定义的操作含义的扩展含义。例如运算符 + 用于添加两个整数以及连接两个字符串和合并两个列表。这是可以实现的,因为
- 1. 把数字转换成字符串,应用"" + 1,虽然看起来比较丑一点,但事实上这个效率是最高的,性能上来说:("&
- INSTR (源字符串, 目标字符串, 起始位置, 匹配序号) 在Oracle/PLSQL中,instr函数返回要截取的字符串在源字符串中的
- 前言写过 CLI 常驻进程的老司机肯定遇到过这么一个问题:在需要更新程序的时候,我要怎样才能安全关闭老进程?你可能会想到 NGIN
- 前因后果公司有人阳了,今天在家上班,突然小姨子就问我有没有baidu文库会员,想下载点东西,我心想这还要会员?用Python不是分分钟的事情
- 本文实例讲述了php利用cookies实现购物车的方法。分享给大家供大家参考。具体分析如下:php购物车是在电子商务网站会用到的,一种像超市
- hanxiaolian 为了躲避 lake2 ASP站长管理助手而写.. 一.绕过lake2 Asp木马扫描的小马 代码如下:<%&n
- 静态页面由于其稳定性快速性,的确给SE、用户及站长带来了方便。但有时,需要记住用户的信息,如用户留下评论后,下一次再来,就要记住该用户的信息
- 作为 Web 设计者,我们希望实现鹤立鸡群的设计,要做到这一点,要开阔眼界。欧美同东方的 Web 设计很不同,因为属于不同的文化。韩国不仅为
- 一、调用百度接口进行人脸属性识别安装好baidu-aip模块,获取了百度AI接口密钥后,即可调用百度接口进行人脸属性识别了。首先以杨紫的图片
- 相关代码:JavaScript写的日期时间控件,很好用 13个超酷的js显示时间效果 <html><head><
- 一、代码注释介绍注释就是对代码的解释和说明,其目的是让人们能够更加轻松地了解代码。注释是编写程序时,写程序的人给一个语句、程序段、函数等的解
- 以前写过《 10条影响CSS渲染速度的写法与建议》,今天放些数据出来,供参考;首先说明一点,CSS对网页的最后渲染出来的速度影响非
- digo工具地址:https://github.com/werbenhu/digo特性使用注释中的注解自动代码生成自动检测循环依赖编译时期依
- 本文实例讲述了Python只用40行代码编写的计算器。分享给大家供大家参考,具体如下:效果图:代码:from tkinter import
- PyType_Type和PyBaseObject_TypePyObject和PyTypeObject内容的最后指出下图中对实例对象和类型对象