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)

相关文章

Django自定义manage命令实例代码

manage.py是在我们创建Django项目的时候就自动生成在根目录下的一个命令行工具,它可以执行一些简单的命令,其功能是将Django project放到sys.path目录中,同时...

python中的RSA加密与解密实例解析

这篇文章主要介绍了python RSA加密与解密实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 什么是RSA: RSA公开密...

Python中类的定义、继承及使用对象实例详解

本文实例讲述了Python中类的定义、继承及使用对象的方法。分享给大家供大家参考。具体分析如下: Python编程中类的概念可以比作是某种类型集合的描述,如“人类”可以被看作一个类,然后...

Python网页正文转换语音文件的操作方法

Python网页正文转换语音文件的操作方法

天气真的是越来越冷啦,有时候我们想翻看网页新闻,但是又冷的不想把手拿出来,移动鼠标翻看。这时候,是不是特别想电脑像讲故事一样,给我们念出来呢?人生苦短,我有python啊,试试用 Pyt...

Java实现的执行python脚本工具类示例【使用jython.jar】

本文实例讲述了Java实现的执行python脚本工具类。分享给大家供大家参考,具体如下: 这里java中执行python脚本工具类,需要使用jython.jar java中执行pytho...