python 算法 排序实现快速排序
python 算法 排序实现快速排序
发布时间:2016-12-28 来源:查字典编辑
摘要:QUICKSORT(A,p,r)是快速排序的子程序,调用划分程序对数组进行划分,然后递归地调用QUICKSORT(A,p,r),以完成快速排...

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学习
热门python学习
脚本专栏子分类