# python--几种快速排序的实现以及运行时间比较

1.利用匿名函数lambda

```quick_sort = lambda array: \
array if len(array) <= 1 \
else quick_sort([item for item in array[1:] if item <= array[0]]) \
+ [array[0]] + \
quick_sort([item for item in array[1:] if item > array[0]])```

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

```def func2(array):
if len(array)<=1:
return array
tmp = array[0]
left = [x for x in array[1:] if x<=tmp]
right = [x for x in array[1:] if x>tmp]
return func2(left) + [tmp] + func2(right)```

3.网上常见的

```def func2(array,left,right):
if left>=right:
return
low=left
high=right
tmp=array[low]
while left<right:
while left<right and array[right]>tmp:
right-=1
array[left] = array[right]
while left<right and array[left]<=tmp:
left+=1
array[right]=array[left]
array[right]=tmp
func2(array,low,left-1)
func2(array,left+1,high)```

4.算法导论里面的

```def func3(array, l, r):
if l < r:
q = partition(array, l, r)
func3(array, l, q - 1)
func3(array, q + 1, r)

def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i + 1]
return i + 1```

5.利用栈实现非递归版本

```def func4(array, l, r):
if l >= r:
return
stack = []
stack.append(l)
stack.append(r)
while stack:
low = stack.pop(0)
high = stack.pop(0)
if high - low <= 0:
continue
x = array[high]
i = low - 1
for j in range(low, high):
if array[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)`

```def count_time(func):
@wraps(func)
def helper(func,*args,**kwargs):
start=time()
result = func(*args,**kwargs)
end=time()
print("函数：", func.__name__, "运行时间：", round(end - start, 4), "s")
return result
return helper```

```from functools import wraps
from random import randint
from time import time

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 = [randint(0,100) for i in range(5000)]`

```import sys
sys.setrecursionlimit(100000)```

• 方法一、方法二速度较快，同时也较好理解，想要学会快速排序，只要记住方法二即可；
• python内置的排序速度还是最快的呀；

0 条评论

• ### 【numpy】新版本中numpy（numpy>1.17.0）中的random模块

numpy是Python中经常要使用的一个库，而其中的random模块经常用来生成一些数组，本文接下来将介绍numpy中random模块的一些使用方法。

• ### golang之引用自己定义的包

其中main.go只有一个主函数main()，用于运行程序，array文件夹是自己定义的包，里面spArr.go位于package array。

• ### [PHP] 最简单的权限控制设计

假设url部分我们只有action和method , 某个控制器下的某个方法 , 比如:log/loginlog 查看日志下的登陆日志, action就是l...

• ### 浅谈PHP array_search 和 in_array 函数效率问题

在一个接口中，发现非常耗时，排查原因发现 array_search 查找数组中的元素的 key 时，效率随着数组变大，耗时增加。特别是大数组时，非常耗时。在函数...

• ### PHP实现二维数组（或多维数组）转换成一维数组的常见方法总结

本文实例总结了PHP实现二维数组（或多维数组）转换成一维数组的常见方法。分享给大家供大家参考，具体如下：

• ### 3分钟短文 | PHP数组获取最后一个元素，10个方式中哪个有错？

我们对于 PHP 的数组操作乐此不疲，为什么？因为 PHP 编程你几乎时时刻刻都在于数组打交道，对于数组的操作熟练程度，很大一部分因素关系着代码的优劣。

• ### php去重后重新排键值

因为我们已经移除了一些元素，因此数组看起来不是正常的序列。比如我们可能会得到：array(0=>’A’,2=>’B’,5=>’C’);。在某些情况下，这不是一个...