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

Sagiri

def q(a):
    if len(a) < 2:
        return a
    else:
        less = []
        high = []
        dump = a[0]
        for i in range(1, len(a)):
            if (a[i] <= dump):
                less.append(a[i])
            else:
                high.append(a[i])
        # less = [i for i in a[1:] if i <= dump]
        # high = [i for i in a[1:] if i > dump]
    return q(less) + [dump] + q(high)

a = [1, 32, 23, 46, 15, 6, 72]
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小的时候没有什么差别，不用太在意，大的时候，尽量别用，可以节省一些时间

import time

def timecount(func):

    def wapperd(*args, **kwargs):
        s = time.time()
        func(*args, **kwargs)
        t = time.time() - s
        print(f"{func.__name__} 运行 {t} ")
    return wapperd

@timecount
def rangN(N):
    N = len(N)
    for i in range(N):
        pass

@timecount
def rangLen(N):
    for i in range(len(N)):
        pass

if __name__ == '__main__':
    N = list(range(100000000))
    rangN(N)
    rangLen(N)

rangN 运行 6.960397958755493 
rangLen 运行 7.127407789230347 

hrp

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

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