Python天天美味(30) - python数据结构与算法之快速排序-阿里云开发者社区

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

2017-01-11 1450

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

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

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 )