python快速排序-这个代码可以改进吗

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<根，i>root和i==root条件，就像/elif/else语句作为主体一样，而不是对每个条件使用列表理解。这将把你触摸阵列中每个元素的次数从大约3次减少到大约1次。

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