python quicksort - 这段代码可以改进吗？

Question

你能给我一些关于如何改进这段代码的建议吗？

def qsort(arr):
    if len(arr) < 2:
        return arr
    else:
        root =  arr[round(len(arr)/2)]
        arr.remove(root)
        min_  = [i for i in arr if i <  root]
        max_  = [i for i in arr if i >  root]
        oth_  = [i for i in arr if i == root]
        return  qsort(min_) + [root]+oth_ + qsort(max_)

Answer 1

我能想到两件事可以提高这段代码的效率。第一种是使用一个循环，将三个 i < root、i > root 和 i == root 条件作为 if/elif/else 语句作为主体，而不是对每个条件使用列表理解。这会将您触摸数组中每个元素的次数从大约 3 次减少到大约 1 次。

第二件事是从数组中删除根。通过这样做你不会完成太多（你可以只获取根索引并在需要根时引用 arr[root_index]），并且从数组中间删除一个元素可能有点像Python 中的昂贵操作（因为您没有获得索引，您实际上是再次在数组中搜索根，然后删除它，然后将索引中高于根的所有内容向下移动索引）。如果您决定不从数组中删除它，请记住不要重复计算它。

python quicksort - 这段代码可以改进吗？

python quicksort - Can this code be improved?

python

sorting

quicksort

qsort

python-3.x