Python八大常见排序算法定义、实现及时间消耗效率分析
本文实例讲述了Python八大常见排序算法定义、实现及时间消耗效率分析。分享给大家供大家参考，具体如下：
昨晚上开始总结了一下常见的几种排序算法，由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的，这里的目的是为了更加完整详尽的总结一下这些排序算法，为了复习基础的东西，从冒泡排序、直接插入排序、选择排序、归并排序、希尔排序、桶排序、堆排序。快速排序入手来分析和实现，在最后也给出来了简单的时间统计，重在原理、算法基础，其他的次之，这些东西的熟练掌握不算是对之后的工作或者接下来的准备面试都是很有帮助的，算法重在理解内在含义和理论基础，在实现的时候才能避开陷阱少出错误，这不是说练习的时候有错误不好而是说，有些不该出现的错误尽量还是少出现的好，毕竟好的编程习惯是离不开严格的约束的，好了，这里就不多说了，复习一下基础知识，共同学习吧，下面是具体实现，注释应该都很详细，就不解释了：
#!usr/bin/envpython
#encoding:utf-8
'''''
__Author__:沂水寒城
功能：八大排序算法
'''
importtime
importrandom
time_dict={}
deftime_deco(sort_func):
'''''
时间计算的装饰器函数,可用于计算函数执行时间
'''
defwrapper(num_list):
start_time=time.time()
res=sort_func(num_list)
end_time=time.time()
time_dict[str(sort_func)]=(end_time-start_time)*1000
print'耗时为：',(end_time-start_time)*1000
print'结果为：',res
returnwrapper
defrandom_nums_generator(max_value=1000,total_nums=20):
'''''
随机数列表生成器
一些常用函数：
random随机数生成
random.random()用于生成一个0到1之间的随机数:0<=n<1.0；
random.uniform(a,b)，用于生成一个指定范围内的随机符点数，两个参数其中一个是上限，一个是下限。min(a,b)<=n<=max(a,b)；
randdom.randint(a,b),用于生成一个指定范围内的整数，其中a是下限，b是上限：a<=n<=b；
random.randrange(start,stop,step),从指定范围内，按指定基数递增的集合获取一个随机数；
random.choice(sequence),从序列中获取一个随机元素；
random.shuffle(x),用于将一个列表中的元素打乱；
random.sample(sequence,k),从指定序列中随机获取指定长度的片断；
'''
num_list=[]
foriinrange(total_nums):
num_list.append(random.randint(0,max_value))
returnnum_list
#@time_deco
defBubble_sort(num_list):
'''''
冒泡排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
'''
foriinrange(len(num_list)):
forjinrange(i,len(num_list)):
ifnum_list[i]>num_list[j]:#这里是升序排序
num_list[i],num_list[j]=num_list[j],num_list[i]
returnnum_list
#@time_deco
defInsert_sort(num_list):
'''''
直接插入排序，时间复杂度O(n^2)，空间复杂度O(1)，是稳定排序
'''
foriinrange(len(num_list)):
forjinrange(0,i):
ifnum_list[i]0:
i=0
whilei=0:
ift>=new_list[k]:
new_list.insert(k+1,t)
break
k=k-step
ifk<0:
new_list.insert(0,t)
#print'---------本轮结果为：--------'
#printnew_list
j=j+step
#printj
i=i+1
#printi
step=step/2#希尔排序是一个更新步长的算法
returnnew_list
#@time_deco
defTong_sort(num_list):
'''''
桶排序，时间复杂度O(1)，空间复杂度与最大数字有关，可以认为是O(n)，典型的空间换时间的做法
'''
original_list=[]
total_num=max(num_list)#获取桶的个数
foriinrange(total_num+1):#要注意这里需要的数组元素个数总数比total_num数多一个因为下标从0开始
original_list.append(0)
fornuminnum_list:
original_list[num]+=1
result_list=[]
forjinrange(len(original_list)):
iforiginal_list[j]!=0:
forhinrange(0,original_list[j]):
result_list.append(j)
returnresult_list
defQuick_sort(num_list):
'''''
快速排序，时间复杂度：O(nlog₂n)，空间复杂度：O(nlog₂n)，不是稳定排序
'''
iflen(num_list)<2:
returnnum_list
left_list=[]#存放比基准结点小的元素
right_list=[]#存放比基准元素大的元素
base_node=num_list.pop(0)#在这里采用pop()方法的原因就是需要移除这个基准结点，并且赋值给base_node这个变量
#在这里不能使用del()方法，因为删除之后无法再赋值给其他变量使用，导致最终数据缺失
#快排每轮可以确定一个元素的位置，之后递归地对两边的元素进行排序
forone_numinnum_list:
ifone_numnum_list[max_temp]:
max_temp=left_child
ifright_childnum_list[max_temp]:
max_temp=right_child
ifmax_temp!=i:
num_list[i],num_list[max_temp]=num_list[max_temp],num_list[i]
Heap_adjust(num_list,max_temp,size)#避免调整之后以max为父节点的子树不是堆
defCreate_heap(num_list,size):
a=size/2-1
foriinrange(a,-1,-1):
#print'**********',i
Heap_adjust(num_list,i,size)
#@time_deco
defHeap_sort(num_list):
'''''
堆排序，时间复杂度：O(nlog₂n)，空间复杂度：O(1)，不是稳定排序
'''
size=len(num_list)
Create_heap(num_list,size)
i=size-1
whilei>0:
num_list[0],num_list[i]=num_list[i],num_list[0]
size-=1
i-=1
Heap_adjust(num_list,0,size)
returnnum_list
if__name__=='__main__':
num_list=random_nums_generator(max_value=100,total_nums=50)
print'Bubble_sort',Bubble_sort(num_list)
print'Insert_sort',Insert_sort(num_list)
print'Select_sort',Select_sort(num_list)
print'Merge_sort',Merge_sort(num_list)
print'Shell_sort',Shell_sort(num_list)
print'Tong_sort',Tong_sort(num_list)
print'Heap_sort',Heap_sort(num_list)
print'Quick_sort',Quick_sort(num_list)
#print'-----------------------------------------------------------------------------'
#fork,vintime_dict.items():
#printk,v
结果如下：
Bubble_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
Insert_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
Select_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
Merge_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
Shell_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
Tong_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
Heap_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
Quick_sort[34,49,63,67,71,72,75,120,128,181,185,191,202,217,241,257,259,260,289,293,295,304,311,326,362,396,401,419,423,456,525,570,618,651,701,711,717,718,752,774,813,816,845,885,894,900,918,954,976,998]
这里没有使用到装饰器，主要自己对这个装饰器不太了解，在快速排序的时候报错了，也没有去解决，这里简单贴一下一个测试样例使用装饰器的结果吧：
Bubble_sort耗时为：0.0290870666504
结果为：[5,45,46,63,81,83,89,89,89,90]
None
Insert_sort耗时为：0.0209808349609
结果为：[5,45,46,63,81,83,89,89,89,90]
None
Select_sort耗时为：0.0259876251221
结果为：[5,45,46,63,81,83,89,89,89,90]
None
Merge_sort耗时为：0.0138282775879
结果为：[5,45,46,63,81,83,89,89,89,90]
None
Shell_sort耗时为：0.113964080811
结果为：[5,45,46,63,81,83,89,89,89,90]
None
Tong_sort耗时为：0.0460147857666
结果为：[5,45,46,63,81,83,89,89,89,90]
None
Heap_sort耗时为：0.046968460083
结果为：[5,45,46,63,81,83,89,89,89,90]
None
Quick_sort[5,45,46,63,81,83,89,89,89,90]
-----------------------------------------------------------------------------
0.113964080811
0.0259876251221
0.0209808349609
0.046968460083
0.0138282775879
0.0460147857666
0.0290870666504
接下来有时间的话我想学一下装饰器的东西，感觉对于模式化的东西装饰器简直就是一个神器，但是得明白会用会写才行哈！
PS：这里再为大家推荐一款关于排序的演示工具供大家参考：
在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys
更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》
希望本文所述对大家Python程序设计有所帮助。