python 算法 排序实现快速排序

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

相关文章

通过5个知识点轻松搞定Python的作用域

1、块级作用域 想想此时运行下面的程序会有输出吗?执行会成功吗? #块级作用域 if 1 == 1: name = "lzl" print(name) for i...

Python 函数用法简单示例【定义、参数、返回值、函数嵌套】

Python 函数用法简单示例【定义、参数、返回值、函数嵌套】

本文实例讲述了Python 函数用法。分享给大家供大家参考,具体如下: demo.py(函数定义): # say_hello() # 不能在定义函数之前调用函数 # Python 解...

django 开发忘记密码通过邮箱找回功能示例

一、流程分析: 1.点击忘记密码====》forget.html页面,输入邮箱和验证码,发送验证链接网址的邮件====》发送成功,跳到send_success.html提示 2.到邮箱里...

Python的__builtin__模块中的一些要点知识

1.isinstance函数:除了以一个类型作为参数,还可以以一个类型元组作为参数。 isinstance(obj,basestring)===isinstance(obj,(str...

一篇文章弄懂Python中的可迭代对象、迭代器和生成器

一篇文章弄懂Python中的可迭代对象、迭代器和生成器

我们都知道,序列可以迭代。但是,你知道为什么吗? 本文来探讨一下迭代背后的原理。 序列可以迭代的原因:iter 函数。解释器需要迭代对象 x 时,会自动调用 iter(x)。内置的 it...