python快速排序的实现及运行时间比较

2023-08-08 11:20:04 73

快速排序的基本思想：首先选定一个数组中的一个初始值，将数组中比该值小的放在左边，比该值大的放在右边，然后分别对左边的数组进行如上的操作，对右边的数组进行如上的操作。（分治+递归）

1.利用匿名函数lambda

匿名函数的基本用法func_name =lambdax:array，冒号左边的x代表传入的参数，冒号右边的array代表返回值，当然名字是可以自己取的。

quick_sort=lambdaarray:\
arrayiflen(array)<=1\
elsequick_sort([itemforiteminarray[1:]ifitem<=array[0]])\
+[array[0]]+\
quick_sort([itemforiteminarray[1:]ifitem>array[0]])

2.将匿名函数拆解封装为函数

deffunc2(array):
iflen(array)<=1:
returnarray
tmp=array[0]
left=[xforxinarray[1:]ifx<=tmp]
right=[xforxinarray[1:]ifx>tmp]
returnfunc2(left)+[tmp]+func2(right)

3.网上常见的

deffunc2(array,left,right):
ifleft>=right:
return
low=left
high=right
tmp=array[low]
whilelefttmp:
right-=1
array[left]=array[right]
whileleft
4.算法导论里面的
deffunc3(array,l,r):
ifl
5.利用栈实现非递归版本
deffunc4(array,l,r):
ifl>=r:
return
stack=[]
stack.append(l)
stack.append(r)
whilestack:
low=stack.pop(0)
high=stack.pop(0)
ifhigh-low<=0:
continue
x=array[high]
i=low-1
forjinrange(low,high):
ifarray[j]<=x:
i+=1
array[i],array[j]=array[j],array[i]
array[i+1],array[high]=array[high],array[i+1]
stack.extend([low,i,i+2,high])
6.python内置的
sorted(array)
本来是想利用装饰器来测一下每个函数的运行时间的，但是由于快排里面存在递归，使用装饰器会报错，就只好一个个计算了。这里还是贴一下用装饰器计算时间的代码：
defcount_time(func):
@wraps(func)
defhelper(func,*args,**kwargs):
start=time()
result=func(*args,**kwargs)
end=time()
print("函数：",func.__name__,"运行时间：",round(end-start,4),"s")
returnresult
returnhelper
这里我们的输入是随机生成的在0-100间的整数，我们测试一下在不同数量下的消耗时间：
fromfunctoolsimportwraps
fromrandomimportrandint
fromtimeimporttime
func1_start=time()
res=quick_sort(array)
func1_end=time()
print("函数：func1运行时间：",round(func1_end-func1_start,4),"s")
func2_start=time()
func2(array)
func2_end=time()
print("函数：func2运行时间：",round(func2_end-func2_start,4),"s")
func3_start=time()
func3(array,0,len(array)-1)
func3_end=time()
print("函数：func3运行时间：",round(func3_end-func3_start,4),"s")
func4_start=time()
func4(array,0,len(array)-1)
func4_end=time()
print("函数：func4运行时间：",round(func4_end-func4_start,4),"s")
func5_start=time()
func5(array,0,len(array)-1)
func5_end=time()
print("函数：func5运行时间：",round(func5_end-func5_start,4),"s")
func6_start=time()
sorted(array)
func6_end=time()
print("函数：func6运行时间：",round(func6_end-func6_start,4),"s")
输入array的定义：
array=[randint(0,100)foriinrange(5000)]
需要注意的是，随着数据量的增加，方法4，也就是算法导论中的会出现以下问题：

 这是因为python中的递归深度是有一定限制的，可以使用如下方法暂时解决该问题：
importsys
sys.setrecursionlimit(100000)
同时，方法4还会出现内存溢出问题，方法4也太坑了。

 最后对比一下这些方法消耗的时间：



 总结：
方法一、方法二速度较快，同时也较好理解，想要学会快速排序，只要记住方法二即可；
python内置的排序速度还是最快的呀；
以上所述是小编给大家介绍的python快速排序的实现及运行时间比较，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！

如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

python快速排序的实现及运行时间比较

热门推荐

随机推荐