快速排序实现（分区期间包含与排除枢轴元素）

Question

我正在尝试找出快速排序算法。我尝试过不同的实现。我遇到的问题与枢轴元素的包含/排除有关。

考虑这三种实现。

1. 此代码会导致 VS 代码出错，并且 VS 代码会停止。请注意，枢轴元素 (

   ind

   ) 仅在

   left

   中包含一次（至少在我看来是这样），并且它不会单独添加到函数的最后一行中：

   def quick_sort(arr):
       if len(arr)<=1:
           return arr
       ind = arr[0]
       left = [i for i in arr if i <= ind]           
       right = [i for i in arr if i > ind]     
       return quick_sort(left) + quick_sort(right)    
   

2. 如果我从

   ind

   中排除

   left

   （使用

   <

   而不是

   <=

   ）并在最后一行添加

   [ind]

   ，则它可以工作。但排序后的列表不会与原始列表有任何重复项：

   numbers = [5, 2, 3, 2, 7]
   print("Sum of numbers:", quick_sort(numbers))
   
   def quick_sort(arr):
       if len(arr)<=1:
           return arr
       ind = arr[0]
       left = [i for i in arr if i < ind]          
       right = [i for i in arr if i > ind]     
       return quick_sort(left) + [ind] + quick_sort(right)    
   

3. 最后，这个实现可以很好地对所有值进行正确排序。但我不明白这个实现和第一个实现有什么区别。为什么第一个会导致错误，而这个却有效？然而，在这两种情况下，我们都只包含一次枢轴 (

   ind

   )？

   numbers = [5, 2, 3, 2, 7]
   print("Sum of numbers:", quick_sort(numbers))
   
   def quick_sort(arr):
       if len(arr)<=1:
           return arr
       ind = arr[0]
       left = [i for i in arr if i < ind]  
       middle = [i for i in arr if i == ind]         
       right = [i for i in arr if i > ind]     
       return quick_sort(left) + middle + quick_sort(right) 
   

我检查了之前关于这个主题的问答，但没有找到任何关于这个问题的内容。

Answer 1

当

left

 获取给定列表中的 

all 值时（并且 right

 保持为空），

实现 #1 将遭受无限递归。在这种情况下，没有任何进展，递归调用将再次解决完全相同的问题，导致相同的重复递归调用......等等。例如，输入 [2, 1] 就会发生这种情况。

您已经正确识别了第二次实现的问题。如果主值有重复项，则会从结果中删除它们。第三次实现解决了这个问题。

第二个和第三个实现都解决了第一个实现的问题：保证递归调用将处理严格较短的列表，因为保证一个或所有主值不再是列表的成员它被传递给递归调用。

与您的问题无关，但快速排序通常作为“就地”算法实现，即在此过程中不创建新列表。相反，给定的列表是通过交换而改变的。请参阅有关快速排序的维基百科。