Python天天美味(30)
快速排序的原理是将取出第一个数，将整个数组分为两波，一拨都大于这个数，另一波都小于这个数，然后递归用同样的方法处理第一波数字和第二波数字。都说是“快速排序”，效率肯定比其他的一般排序算法高，下面我们就来验证一把，比较一下所谓的“快速排序”和“冒泡排序”的性能差异。1. 快速排序
def quicksort(data, low = 0, high = None):
if high == None:
high = len(data) - 1
if low < high:
s, i, j = data, low, high
while i < j:
while i < j and data >= s:
j = j - 1
if i < j:
data = data
i = i + 1
while i < j and datadata:
data, data = data, data
3. 性能比较
上面看来，冒泡排序只需要5行，够简洁的，但性能咋样呢？来比较一下吧：
import random
import datetime
import copy
def sort_perfmon(sortfunc, data):
sort_data = copy.deepcopy(data)
t1 = datetime.datetime.now()
sortfunc(sort_data)
t2 = datetime.datetime.now()
print sortfunc.__name__, t2 - t1
#print sort_data
data =
#print data
sort_perfmon(quicksort, data)
sort_perfmon(bubblesort, data)
4. 结果
通过对随机的2000个数字进行排序，下面的结果可非常容易的看出，快速排序的优势是非常大的。
quicksort 0:00:00.062000
bubblesort 0:00:03.563000
5. 代码下载
http://files.iyunv.com/coderzh/Code/sorttest.rar
Python 天天美味系列（总）
Python 天天美味(28) - urlopen
Python 天天美味(29) - 调用VC++的动态链接库(DLL)
Python 天天美味(30) - python数据结构与算法之快速排序
Python 天天美味(31) - python数据结构与算法之插入排序
Python 天天美味(32) - python数据结构与算法之堆排序
...
页:
[1]