python 算法排序实现快速排序 -电脑资料

电脑资料时间：2019-01-01 我要投稿

【www.unjs.com - 电脑资料】

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入门教程超详细1小时学会

python 中文乱码问题深入分析

比较详细Python正则表达式操作指

Python字符串的encode与decode研

Python open读写文件实现脚本

Python enumerate遍历数组示例应

Python 深入理解yield

Python+Django在windows下的开发

python 文件和路径操作函数小结

python 字符串split的用法分享

相关文章

python 算法 排序实现快速排序 -电脑资料