Python天天美味(30) - python数据结构与算法之快速排序

快速排序的原理是将取出第一个数,将整个数组分为两波,一拨都大于这个数,另一波都小于这个数,然后递归用同样的方法处理第一波数字和第二波数字。都说是“快速排序”,效率肯定比其他的一般排序算法高,下面我们就来验证一把,比较一下所谓的“快速排序”和“冒泡排序”的性能差异。

1. 快速排序

def quicksort(data, low = 0, high = None):     if high == None:         high = len(data) - 1     if low < high:         s, i, j = data[low], low, high         while i < j:             while i < j and data[j] >= s:                 j = j - 1             if i < j:                 data[i] = data[j]                 i = i + 1             while i < j and data[i] <= s:                 i = i + 1             if i < j:                 data[j] = data[i]                 j = j - 1         data[i] = s         quicksort(data, low, i - 1)         quicksort(data, i + 1, high)

2. 冒泡排序

def bubblesort(data):     for i in range(len(data) - 1, 0, -1):         for j in range(0, i):             if data[j] > data[j + 1]:                 data[j], data[j + 1] = data[j + 1], data[j]

 

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 = [random.randint(0, 65536) for i in range(2000)] #print data sort_perfmon(quicksort, data) sort_perfmon(bubblesort, data)

 

4. 结果

通过对随机的2000个数字进行排序,下面的结果可非常容易的看出,快速排序的优势是非常大的。

quicksort 0:00:00.062000 bubblesort 0:00:03.563000

 

  1. 代码下载

http://files.cnblogs.com/coderzh/Code/sorttest.rar 

 

 

Python 天天美味系列(总)

Python 天天美味(28) - urlopen    

Python 天天美味(29) - 调用VC++的动态链接库(DLL) 

Python 天天美味(30) - python数据结构与算法之快速排序 

Python 天天美味(31) - python数据结构与算法之插入排序 

Python 天天美味(32) - python数据结构与算法之堆排序 

[温馨提示]:该文章由原博客园导入而来,如排版效果不佳,请移步:http://www.cnblogs.com/coderzh/archive/2008/09/20/1294947.html

微信扫一扫交流

作者:CoderZh
微信关注:hacker-thinking (一个程序员的思考)
本文出处:https://blog.coderzh.com/2008/09/20/1294947/
文章版权归本人所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。