quicksort in place performance（python）

Question

我被要求写一个'in place'Quicksort版本。创建了两个内部函数 - 一个递归函数和一个“就地排序”，它选择随机数据透视表（需要这样的问题），对列表进行排序并在排序后返回数据透视表的索引。

 import random 

def quicksort(lst): 

    def innerfunc(lst, start=0, end=(len(lst) - 1)): 
     temporal_pivot = subfunc(lst, start, end) 

     if (end - start > 1): 
      if (temporal_pivot == start or temporal_pivot == start + 1): 
       innerfunc(lst, temporal_pivot + 1, end) 

      elif (temporal_pivot == end or temporal_pivot == end - 1): 
       innerfunc(lst, 0 , temporal_pivot - 1) 

      else: 
       innerfunc(lst, 0 , temporal_pivot - 1), innerfunc(lst, temporal_pivot + 1, end) 


    def subfunc(l, start, end): 
     i_random = random.randint(start, end) # chooses random index! 
     l[i_random], l[start] = l[start], l[i_random] 

     i_pivot = start 
     pivot = l[start] 

     i = end 
     while i > i_pivot: 
      if l[i] <= pivot: 
       l.insert(i_pivot, l[i]) 
       i_pivot += 1 
       l.pop(i + 1) 

      else: 
       i = i - 1 

     return i_pivot 


    return innerfunc(lst) 

问题是运行时间 - 包含100元以上的速度很慢排序

列表。

你有一个想法如何提高“subfunc”算法和我的Quicksort性能？

谢谢！

奥伦

Answer 1

似乎subfunc效率不高 - 环和插入阵列的一部分。 我不是Python程序员，但我建议它可以导致内存重新分配和成本O（n）操作

Answer 2

问题是重复调用l.insert()和l.pop()。其中每个都具有O(n)复杂性，而您希望循环的每次迭代为O(1)。

您需要修改该功能，以便通过交换元素，而不是执行重复的插入和删除操作。

你可以在Wikipedia找到一些伪代码。