python 算法 排序实现快速排序

yipeiwu_com6年前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的Django框架加载模版的方式

一般说来,你会把模板以文件的方式存储在文件系统中,但是你也可以使用自定义的 template loaders 从其他来源加载模板。 Django有两种方法加载模板  &n...

python实现下载pop3邮件保存到本地

python实现下载pop3邮件保存到本地

利用python进行unix管理一书中有一个登陆下载邮箱的脚本,实练了下还不错,对于邮箱备份来说还是比较快捷的,但是其命名方式是以编号和 文件大小来命名的,不方便阅读,于是进行了改进修改...

Python脚本实现集群检测和管理功能

Python脚本实现集群检测和管理功能

场景是这样的:一个生产机房,会有很多的测试机器和生产机器(也就是30台左右吧),由于管理较为混乱导致了哪台机器有人用、哪台机器没人用都不清楚,从而产生了一个想法--利用一台机器来管理所有...

解决pyttsx3无法封装的问题

解决pyttsx3无法封装的问题

一、python3下面的pyttsx3正常可以使用,类似下面: import pyttsx3 engine = pyttsx3.init() rate = engine.getPro...

python实现360的字符显示界面

复制代码 代码如下:#!/usr/bin/python  #-*-coding:utf-8-*- from push_button import *from clabel im...