python 算法 排序实现快速排序

yipeiwu_com5年前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)

相关文章

Python和GO语言实现的消息摘要算法示例

Python和GO语言实现的消息摘要算法示例

常用的消息摘要算法有MD5和SHA,这些算法在python和go的库中都有,需要时候调用下就OK了,这里总结下python和go的实现。 一、python消息摘要示例 代码如下: 复制代...

window7下的python2.7版本和python3.5版本的opencv-python安装过程

花费了整整2天的时间终于学会安装了opencv,换系统的心都有了,由于ubuntu实在不会玩,看来还是老老实实在windows下安装吧,以此作为记录方便以后安装 python2.7版本的...

Python和php通信乱码问题解决方法

即使在urlencode之前str.decode(“cp936″).encode(“utf-8″)做了编码转换也是没用的。后来查询手册查到一个urllib.quote()函数,用此方法成...

python获取指定路径下所有指定后缀文件的方法

本文实例讲述了python获取指定路径下所有指定后缀文件的方法。分享给大家供大家参考。具体实现方法如下: # 获取指定路径下所有指定后缀的文件 # dir 指定路径 # ext 指定...

OpenCV+python手势识别框架和实例讲解

OpenCV+python手势识别框架和实例讲解

基于OpenCV2.4.8和 python 2.7实现简单的手势识别。 以下为基本步骤 1.去除背景,提取手的轮廓 2. RGB->YUV,同时计算直方图 3.进行形态学滤波,提...