[已解决]不懂就问，这样写快速排序效率是不是更高点？

Sagiri

1. def q(a):
   
2.     if len(a) < 2:
   
3.         return a
   
4.     else:
   
5.         less = []
   
6.         high = []
   
7.         dump = a[0]
   
8.         for i in range(1, len(a)):
   
9.             if (a[i] <= dump):
   
10.                 less.append(a[i])
    
11.             else:
    
12.                 high.append(a[i])
    
13.         # less = [i for i in a[1:] if i <= dump]
    
14.         # high = [i for i in a[1:] if i > dump]
    
15.     return q(less) + [dump] + q(high)
    
16. 
    
17. a = [1, 32, 23, 46, 15, 6, 72]
    
18. print(q(a))

复制代码

注释的地方是《算法图解》里的代码，但是我觉得没必要遍历两次

最佳答案

月排行榜 / 总排行榜

Stubborn

2021-4-4 11:00:31

原来上来说  O  和 2O的时间效率都等于O 。

还有一个小建议：

for i in range(1, len(a)):

变为，可以减少每次运行len的时间
N =  len(a)
for i in range(1, N):

跳转到最佳答案楼层

Daniel_Zhang

可以算100个数，然后看运行时间

重复100次，计算运行时间的平均值

比较两种方法的平均值

Stubborn

原来上来说  O  和 2O的时间效率都等于O 。

还有一个小建议：

for i in range(1, len(a)):

变为，可以减少每次运行len的时间
N =  len(a)
for i in range(1, N):

hrp

Stubborn 发表于 2021-4-4 11:00
原来上来说  O  和 2O的时间效率都等于O 。

还有一个小建议：

for循环应该不会重复运行len，因为range仅生成一次

Stubborn

hrp 发表于 2021-4-4 11:26
for循环应该不会重复运行len，因为range仅生成一次

N小的时候没有什么差别，不用太在意，大的时候，尽量别用，可以节省一些时间

1. 
   
2. import time
   
3. 
   
4. def timecount(func):
   
5. 
   
6.     def wapperd(*args, **kwargs):
   
7.         s = time.time()
   
8.         func(*args, **kwargs)
   
9.         t = time.time() - s
   
10.         print(f"{func.__name__} 运行 {t} ")
    
11.     return wapperd
    
12. 
    
13. @timecount
    
14. def rangN(N):
    
15.     N = len(N)
    
16.     for i in range(N):
    
17.         pass
    
18. 
    
19. @timecount
    
20. def rangLen(N):
    
21.     for i in range(len(N)):
    
22.         pass
    
23. 
    
24. if __name__ == '__main__':
    
25.     N = list(range(100000000))
    
26.     rangN(N)
    
27.     rangLen(N)

复制代码

1. rangN 运行 6.960397958755493
   
2. rangLen 运行 7.127407789230347

复制代码

hrp

Stubborn 发表于 2021-4-4 11:44
N小的时候没有什么差别，不用太在意，大的时候，尽量别用，可以节省一些时间

我突然想起来  代码简洁之道  里写的：尽量不要用嵌套语句，嵌套语句运行比分步运行慢一点(大致意思)。难道这就是rangLen比rangN慢的原因