QUICKSORT(A, p, r)是快速排序的子程序,调用划分程序对数组进行划分,然后递归地调用QUICKSORT(A, p, r),以完成快速排序的过程,
python 算法 排序实现快速排序
。快速排序的最差时间复杂度为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)
您可能感兴趣的文章:
python计数排序和基数排序算法实例
python实现排序算法
python算法学习之计数排序实例
python算法学习之基数排序实例
python算法学习之桶排序算法实例(分块排序)
python冒泡排序算法的实现代码
python选择排序算法的实现代码
python插入排序算法的实现代码
python快速排序代码实例
python实现的各种排序算法代码
python 实现堆排序算法代码
python 实现归并排序算法
python 快速排序代码
python3.0 字典key排序
Python学习笔记_数据排序方法
QQ空间 搜狐微博 人人网 开心网 百度搜藏更多
Tags:python 快速排序
复制链接收藏本文打印本文关闭本文返回首页
上一篇:python操作MySQL数据库的方法分享
下一篇:windows下wxPython开发环境安装与配置方法
相关文章
2014-06-06Python实例分享:快速查找出被挂马的文件
2014-06-06pycharm 使用心得(四)显示行号
2014-06-06Python对两个有序列表进行合并和排序的例子
2006-09-09Python入门教程 超详细1小时学会Python
2014-03-03python基础教程之元组操作使用详解
2014-04-04sqlalchemy对象转dict的示例
2014-04-04Python和php通信乱码问题解决方法
2009-03-03wxpython 学习笔记 第一天
2014-02-02使用python在校内发人人网状态(人人网看状态)
2014-06-06解决windows下Sublime Text 2 运行 PyQt 不显示的方法分享
文章评论
最 近 更 新
python 实现堆排序算法代码
linux系统使用python监测系统负载脚本分享
python线程池的实现实例
win7安装python生成随机数代码分享
Python Web框架Pylons中使用MongoDB的例子
Python设计模式之单例模式实例
Python 错误和异常小结
python实现猜数字游戏(无重复数字)示例分
Python的print用法示例
python抓取京东商城手机列表url实例代码
热 点 排 行
Python入门教程 超详细1小时学会
python 中文乱码问题深入分析
比较详细Python正则表达式操作指
Python字符串的encode与decode研
Python open读写文件实现脚本
Python enumerate遍历数组示例应
Python 深入理解yield
Python+Django在windows下的开发
python 文件和路径操作函数小结
python 字符串split的用法分享